Penerapan Implicit Tree dengan Paradigma Divide and Conquer pada Studi Kasus SPOJ HC10000 Hofstadter-Conway 10000 Dollar Sequence

Al Giffary, Fadhil Musaad (2021) Penerapan Implicit Tree dengan Paradigma Divide and Conquer pada Studi Kasus SPOJ HC10000 Hofstadter-Conway 10000 Dollar Sequence. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

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

Abstract

Barisan Hofstadter-­Conway 10000 Dollar adalah suatu baris­ an yang diajukan oleh matematikawan inggris, John Conway di suatu perkuliahannya di Bell Labs pada tahun 1988. Co­ nway menyebutnya sebagai barisan “gila” yang kemudian menjadi salah satu permasalahan teori bilangan yang belum terpecahkan. Barisan ini memiliki bentuk rekurens sederhana a(n) = a(a(n − 1)) + a(n − a(n − 1)), a(1) = a(2) = 1. Pada studi lebih lanjut barisan ini dapat digunakan untuk menciptakan citra maupun fitur audio.

Tugas Akhir ini mengacu pada penerapan struktur data im­ plisit untuk mencari nilai dari sebuah fungsi penjumlahan pada sebuah rekurens dengan tujuan mengoptimalkan kompleksitas ruang dan waktu. Inti permasalahan pada HC10000 adalah mencari penjumlahan prefiks pada barisan Hofstadter–Conway 10000 Dollar dalam modulo 10^9 dengan cara membentuk sebuah implicit tree yang dapat menyimpan penjumlahan suku pada barisan tersebut dan dapat di­query menggunakan paradigma divide and conquer sehingga operasinya memiliki kompleksitas logaritmik terhadap jumlah suku.
=====================================================================================================
Hofstadter-­Conway 10000 dollar is a sequence proposed by British mathematician, John Conway in his lecture at Bell Labs on 1988. Conway state that this sequence is ”crazy” which then became one of unsolvable problem in number theory. The sequence have a simple recurrence a(n) = a(a(n − 1)) + a(n − a(n − 1)), a(1) = a(2) = 1. On later study, this sequence can be used to create a digital image or audio feature. This thesis reviewed on the implementation of implicit data structure to find the value of a summatory function on a recurrence with the intention to optimized the time and space complexity. The core of the problem in HC10000 is to find the prefix sum of Hofstadter­Conway 10000 Dollar sequence under modulo 10^9 by forming an implicit tree which saves sum of its terms and can be queried using divide and conquer paradigm resulting in having logarithmic complexity toward the number of term.

Item Type:	Thesis (Undergraduate)
Uncontrolled Keywords:	divide and conquer, koefisien binomial, segitiga pa­scal, struktur data implisit, binomial coefficient, implicit data structure, pascal triangle
Subjects:	T Technology > T Technology (General) > T11 Technical writing. Scientific Writing T Technology > T Technology (General) > T58.8 Productivity. Efficiency
Divisions:	Faculty of Information and Communication Technology > Informatics > 55201-(S1) Undergraduate Thesis
Depositing User:	Fadhil Musaad Al Giffary
Date Deposited:	03 Mar 2021 09:34
Last Modified:	03 Mar 2021 09:34
URI:	http://repository.its.ac.id/id/eprint/83323

Actions (login required)

View Item