Desain dan Analisis Metode Pemrograman Dinamis dengan Strategi Profil pada persoalan perhitungan banyaknya partisi persegi panjang menjadi dua subdaerah: Studi Kasus E-Olymp 1478 Rectangle

Yendri, Sheinna (2022) Desain dan Analisis Metode Pemrograman Dinamis dengan Strategi Profil pada persoalan perhitungan banyaknya partisi persegi panjang menjadi dua subdaerah: Studi Kasus E-Olymp 1478 Rectangle. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

Text 05111840000038-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 April 2024. Download (2MB) | Request a copy

Abstract

Suatu persegi panjang dapat dinyatakan dipartisi menjadi dua subdaerah, di mana untuk dinyatakan sebagai suatu subdaerah yang valid, maka unit 1 × 1 yang membentuk subdaerah tersebut harus saling terhubung oleh setidaknya satu sisi dari unit 1 × 1 lain dalam subdaerah yang sama. Banyak konfigurasi partisi yang valid untuk setiap persegi panjang beragam berdasarkan ukuran dari persegi panjang tersebut, dan menjadi permasalahan dalam Tugas Akhir. Permasalahan ini dikategorikan sebagai permasalahan kombinatorik dengan tingkat kesulitan very difficult pada situs E­-Olymp Online Judge. Meskipun terkategori dalam permasalahan kombinatorik, solusi yang digunakan justru berbasis rekuren dan tidak didekati dengan solusi kombinatorik. Dalam Tugas Akhir ini, akan dilakukan analisis, desain, dan implementasi solusi permasalahan tersebut.
Tugas Akhir ini mengacu pada penerapan metode pemrograman dinamis dengan strategi profil untuk mencari banyaknya konfigurasi partisi persegi panjang valid yang dilakukan secara prakomputasi untuk memenuhi batasan waktu yang diberikan. Metode pemrograman dinamis dengan strategi profil memiliki karakteristik khusus yaitu mengeksploitasi struktur spesial dari suatu permasalahan tertentu, yang disebut sebagai profil, yaitu konfigurasi baris dalam permasalahan Rectangle. Selain itu, dengan batasan nilai ukuran persegi panjang maksimal mencapai 11 unit pada studi kasus, maka diperlukan implementasi big integer untuk menyelesaikan permasalahan Tugas Akhir ini. Implementasi big integer akan dilakukan dengan dua metode yaitu dengan modifikasi tipe data primitif numerik atau menggunakan tipe data ekstensi __int128, di mana kinerja keduanya akan dibandingkan.
Berdasarkan hasil uji coba pada studi kasus yang diberikan, penyelesaian menggunakan metode pemrograman dinamis dengan strategi profil secara prakomputasi membutuhkan rata­rata waktu sebesar 0.0012 detik dan rata­rata memori sebesar 530 KiB. Solusi ini berhasil menempati peringkat pertama pada situs E­-Olymp Online Judge dan mendapatkan grade A dari segi penggunaan memori, yang berarti solusi menggunakan lebih sedikit sumber daya dibandingkan 90% solusi lainnya. Didapatkan pula bahwa implementasi menggunakan tipe data ekstensi __int128 (8.882 detik) sedikit lebih baik dibandingkan dengan modifikasi tipe data primitif numerik (8.933 detik).
================================================================================================
A rectangle can be partitioned into two subregions, where to be declared as a valid subregion, each 1 × 1 unit that make up the subregion must be connected by at least one edge of the other 1 × 1 unit in the same subregion. The number of valid partition configurations for each rectangle varies based on the size of the rectangle, and becomes the problem in this thesis. This problem is categorized as a very difficult combinatoric problem in E-­Olymp Online Judge site. Although being categorized in the combinatoric domain, turns out the efficient solution is based on recurrence and is not approached by a combinatoric solution. In this thesis, analysis, design, and implementation of the solution will be carried out.
This thesis reviewed on the implementation of dynamic programming with profile to find the number of valid rectangular partition configurations that are pre-­computed to meet the given time constraint. Dynamic programming with profile method has a special characteristics, exploiting the special structure of a particular problem, which is referred as a profile, like the row configuration as in the Rectangle problem. In addition, with a maximum rectangular size limit of 11 units, it is necessary to implement big integer to solve the problem in this thesis. Big integer implementation will be carried out by two methods, by modifying the numeric primitive data type or using the __int128 extension data type, where the performance of the two will be compared.
Based on the result of testing from given case studies, the solution using the pre-­computation of dynamic programming with profile method requires an average time of 0.0012 seconds and an average memory of 530 KiB. This solution managed to rank first and get a grade A in terms of memory usage, which means it uses less resources than 90% of all solutions submitted. It was also found that the implementation using the extension data type __int128 (8,882 seconds) was slightly better than the modified numeric primitive data type (8,933 seconds).

Item Type:	Thesis (Undergraduate)
Uncontrolled Keywords:	big integer, dynamic programming with profile, rectangle partitioning, partisi persegi panjang, pemrograman dinamis dengan strategi profil.
Subjects:	Q Science > QA Mathematics > QA9.58 Algorithms 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:	Sheinna Yendri
Date Deposited:	25 Jan 2022 06:40
Last Modified:	25 Jan 2022 06:40
URI:	http://repository.its.ac.id/id/eprint/92496

Actions (login required)

View Item