Mohammad, Fandy Putra (2020) Desain dan Analisis Penyelesaian Permasalahan Linear Recursive Sequence pada Studi Kasus : SPOJ HAL9000. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05111640000080-Fandy_Putra_Mohammad-Buku_TA.pdf Download (1MB) | Preview |
Abstract
dalam bidang matematika. Berbagai contohnya antara
lain: faktorial, bilangan fibonacci, bilangan lucas, dan lain-lain. Selain di bidang matematika, linear recursive sequence memiliki banyak manfaat di bidang lainnya seperti, ekonomi makro, bidang digital, dan lain-lain. Penelitian Tugas Akhir ini dapat direpresentasikan
sebagai persoalan Linear Recursive Sequence dan
terdapat pada situs Sphere Online Judge 100pct failure in 72 hours. Secara umum persoalan yang akan diselesaikan pada penelitian Tugas Akhir ini adalah bagaimana cara melakukan komputasi darin suku pertama atau deret dari sebuah Linear Recursive Sequence dengan efisien.
Tugas akhir ini mengulas pendekatan Matrix Exponentiation
dan penggunaan algoritma Gaussian Elimination, yang digunakan untuk menyelesaikan permasalahan mencari jumlah n suku pertama dari Linear Recursive Sequence. Lalu, dengan memanfaatkan salah satu generalisasi dari deret geometri yaitu deret Neumann,permasalahan ini dapat diselesaikan dengan mengkomputasi invers sebuah matriks. Modifikasi Gaussian Elimination dapat menyelesaikan penghitungan invers dari matriks ini dengan cukup
efisien, yaitu dengan kompleksitas O(n).
Dari hasil uji coba pada studi kasus yang diberikan, didapat hasil bahwa algoritma Gaussian Elimination memiliki efisiensi kinerja yang lebih baik dibandingkan dengan pendekatan naive.
Rata-rata waktu hasil uji coba pada Linear Recursive Sequence menggunakan Gaussian Elimination adalah 0, 012 detik. Sementara rata-rata memori hasil uji coba adalah 4, 86 MB
============================================================================================
Linear recursive sequence is one of the important parts
of the mathematics field. Various examples include factorial,
Fibonacci sequence, Lucas sequence, etc. Besides in the field
of mathematics, linear recursive sequence has many benefits in
other fields like in, macroeconomics, digital field, etc. This thesis
can be represented as a Linear Recursive Sequence problem and
found on SPOJ site as 100pct failure in 72 hours problem. By
general the problem to be solved is about how to compute the first n
term or sum of a sequence of a linear recursive sequence efficiently.
This thesis reviewed the Matrix Exponentiation approach
and Gaussian Elimination algorithm that used to solve computation
of the first n term of a Linear Recursive Sequence. Then,
using one of the generalization of geometric series, NeumannSeries,
this problem can be solved by computing the inverse of
a matrix. Modified Gaussian Elimination can solve the computation
of the inverse of this matrix efficiently, with complexity
O
(n).
xi
From the result of testing from given case studies, it turns that
the Gaussian Elimination algorithm has a better performance compared
to the naive approach to solve computation of the first n term
of a Linear Recursive Sequence. The average time result of testing
on Linear Recursive Sequence using the Gaussian Elimination algorithm
is 0.012 second. While the average memory usage result is
4.86 MB
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Uncontrolled Keywords: | Kata Kunci: deret, gaussian elimination, linear recursive sequence,matrix exponentiation |
| Subjects: | Q Science > QA Mathematics > QA9.58 Algorithms |
| Divisions: | Faculty of Information Technology > Informatics Engineering |
| Depositing User: | Fandy Putra Mohammad |
| Date Deposited: | 11 Aug 2020 04:02 |
| Last Modified: | 11 May 2023 05:39 |
| URI: | http://repository.its.ac.id/id/eprint/77434 |
Actions (login required)
 |
View Item |