Hapriarso, Pramudito (2018) Desain Dan Analisis Algoritma Komputasi Graf Hamilton Pada Penyelesaian Persoalan: Spoj Klasik 8750 Word Play. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5114100035-Pramudito-Hapriarso-Buku_TA_RepoITS.pdf - Accepted Version Download (1MB) | Preview |
Abstract
Permasalahan yang dibahas adalah permasalahan penyusunan beberapa buah string sepanjang K menjadi sebuah string sepanjang N yang diinginkan. Diberikan sebuah kata dengan panjang N yang dipisahkan menjadi N-K+1 buah subkata dengan panjang K dan diurutkan dengan urutan leksikografis. Diperlukan sebuah solusi unik untuk menyusun kembali subkata-subkata yang telah urut berdasarkan urutan leksikografis tadi menjadi sebuah kata utuh yang diinginkan.
Penyelesaian permasalahan dilakukan dengan cara merepresentasikan masukan permasalahan tersebut ke dalam bentuk graf. Dengan menjadikan subkata-subkata yang diberikan sebagai simpul (node) dari sebuah graf. Graf yang akan dibentuk merupakan graf berarah yang mengandung lintasan Hamilton. Sebuah graf berarah dapat dikatakan memiliki lintasan hamilton apabila masing-masing simpul (node) dari graf tersebut dapat dilewati sejumlah tepat satu kali. Sebelum digunakan, subkata-subkata yang menjadi masukan sistem ditampung ke dalam container map. Container map ini telah disediakan oleh Standard Template Library (STL). Selain menyediakan container, Standard Template Library (STL) ini juga menyediakan komponen-komponen lain seperti algoritma, fungsi, dan juga iterators yang dapat digunakan.
Pada tugas akhir ini akan dirancang penyelesaian masalah yang disampaikan pada paragraf pertama dengan menggunakan pengimplementasian metode graf hamilton dan juga penggunaan Standard Template Library (STL). Solusi yang dikembangkan berjalan dengan kompleksitas waktu O((N-K+1)log2(N-K+1)), dimana N adalah panjang kata yang dicari, K adalah panjang subkata yang menjadi masukan.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Uncontrolled Keywords: | graf, graf hamilton, SPOJ word play, string |
| Subjects: | T Technology > T Technology (General) > T58.5 Information technology. IT--Auditing |
| Divisions: | Faculty of Information and Communication Technology > Informatics > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Hapriarso Pramudito |
| Date Deposited: | 21 Jun 2021 02:21 |
| Last Modified: | 21 Jun 2021 02:21 |
| URI: | http://repository.its.ac.id/id/eprint/54247 |
Actions (login required)
 |
View Item |