Rahadian, Fandi Akbar (2015) Desain Dan Analisis Algoritma Pemrograman Dinamis Model Tree Pada Penyelesaian Permasalahan SPOJ Klasik Disjoint Subtrees. Undergraduate thesis, Institut Technology Sepuluh Nopember.
Preview |
Text
5111100192-Undergraduate Thesis.pdf - Published Version Download (1MB) | Preview |
Abstract
Diberikan sebuah arbitrary tree dimana setiap vertex pada tree
tersebut memiliki bobot tertentu. Tentukan nilai selisih terbesar
dari dua himpunan vertex, dimana vertex pada himpunan tersebut
tidak dipisahkan oleh suatu vertex yang bukan anggota
himpunannya dan kedua himpunan tidak memiliki vertex yang
sama. Nilai dari suatu himpunan adalah total jumlah bobot
vertex anggotanya.
Pemrograman Dinamis adalah sebuah paradigma untuk
mendapatkan nilai optimal dari beberapa kemungkinan jawaban,
dimana permasalahan tersebut memiliki submasalah tumpang
tindih dan struktur optimal.
Algoritma pemrograman dinamis pada struktur data tree dapat
diimplementasikan dengan beberapa cara, menggunakan
pemrograman dinamis dalam proses penggabungan nilai
submasalah pada children suatu vertex atau dengan
mengkonversi arbitrary tree awal menjadi left child right sibling
tree agar proses penggabunganan nilai submasalah pada
children suatu vertex menjadi lebih sederhana.
Pada penelitian ini didesain dan diimplementasikan solusi untuk
permasalahan yang disampaikan pada paragraf pertama dengan
pendekatan pemrograman dinamis dalam proses penggabungan
nilai submasalah pada children suatu vertex dan pendekatan
mengkonversi arbitrary tree menjadi left child right sibling tree.
viii
Solusi yang dikembangkan berjalan dengan kompleksitas waktu
=========================================================================================================
Given an arbitrary tree where each vertex in the tree has a
certain weight. Determine the value of the largest difference
between the two set of vertices, where vertex in the set is not
separated by a vertex that is not a member its set and the two sets
do not have common vertex. The value of the set is the total
number of vertex weights of its members.
Dynamic programming is a paradigm to gain optimal value from
several possible answers, where the problem has overlapping
subproblems and optimal structure.
Dynamic programming on a tree data structure algorithm can be
implemented in several ways, using dynamic programming in the
process of merging subproblems value in children of each vertex
or to convert the initial tree become left child right sibling tree so
that the process of merging subproblems value in children of each
vertex become simpler.
In this thesis, will be designed and implemented solution to the
problems presented in the first paragraph with a dynamic
programming approach in the process of merging subproblems
value on children and the approach of converting an arbitrary
vertex tree be left child right sibling tree.
x
The time complexity of the solution is
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 006.746 Rah d |
| Uncontrolled Keywords: | Pemrograman Dinamis, Left Child Right Sibling Tree. |
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science. EDP T Technology > T Technology (General) > T57.5 Data Processing |
| Divisions: | Faculty of Information and Communication Technology > Informatics > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Mr. Tondo Indra Nyata |
| Date Deposited: | 15 May 2019 03:33 |
| Last Modified: | 15 May 2019 03:33 |
| URI: | http://repository.its.ac.id/id/eprint/63030 |
Actions (login required)
 |
View Item |