Penerapan Konsep Dsu On Tree Dan Struktur Data Segment Tree Pada Rancang Algoritma: Studi Kasus Spoj Klasik Lis And Tree

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.

This is the latest version of this item.

[img]
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: https://repository.its.ac.id/id/eprint/55374

Available Versions of this Item

  • Penerapan Konsep Dsu On Tree Dan Struktur Data Segment Tree Pada Rancang Algoritma: Studi Kasus Spoj Klasik Lis And Tree. (deposited 25 Jun 2021 10:05) [Currently Displayed]

Actions (login required)

View Item View Item