Agathon, Karsten Ari (2017) Desain Dan Analisis Algoritma Penyelesaian Persoalan SPOJ Maximum Edge Of Powers Of Permutation Dengan Metode Permutation Cycles Finding Dan FFT Convolution. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5112100110-Undergraduate-Theses.pdf - Published Version Download (3MB) | Preview |
Abstract
Permasalahan dalam buku tugas akhir ini adalah permasalahan “Maximum Edge of Powers of Permutation” yang terdapat pada situs penilaian daring Sphere Online Judge(SPOJ) dengan nomor soal 6895 dan kode soal MEPPERM. Dalam permasalahan ini, diberikan sejumlah simpul yang masing-masing memiliki bobot keluar dan masuk. Diberikan suatu permutasi terhadap sejumlah simpul tersebut. Suatu graf dibentuk dari setiap simpul yang terhubung ke simpul hasil permutasi dengan bobot jumlah bobot keluar simpul asal dan bobot masuk simpul tujuan. Dicari sisi dengan bobot terbesar pada setiap graf yang dibentuk dari hasil pangkat permutasi.
Tugas akhir ini akan mengimplementasikan metode pencarian permutasi siklus dan konvolusi menggunakan transformasi Fourier cepat(FFT) dalam menyelesaikan permasalahan Maximum Edge of Powers of Permutation. Metode transformasi Fourier cepat yang digunakan adalah algoritma Cooley-Tukey.
Implementasi dalam tugas akhir ini menggunakan bahasa pemrograman C++. Hasil uji coba menunjukkan bahwa sistem menghasilkan bobot sisi maksimum pada setiap pangkat permutasi dengan benar dan memiliki pertumbuhan waktu dengan kompleksitas O(NMlogNM+Q*sqrt(N)).
=====================================================================================
This final project is based on “Maximum Edge of Powers of Permutation” problem on SPOJ with problem number 6895 and problem code MEPPERM. In this problem, given vertices which each have weight in and out. Given a permutation for those vertices. A graph can be built by connecting each vertices to its permutation with edge weight sum of vertex weight out and vertex weight in from its permutation. Determine edge with maximum weight from each graph which are created from the powers of permutation.
This final project implements permutation cycles finding and convolution using fast Fourier Transform(FFT) to solve the problem of Maximum Edge of Powers of Permutation. Fast Fourier transform method used is Cooley-Tukey algorithm.
The implementation of final project uses C++ programming language. The experiment result proved the system provide edge with maximum weight for each powers of permutation correctly and has growth time with complexity of O(NMlogNM+Q*sqrt(N)).
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Uncontrolled Keywords: | Permutasi Siklus; Pangkat Permutasi; Bobot Maksimum; FFT; Konvolusi; Permutation Cycles; Powers of Permutation; Maximum Weight; Convolution. |
| Subjects: | T Technology > T Technology (General) Z Bibliography. Library Science. Information Resources > ZA Information resources |
| Divisions: | Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | KARSTEN ARI AGATHON |
| Date Deposited: | 19 Apr 2017 02:01 |
| Last Modified: | 08 Mar 2019 06:30 |
| URI: | http://repository.its.ac.id/id/eprint/3694 |
Actions (login required)
 |
View Item |