Dave, Michael (2018) Desain dan Analisis Algoritma Penentuan Dimensi Fungsi Periodik berbasis Metode Penjumlahan Euler Totient Studi Kasus : SPOJ (22269) Periodic Function, trip 1. Undergraduate thesis, Insitut Teknologi Sepuluh Nopember.
Preview |
Text
05111440000131-Undergraduate_Thesis.pdf - Accepted Version Download (2MB) | Preview |
Abstract
Permasalahan pencarian dimensi fungsi periodik merupakan sebuah permasalahan yang ada dan tergambarkan pada situs SPOJ dengan kode soal PERIOD1. Permasalahan ini mencakup pencarian rank dari keluarga fungsi periodik yang memiliki periode maksimal tertentu. Tujuan dari penelitian ini adalah mendesain serta mengimplementasikan algoritma untuk menentukan dimensi dari keluarga fungsi periodik yang demikian dan juga dapat dibuktikan dengan menyelesaikan permasalahan pada studi kasus SPOJ PERIOD1. Algoritma yang dibuat perlu efektif karena batasan waktu 1 detik sedangkan niliai periode maksimal yang diizinkan adalah 10^8.
Penyelesaian permasalahan ini terbagi dalam 2 domain utama yaitu domain konseptual dan domain komputasional. Domain konseptual bergerak dari fungsi periodik yang perlu direpresentasikan sebagai vektor dan penggabungannya membentuk matriks. Matriks yang terbentuk memiliki attribut yaitu rank matriks. Salah satu syarat pencarian rank matriks adalah sifat bebas linear yang berdasarkan hasil observasi memiliki keterkaitan dengan konsep pada teori bilangan yang dikenal dengan fungsi Euler Totient. Konsep Euler Totient inilah yang nantinya akan didesain dan diimplementasikan sedemikian rupa sehingga dapat menjadi solusi penentuan dimensi keluarga fungsi periodik. Hasil dari uji coba dan pembuktian kebenarannya menyatakan bahwa penjumlahan Euler Totient dengan pengoptimalan menggunakan sifat faktor bilangan dapat menjadi solusi penyelesaian permasalahan kasus PERIOD1 pada SPOJ serta menjadi solusi algoritma penentuan dimensi dari keluarga fungsi periodik. Algoritma yang diimplementasikan memiliki kompleksitas O(√(N)) dan dapat menyelesaikan permasalahan studi kasus SPOJ PERIOD1 dalam rata-rata waktu 0.21 ms.
=======================================================================================================
A problem about finding dimension of a periodic function can be found in SPOJ with problem code PERIOD1. This problem is about finding rank of the family of periodic function that have a maximum value of a period. The purpose of this observation were designing and implementing an algorithm to determine the dimension of the family of periodic function which can be shown by solving the problem of SPOJ PERIOD1. The algortihm should be effective in case of 1 second for the time limit of computation while the maximum allowable value of period is 10^8. The solution of this problem consist 2 domain which is conceptual domain and computational domain. The conceptual domain start from the periodic function that represented as a vector and its concatenation to form a matrix. The matrix has an attribute called rank matrix. One of the condition of finding the rank matrix is linearly independent which is in this observation sum up to have a corelation with a number theory concept called Euler Totient. This Euler Totient function should be designed and implemented in such a way that it may be the solution to determine the dimension of this periodic function's family. The result from the observation show that the sum of the Euler Totient and its optimization using a correlation with number factor can be a solution for the PERIOD1's problem which can also be the algorithm to determine the dimension of a periodic function's family. The algorithm has a O(√(N)) and can solved the problem in the average of 0.21 ms.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 006.746 Dav d-1 3100018076711 |
| Uncontrolled Keywords: | dimensi, Euler Totient, fungsi periodik, matriks, rank matriks, Sieve of Eratosthenes, vektor |
| Subjects: | Q Science > QA Mathematics > QA184 Algebra, Linear Q Science > QA Mathematics > QA76.9.D33 Data compression (Computer science) Q Science > QA Mathematics > QA9.58 Algorithms |
| Divisions: | Faculty of Information and Communication Technology > Informatics > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Dave Michael |
| Date Deposited: | 10 Dec 2020 06:11 |
| Last Modified: | 10 Dec 2020 06:11 |
| URI: | http://repository.its.ac.id/id/eprint/56242 |
Actions (login required)
 |
View Item |