Santoso, Natasha Valentina (2020) Penerapan Pemrograman Dinamis Untuk Menyelesaikan Permasalahan Komputasi Geometri: Studi Kasus SPOJ 7693 Environmental Engineering. Other thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05111640000183-Undergraduate_Thesis.pdf - Accepted Version Download (2MB) | Preview |
Abstract
Permasalahan ini diangkat dari soal pada situs SPOJ “Environmental Engineering” yang membahas mengenai pendistribusian air bersih. Permasalahan tersebut menceritakan cara menyalurkan air dari daerah kaya air ke daerah langka air. Masalah ini akan diselesaikan dengan membangun suatu jaringan pipa yang menghubungkan kedua tempat tersebut dengan syarat jaringan pipa tidak ada yang saling bersilangan. Hasil akhir yang diminta adalah total panjang minimal pipa yang harus dibangun. Tugas Akhir ini merancang penyelesaian masalah dengan melakukan pemodelan jaringan pipa berdasarkan prinsip kesebangunan matematis. Jaringan pipa akan dihitung dengan cara pemrograman dinamis karena pemodelan dapat dipecah menjadi submasalah optimal dan submasalah tumpang tindih. Solusi yang dikembangkan berjalan dengan kompleksitas O(N3), dimana N adalah jumlah titik lokasi. Solusi ini berhasil melakukan komputasi geometri dengan cepat. ================================================================================================================================
This problem is based on the problem on SPOJ “Environmental Engineering” which discusses the distribution of fresh water throughout the earth. This specific problem covers how to connect water scarce regions to water abundant regions. The idea in this project is to construct non-crossing gigantic pipelines that can transport water to these water scarce regions. The final objective is to calculate the total minimum length of all pipes that connect two adjacent locations. In this Thesis, a solution will emerge by modeling the pipelines based on the principle of similarity in geometry. These pipelines modeling can be broken down into an optimal substructure and overlapping subproblems, which allows the calculation to be done with dynamic programming. The complexity of the solution developed is O(N3), where N is the number of locations. The solution defined has successfully answered the geometry problem.
| Item Type: | Thesis (Other) |
|---|---|
| Additional Information: | RSIf 003.85 San p-1 2020 |
| Uncontrolled Keywords: | komputasi geometri, kesebangunan geometri, pemrograman dinamis |
| 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: | Santoso Natasha Valentina |
| Date Deposited: | 05 Jun 2023 03:26 |
| Last Modified: | 05 Jun 2023 03:26 |
| URI: | http://repository.its.ac.id/id/eprint/73054 |
Actions (login required)
 |
View Item |