Perbandingan Kinerja Algoritma Berlekamp-Massey dan Interpolasi Lagrange sebagai Metode Penyelesaian Permasalahan Pembangkitan Formula Barisan Bilangan Berpola: Studi Kasus SPOJ 40192 BATTLECRY

Hartono, Aldo Yaputra (2023) Perbandingan Kinerja Algoritma Berlekamp-Massey dan Interpolasi Lagrange sebagai Metode Penyelesaian Permasalahan Pembangkitan Formula Barisan Bilangan Berpola: Studi Kasus SPOJ 40192 BATTLECRY. Other thesis, Institut Teknologi Sepuluh Nopember.

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

Abstract

Penempatan papan catur adalah salah satu masalah kombinatorial paling umum yang tujuan utamanya adalah menghitung kemungkinan konfigurasi berdasarkan beberapa variabel yang diberikan. Dalam studi kasus ini, terdapat empat buah bidak catur (sebuah bidak raja hitam, sebuah bidak raja putih, dan dua buah bidak benteng putih) yang akan diletakkan pada sebuah papan catur dengan ketentuan setiap bidak harus menempati petak yang berbeda. Dengan menerapkan aturan permainan catur pada umumnya, maka jumlah konfigurasi penempatan keempat bidak tersebut pada sebuah papan catur dengan ukuran tertentu sedemikian sehingga raja hitam mengalami sekakmat akan menjadi topik utama Tugas Akhir ini. Permasalahan ini dikategorikan sebagai permasalahan classical pada Sphere Online Judge. Pada Tugas Akhir ini akan dibahas analisis, desain, dan implementasi solusi dari permasalahan. Topik Tugas Akhir ini mengacu pada perbandingan kinerja beberapa metode dalam menghasilkan formula untuk menghitung jumlah konfigurasi penempatan bidak catur. Metode bruteforce digunakan untuk menghasilkan barisan bilangan berpola yang kemudian digunakan pada saat menyusun formula penyelesaian permasalahan. Algoritma Berlekamp-Massey dan interpolasi Lagrange digunakan untuk menghasilkan formula barisan bilangan berpola dan performa dari keduanya akan dibandingkan. Berdasarkan hasil pengujian pada studi kasus yang diberikan, solusi kedua metode menempati peringkat kedua dengan rata-rata waktu 0,01 detik dan rata-rata memori 5,3 MB. Dapat juga disimpulkan bahwa penerapan interpolasi Lagrange (0,0006 detik) lebih efisien daripada algoritma Berlekamp-Massey (0,0042 detik) dalam menghasilkan formula penyelesaian.
========================================================================================================================
Chessboard placement is one of the most common combinatorial problems which main purpose is to count possible configurations based on some given variables. In this case study, there are four chess pieces (a black king piece, a white king piece, and two white rook pieces) which will be placed on a chessboard with the provision that each piece must occupy a different square. By applying the rules of chess in general, the number of configurations for the placement of the four pieces on a chessboard of a certain size so that the black king experiences checkmate will be the main topic of this Final Project. This problem is categorized as a classical problem in Sphere Online Judge. This Final Project will discuss the analysis, design, and implementation of solutions to problems. The topic of this Final Project refers to the performance comparison of some methods in generating formulas to calculate the number of configurations for placement the chess pieces. The bruteforce method is used to generate a sequence of patterned numbers which are then used when generating formulas for solving the problems. The Berlekamp-Massey algorithm and Lagrange interpolation are used to generate patterned number sequence formulas and both performances will be compared. Based on the test results in the given case study, the solutions of both methods were ranked second with an average time of 0.01 seconds and an average memory of 5.3 MB. It can also be concluded that the implementation of Lagrange interpolation (0.0006 seconds) is more efficient than the Berlekamp-Massey algorithm (0.0042 seconds) in generating the solving formula.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Algoritma Berlekamp-Massey, Interpolasi Lagrange, Berlekamp-Massey Algorithm, Lagrange Interpolation
Subjects:	Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Aldo Yaputra Hartono
Date Deposited:	02 Feb 2023 07:28
Last Modified:	02 Feb 2023 07:28
URI:	http://repository.its.ac.id/id/eprint/96016

Actions (login required)

View Item