Perancangan Dan Analisis Penerapan Teknik Pemrograman Dinamis Dan Metode Fast Fourier Transform Pada Studi Kasus SPOJ 37444 – Anti Hash II

Maulana, Fadel Pramaputra (2024) Perancangan Dan Analisis Penerapan Teknik Pemrograman Dinamis Dan Metode Fast Fourier Transform Pada Studi Kasus SPOJ 37444 – Anti Hash II. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025201260-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2026. Download (2MB) | Request a copy

Abstract

Polinomial hash dari suatu string didefinisikan dengan mengubah setiap huruf dalam string menjadi nilai numerik sesuai dengan posisinya dalam alfabet. Pada studi kasus Anti Hash II, ditentukan jumlah banyaknya string yang memenuhi suatu nilai polinomial hash dengan menggunakan fungsi polinomial hash yang telah diberikan. Banyaknya kombinasi karakter yang dapat dibuat dan pengulangan subproblem yang dapat terjadi merupakan permasalahan dari tugas akhir ini. Dalam tugas akhir ini, dilakukan analisis, desain, dan implementasi solusi permasalahan tersebut.
Tugas akhir ini mengacu pada permasalahan berbasis rekuren sehingga digunakan metode pemrograman dinamis untuk mencari banyaknya string yang memenuhi nilai hash polynomial yang diberikan. Seiring dengan batasan panjang string yang besar, perhitungan perkalian polinomial akan menjadi permasalahan pada kompleksitas waktu. Oleh karena itu digunakan metode fast Fourier transform (FFT) untuk mempercepat proses ini.
Metode uji coba pada tugas akhir ini terdiri dari uji coba kebenaran, yaitu dengan mengirimkan kode sumber dari program yang telah dibuat ke situs penilaian daring Sphere Online Judge (SPOJ) dan uji coba kinerja untuk mengukur efektivitas dari algoritma dengan kompleksitas yang diharapkan.
Berdasarkan hasil uji coba pada studi kasus yang diberikan, solusi pendekatatan pemrograman dinamis dan fast Fourier transform menempati peringkat pertama dengan waktu rata-rata 2,62 detik dan memori rata-rata 19 MB. Hasil dari tugas akhir ini menghasilkan algoritma perhitungan banyaknya kombinasi hash polinomial string dan diharapkan dapat memberikan kontribusi pada perkembangan ilmu pengetahuan dan teknologi informasi.
=====================================================================================================================================
The hash polynomial of a string is defined by converting each letter in the string into a numeric value according to its position in the alphabet. In the case of Anti Hash II, we are asked to determine the number of strings that satisfy a given hash polynomial value using the provided hash polynomial function. The number of possible character combinations and the possibility of overlapping subproblems are the challenges addressed in this Final Project. The solution to this problem involves analysis, design, and implementation.
This Final Project focuses on a recursive problem, which requires the use of dynamic programming to find the number of strings that satisfy the given hash polynomial value. Due to the large length constraint of the string, the computation of polynomial multiplication becomes a time complexity issue. Therefore, the fast Fourier transform (FFT) method is used to accelerate this process.
The testing methods in this Final Project consist of correctness testing, which involves submitting the source code of the implemented program to the online judge platform Sphere Online Judge (SPOJ) for verification, and performance testing to measure the effectiveness of the algorithm with the expected complexity.
Based on the test results on the given case study, the dynamic programming approach and fast Fourier transform solution ranked first with an average time of 2,62 seconds and an average memory of 19 MB. The results of this final project produce an algorithm for calculating the number of polynomial string hash combinations and are expected to contribute to the development of science and information technology.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Polinomial Hash, Pemrograman Dinamis, Fast Fourier Transform, Hash Polynomial, Dynamic Programming
Subjects:	Q Science > QA Mathematics > QA159 Algebra Q Science > QA Mathematics > QA401 Mathematical models. Q Science > QA Mathematics > QA404 Fourier series Q Science > QA Mathematics > QA76.6 Computer programming. Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Fadel Pramaputra Maulana
Date Deposited:	25 Jul 2024 07:11
Last Modified:	25 Jul 2024 07:15
URI:	http://repository.its.ac.id/id/eprint/109060

Actions (login required)

View Item