Desain Dan Analisis Algoritma Pemrograman Dinamis Model Tree Pada Penyelesaian Permasalahan SPOJ Klasik Disjoint Subtrees

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.

[img] Text
5111100192-Undergraduate Thesis.pdf - Published Version

Download (1MB)

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 > (S1) Undergraduate Theses
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 View Item