Hartanti, Bella Septina Ika (2021) Implementasi Pemrograman Dinamis dengan Teknik Convex Hull sebagai Langkah Optimasi dalam Pencarian Solusi Optimal pada Permasalahan SPOJ CLOUDMG: Cloud Computing. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05111740000117-Undergraduate_Thesis.pdf - Accepted Version Download (1MB) | Preview |
Abstract
Pemrograman Dinamis merupakan salah satu teknik optimasi yang cukup banyak diterapkan untuk menyelesaikan permasalahan. Pemrograman dinamis, seperti metode divide and conquer, menyelesaikan permasalahan dengan cara membagi permasalahan utama menjadi subpermasalahan. Pemrograman
dinamis secara umum diterapkan pada permasalahan optimasi
(Cormen et al, 2009). Implementasi strategi ini dalam kehidupan sehari-hari biasa digunakan dalam mencari solusi permasalahan rute optimal, graf, jaringan komputer, dsb. Permasalahan optimasi lain yang dapat menggunakan strategi dynamic programming yaitu adalah mencari total biaya optimal. Penelitian Tugas Akhir merepresentasikan persoalan mencari total biaya minimum persoalan Cloud Computing pada situs Sphere Online Judge. Secara umum persoalan yang akan diselesaikan pada penelitian Tugas Akhir ini adalah bagaimana cara melakukan komputasi dengan pemrograman dinamis convex hull.
Tugas akhir ini mengulas penggunaan strategi algoritma
pemrograman dinamis convex hull, yang digunakan untuk menyelesaikan permasalahan mencari total biaya minimum untuk
membeli semua server yang memenuhi kebutuhan dengan jenis server yang terbatas. Lalu, dengan memanfaatkan strategi ini, permasalahan dapat diselesaikan dengan cukup efisien, yaitu dengan kompleksitas O(n log n) dimana n merepresentasikan jumlah server yang harus dibeli.
Dari hasil uji coba pada studi kasus yang diberikan, didapat
hasil bahwa algoritma pemrograman dinamis convex hull memiliki efisiensi kinerja baik. Rata-rata waktu hasil uji coba adalah 0,06 detik. Sementara rata-rata memori hasil uji coba adalah 4,4 MB.
=====================================================================================================
Dynamic Programming is one of the most widely applied optimization techniques to solve problems. The implementation of this strategy in real life is commonly used in finding solutions to problems of optimal routes, graphs, computer networks, etc. This thesis can be represented as a problem of finding the minimum total
cost of cloud computing problems on the Sphere Online Judge site.
In general, the problem that will be resolved in this thesis is how to do computation with convex hull dynamic programming. This thesis represented a problem of finding the minimum total cost of cloud computing problems on the Sphere Online Judge site, i.e., the problem of buying all necessary servers against the limited server type. Convex hull dynamic programming strategy has been used to solve well and efficient this problem, i.e., by the complexity O (n log n) where n represents the number of servers that have to be purchased.
From the test results in the given case study, it has been shown that the convex hull dynamic programming algorithm has good performance efficiency. The average tests time used was 0.06 seconds, and the average memory used was 4.4 MB.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Uncontrolled Keywords: | convex hull, pemrograman dinamis, total biaya minimum |
| Subjects: | T Technology > T Technology (General) > T57.83 Dynamic programming |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Bella Septina Ika Hartanti |
| Date Deposited: | 02 Aug 2021 07:46 |
| Last Modified: | 04 Oct 2024 01:50 |
| URI: | http://repository.its.ac.id/id/eprint/84694 |
Actions (login required)
 |
View Item |