Suryaputra, Brian Rainer (2019) Desain dan Analisis Algoritma Faktorisasi Bilangan Trial Division dan Pemangkatan Matriks pada Studi Kasus SPOJ 30945 Non Coprime Sequences. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
![[thumbnail of 05111540000061-Brian Rainer Suryaputra-Buku_TA.pdf]](http://repository.its.ac.id/style/images/fileicons/text.png) |
Text
05111540000061-Brian Rainer Suryaputra-Buku_TA.pdf - Accepted Version Restricted to Repository staff only until 1 October 2023. Download (1MB) | Request a copy |
|
Text
05111540000061-Brian Rainer Suryaputra-Buku_TA.pdf - Accepted Version Restricted to Repository staff only until 1 October 2023. Download (1MB) | Request a copy |
Abstract
Permasalahan yang dibahas dalam Tugas Akhir ini adalah permasalahan untuk menghitung banyak deret non-koprima pada studi kasus SPOJ 30945 Non-Coprime Sequences. Deret non koprima, dinotasikan sebagai F(n,m), adalah banyak deret dengan panjang n di mana elemen dalam deret adalah faktor pembagi positif bilangan m dan setiap deret yang bersebelahan memiliki satu faktor pembagi prima yang sama, dengan kata lain elemen yang bersebelahan adalah saling non-koprima.
Tugas Akhir ini merancang sebuah penyelesaian dengan menganalogikan permasalahan menghitung banyak deret non-koprima menjadi menghitung banyak path unik dalam graph. Node dalam graph dibentuk dengan memfaktorisasi bilangan menggunakan algoritma Trial Division dan path unik dihitung dengan menggunakan teknik berhitung dalam Kombinatorik dan algoritma Pemangkatan Matriks sebagai representasi relasi non-koprima dan jumlah path.
Solusi Tugas Akhir ini mampu menyelesaikan permasalahan dengan rata-rata waktu penyelesaian 0,25 detik dengan penggunaan memori 32 MB.
================================================================================================
The problem imposed in this Final Project is to determine how many non coprime sequnces on case study SPOJ 30945 NonCoprime Sequences. Non-coprime sequences, denoted as F(n,m), is the number of sequences with length n which has positive divisors of m as elements and for any two adjacent element has at least one mutual prime divisor, which is non-coprime.
The Final Project design an approach to count such noncoprime sequences as counting unique paths in a graph. Nodes in the graph are created by number factorization using Trial Division algorithm and unique paths are derived from counting techniques in Combinatorics and Matrix Exponentiation algorithm as non-coprime relations representation and count of paths.
This Final Project’s solution successfully solved the problem with average time of 0.25 seconds and memory usage 32 MB.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 006.746 Sur d-1 2019 |
| Uncontrolled Keywords: | Deret, Faktorisasi Bilangan, Graph, Kombinatorik, Koprima, Pemangkatan Matriks |
| Subjects: | Q Science > QA Mathematics > QA76.9.D33 Data compression (Computer science) Q Science > QA Mathematics > QA9.58 Algorithms |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Brian Rainer Suryaputra |
| Date Deposited: | 27 Sep 2021 15:46 |
| Last Modified: | 27 Sep 2021 15:46 |
| URI: | http://repository.its.ac.id/id/eprint/60871 |
Actions (login required)
 |
View Item |