Akhyar, Miftakhul (2018) Desain dan Analisis Penerapan Algoritma Mo dan Struktur Data Segment Tree pada Studi Kasus Permasalahan SPOJ Klasik DCEPCA09-MMM. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05111440000143-Undergraduate_Thesis.pdf - Accepted Version Download (6MB) | Preview |
Abstract
Perkembangan teknologi informasi dalam beberapa dekade terakhir sangat pesat, terutama dalam hal proses komputasi yang memungkinkan pengambilan keputusan dapat dilakukan dengan cepat dan akurat. Salah satu bidang permasalahan yang menarik untuk dieksplorasi dalam bidang komputasi adalah query processing.
Query processing adalah suatu permasalahan untuk memproses beberapa query dari suatu data dengan indeks yang dinamis sesuai dengan kriteria masing-masing query. Tujuan dari query processing adalah menyelesaikan semua query dengan waktu yang efisien dan biaya komputasi yang rendah oleh karena itu diperlukan algoritma yang optimal untuk mencapai hal tersebut. Terdapat dua pendekatan pada metode query processing yaitu online query dan offline query. Pada online query setiap masukan query akan diproses secara langsung. Sedangkan pada offline query, query akan terlebih dahulu disimpan dan diurutkan dengan fungsi tertentu kemudian diproses dan akan menampilkan hasil sebanyak jumlah query yang ada.
Topik Tugas Akhir ini akan mengangkat permasalahan yang terdapat pada Online Judge SPOJ dengan kode DCEPCA09. Pada permasalahan ini, diberikan sebuah array bilangan dengan panjang N dan dua set bilangan i dan j sebanyak Q. Bilangan i dan j merepresentasikan indeks yang ada pada array. Dari setiap interval array indeks i dan j diminta untuk mencari nilai mean, median dan mode. Pada permasalahan ini memiliki tantangan untuk merancang algoritma yang dapat melakukan pemrosesan tiap case secara optimal pada array yang dinamis karena array yang diproses untuk setiap case berbeda sesuai dengan indeks i dan j dengan batasan yang sudah ditentukan. Dengan batasan waktu selama 0.5 detik, nilai N antara 2 sampai 10^4 dan jumlah query sampai 10^4 maka apabila dikerjakan dengan cara naif akan menghasilkan TLE.
Pada Tugas Akhir ini akan diimplementasikan Algoritma Mo yang merupakan algoritma offline query dengan menggunakan struktur data segment tree. Segment tree digunakan dengan memanfaatkan nilai agregasi untuk menyelesaikan permasalahan pada Tugas Akhir ini yaitu untuk menemukan nilai mean, median dan mode. Hasil dari Tugas Akhir ini diharapkan dapat mendapatkan implementasi algoritma dan struktur data yang tepat untuk memecahkan permasalahan di atas secara optimal dan diharapkan dapat memberikan kontribusi pada perkembangan ilmu pengetahuan dan teknologi informasi.
==================================================================================================================
The development of information technology in recent decades is very rapid, especially in terms of computing processes that enable decision making to be done quickly and accurately. One of the most interesting issues to explore in computing is query processing.
Query processing is a problem for processing multiple queries from a data with a dynamic index according to the criteria of each query. The purpose of query processing is to solve all queries with efficient time and low computational cost and therefore an optimal algorithm is needed to achieve this. There are two approaches to query processing methods: online query and offline query. In the online query each input query will be processed directly. While in the offline query, the query will be first stored and sorted with a certain function then processed and display the results as much as the number of existing queries.
This final project topic will use the problems contained in Online Judge SPOJ with DCEPCA09 code. In this problem, an array of numbers of length N and two sets of numbers i and j of Q are given. The numbers i and j represent the indices in the array. From each array interval between indices i and j are required to find the mean, median and mode values. On this case it has a challenge to design algorithms that can optimally process each case on a dynamic array, because the array processed for each case is different according to index i and j with the limit set by the problem setter. With time limits for 0.5 seconds, the length of array(N) up to 10^4 and the number of queries(Q) up to 10^4 if the problem processed naively will result in TLE.
This Final Project will be implemented using Mo's algorithm which is an offline query algorithm by using data structure segment tree. Segment tree is used by utilizing the aggregation value to solve the problem in this Final Project to find mean, median and mode. The results of this Final Project is expected to determine the implementation of appropriate algorithms and data structure to solve the above problems optimally and can contribute to the development of science and information technology.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Uncontrolled Keywords: | range query, offline query, algortima mo, segment tree |
| Subjects: | T Technology > T Technology (General) > T58.5 Information technology. IT--Auditing |
| Divisions: | Faculty of Information and Communication Technology > Informatics > 55201-(S1) Undergraduate Thesis |
| Depositing User: | MIFTAKHUL AKHYAR |
| Date Deposited: | 23 Jun 2021 08:05 |
| Last Modified: | 23 Jun 2021 08:05 |
| URI: | http://repository.its.ac.id/id/eprint/54760 |
Actions (login required)
 |
View Item |