dimas hirda pratama, dimas (2018) Penerapan Konsep Dsu On Tree Dan Struktur Data Segment Tree Pada Rancang Algoritma: Studi Kasus Spoj Klasik Lis And Tree. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
buku.pdf - Accepted Version Download (10MB) | Preview |
Abstract
Permasalahan LIS and TREE merupakan sebuah permasalahan
yang melibatkan sebuah struktur data tree. Dimana pada tree
tersebut akan dicari LIS terpanjang dari seluruh simple path
yang ada.
Untuk menangani berbagai permasalahan pada
permasalahan tersebut dibutuhkan struktur data yang mampu
mendukung operasi-operasi tersebut dengan efisien.
Pada Tugas Akhir ini akan dirancang penyelesaian permasalahan
LIS and TREE antara lain operasi pencarian nilai LIS pada node
dan subtree saat ini, operasi update nilai LIS pada node dan subtree
saat ini dan menggabungkan serta memindahkan nilai pada dua
subtree yang berbeda. Struktur data klasik yang biasa digunakan
dalam penyelesaian permasalahan ini merupakan salah satu jenis
stuktur data Tree yaitu Segment Tree dengan menggabungkan
konsep Disjoint Set Union.
Pada Tugas Akhir ini digunakan struktur data Segment Tree dan
konsep Disjoint Set Union untuk menyelesaikan operasi-operasi
tersebut
===========================================================
LIS and TREE is a problem which involves tree data structure.
From that tree a LIS should be found from every simple path that
exist. To handle various problem, an efficient data structure is
needed to support the operations.
This undergraduate thesis will be designed problem solving for
LIS and TREE such as operation to find LIS value in a subtree and
node, operation to update value of LIS in a subtree and node, and
also combine and transfer value of LIS between different subtree
and node. Well known data structures, e.g tree specifically segment
tree with combination of Disjoint Set Union concept is able to
answer the problem efficiently.
In this undergraduate thesis Segment Tree data structure and
Disjoint Set Union concept will be used to solve those operations.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Uncontrolled Keywords: | Disjoint Set Union on Tree, Segment Tree, Longest Increasing Subsequence |
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science. EDP Q Science > QA Mathematics > QA76.6 Computer programming. Q Science > QA Mathematics > QA76.9 Computer algorithms. Virtual Reality. Computer simulation. Q Science > QA Mathematics > QA9.58 Algorithms T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5105.546 Computer algorithms |
| Divisions: | Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Dimas Hirda Pratama |
| Date Deposited: | 25 Jun 2021 10:05 |
| Last Modified: | 25 Jun 2021 10:05 |
| URI: | http://repository.its.ac.id/id/eprint/55374 |
Actions (login required)
 |
View Item |