Desain Metode Pemrograman Dinamis Dengan Teknik Bitmask dan Komputasi Perpangkatan Matriks pada Penyelesaian Persoalan SPOJ 21171 Fractal Domino

Tjitrodjojo, Evelyn (2022) Desain Metode Pemrograman Dinamis Dengan Teknik Bitmask dan Komputasi Perpangkatan Matriks pada Penyelesaian Persoalan SPOJ 21171 Fractal Domino. Other thesis, Institut Teknologi Sepuluh Nopember.

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

Abstract

Domino adalah sebuah persegi panjang yang terdiri dari dua sel persegi yang berdekatan, dan dapat berbentuk horizontal (dengan ukuran 1x2) atau vertikal (dengan ukuran 2x1). Permasalahan yang diberikan pada studi kasus SPOJ 21171 Fractal Domino adalah menghitung proporsi dari domino vertikal pada pola orde-K yang diminta.
Yang menjadi permasalahan tersendiri adalah melakukan perhitungan proporsi domino vertikal yang membutuhkan total domino vertikal dibagi dengan total keseluruhan kemungkinan yang harus diselesaikan dengan batas waktu 1 detik. Pada Tugas Akhir ini, akan dirancang penyelesaian dari permasalahan ini menggunakan pemrograman dinamis dengan teknik bitmask dan komputasi perpangkatan matriks.
Hasil dari tugas akhir ini telah berhasil menyelesaikan permasalahan dengan rata-rata waktu penyelesaian dalam 0.041 detik dengan menggunakan memori 5.39 MB.
================================================================================================
Dominoes are rectangles composed of two adjacent square cells, and can be either horizontal (1 × 2) or vertical (2 × 1). The task in the SPOJ 21171 – Fractal Domino’s problem is to calculate the expected proportion of vertical dominoes in the requested K-order pattern.
The problem in itself is calculating the proportion of vertical dominoes which requires the total number of vertical dominoes divided by the total number of possibilities that must be completed within a time limit of 1 second. In this undergraduate theses, the solution of this problem will be designed using dynamic programming with bitmask and matrix exponentiation technique.
The results of this final project have successfully solved the problem with an average completion time of 0.041 seconds using 5.39 MB of memory.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Dynamic Programming, Pemrograman Dinamis, Perpangkatan Matriks, Power of Matrix, Proportion, Proporsi
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:	Evelyn Tjitrodjojo
Date Deposited:	28 Jan 2022 04:24
Last Modified:	02 Nov 2022 04:14
URI:	http://repository.its.ac.id/id/eprint/92538

Actions (login required)

View Item