Kamurapi, Dimas (2020) Desain dan Analisis Algoritma Untuk Mendapatkan Minimum Spanning Tree dengan Batasan Derajat Simpul dalam Penyelesaian Permasalahan SPOJ PT07E - Yet Another Computer Network Problem. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05111640000002-Undergraduate_Thesis.pdf Download (2MB) | Preview |
Abstract
Permasalahan dalam tugas akhir ini dapat dijumpai di dunia nyata namun sudah disederhanakan ke dalam bentuk soal yang terdapat pada situs Sphere Online Judge “PT07E – Yet Another Computer Network Problem”. Pada permasalahan tersebut dicari keluaran berupa topologi jaringan yang dapat menghubungkan tiap komputer dengan batasan jumlah konektor yang tersedia dan biaya kabel yang minimal. Pada permasalahan tersebut diberikan masukan berupa jumlah komputer, jumlah kabel, batasan konektor dan biaya yang dibutuhkan untuk menghubungkan antar komputernya.
Dengan memperhatikan karakteristik persoalan yang akan diselesaikan pada penelitian tugas akhir ini, dapat digunakan metode pendekatan Kruskal’s algorithm yang dimodifikasi dan dioptimasi dengan Randomized algorithm. Kemudian dibandingkan pengaruh dari Randomized algorithm untuk penyelesaian permasalahan ini.
Algoritma penyelesaian diimplementasikan dengan menggunakan bahasa pemrograman C++. Hasil uji coba dengan algoritma yang telah dirancang memiliki rata-rata skor akhir 4023389,389. Sedangkan untuk uji coba tanpa optimasi Randomized algorithm memiliki skor akhir 4023708,67. Sehingga dapat ditarik kesimpulan bahwa Randomized algorithm berpengaruh untuk mendapatkan hasil skor akhir yang lebih kecil atau lebih baik untuk menyelesaikan permasalahan ini.
===========================================================
The problems in this undergraduate thesis can be found in the real world but have been simplified into the form of questions contained on the Sphere Online Judge site "PT07E - Yet Another Computer Network Problem". In this problem, the output required in the form of a network topology that can connect each computer with the limits of existing connectors and minimal cable costs. In this case the input is given in the form of the number of computers, the number of cables, the limits of the connector and the cost required to connect between computers.
By paying attention to the characteristics of the problems that will be solved in this undergraduate thesis research, we can use the modified Kruskal’s algorithm approach and optimization with the Randomized algorithm. Then compare the effect of the Randomized algorithm for solving this problem.
The settlement algorithm is implemented using the C ++ programming language. Trials result with an algorithm that has been designed have an average final score of 4023389,389. Whereas for trials without optimization the Randomized algorithm have final score of 4023708.67. So it can be concluded that the Randomized Algorithm influences to get smaller result or better results to solve this problem.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 005.1 Kam d-1 • Kamurapi, Dimas |
| Uncontrolled Keywords: | Kruskal’s Algorithm, Randomized Algorithm |
| Subjects: | T Technology > T Technology (General) > T57.84 Heuristic algorithms. |
| Divisions: | Faculty of Information and Communication Technology > Informatics > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Dimas Kamurapi |
| Date Deposited: | 05 Aug 2020 03:26 |
| Last Modified: | 18 May 2023 14:50 |
| URI: | http://repository.its.ac.id/id/eprint/76791 |
Actions (login required)
 |
View Item |