Pertemuan 13 MATDIS

TUGAS PERTEMUAN 13 POHON TREE MULTIPLE CHOICE 1.Graf tak berarah terhubung yang tidak mengandung sirkuit disebut a. Pohon b. Binary c. Akar d. Level e. Anak 2. Sisi pada pohon rentang disebut dengan a. Tali hubung b. Cabang c. akar d. Rank e. Upapohon 3. Metode yang digunakan untuk menyelesaikan pohon rentang minimum adalah a. Algoritma Prim b. Algoritma Kruskal c. Traveling Salesman d. a dan c benar e. a dan b benar 4. Di bawah ini yang bukan terminologi pohon adalah…… a . Anak d. Derajat b. Lintasan e. Daun c. Sirkuit 5. Pohon biner dengan daun berupa operand dan simpul dalam berupa operator disebut dengan pohon……… a. Keputusan d. Ekspresi b. Huffman e. Pencarian biner c. Prefiks ESSAY : 1. Algoritma Prim jawaban : 2. Algoritma Kruskal Jawaban : Termologi Pada Pohon : 1. Anak dan Orang tua Jawab: 2,3 dan 4 adalah anak dari simpul 1, dmn 1 adalah orang tua mereka. 5 dan 6 adalah anak dari simpul 7, dmn 7 adalah orang tua mereka 2. Lintasan (path) Lintasan dari simpul v1 ke v11, adalah runtunan simpul v1, v2,…,v11 sedemikian sehingga v9 orang tua dari v9+1 untuk 1<9<11 contoh lintasan dari 1 ke 8 adalah 1, 2, 5, 8 dengan panjang lintasan adalah jumlah sisi yang dilalui dalam suatu lintasan k-1 ada 3. 3. Keturunan (descendant) dan leluhur (ancestor) Jika terdapat lintasan dari simpul X ke Y di dalam pohon , maka X adalah leluhur Y dan Y adalah keturunan X. b adalah leluhur simpul h. Dan h adalah keturunan dari b 4. Saudara kandung (sibling) Simpul yang berorangtua yang sama adalah saudara sekandung. Simpul 8,9 dan 10 adalah saudara kandung dgn orang tua yg sama yaitu simpul 5, sedangkan simpul 7 bukan saudara kandung 5, karena orangtua mereka berbeda 5. Upa pohon (subtree) Misalkan X adalah simpul di dalam pohon T. Yang dimaksud dengan upapohon dengan X sebagai akarnya ialah upagraf T’ = (V’,E’) sedemikian sehingga V’ mengandung X dan semua keturunannya dan E’ mengandung sisi-sisi dalam semua lintasan yang berasal dari X. Contoh T'=(V',E') adalah upahan pohon dari pada gambar dengan V' = {b,e,f,h,i,j} dan E'= {(2,5), (2,6),(2,8),(2,9),(2,10) dan b adalah simpul akarnya. Terdapat banyak upapohon T. dengan perngertian diatas jika X, adalah simpul, maka tiap-tiap upapohon dari x disebut anak, dan x adalah orang tua setiap akar pohon UpaPohon T' = (V',E') dengan b sebagai akarnya 6. Derajat (degree) Jumlah upapohon (atau jumlah anak) pada simpul tersebut. Pada gambar dibawah ini , derajat 1 adalah 3, derajat 2 adalah 2, derajat 4 adalah 1 dan derajat 3 adalah 0. Jadi, derajat yang dimaksudkan di sini adalah derajat-keluar. Derajat maksimum dari sebuah simpul merupakan derajat pohon itu sendiri. Pohon pada Gambar berderajat 3, karena derajat tertinggi dari seluruh simpulnya adalah 3. 7. Daun (leaf) Simpul yang berderajat nol (atau tidak mempunyai anak) Simpul 8, 9, 10, 6, 2, l2, dan 13 adalah daun. 8. Simpul Dalam (internal nodes) Simpul yang mempunyai anak Simpul 2, 4, 5, 7, dan 11 pada gambar adalah simpul dalam 9. Simpul Dalam (internal nodes) Akar mempunyai aras = 0, sedangkan aras simpul lainnya = 1 + panjang lintasan dari akar ke simpul tersebut. 10. Tinggi (height) atau kedalaman (depth) Aras maksimum dari suatu pohon dapat dikatakan tinggi pohon adalah panjang maksimum lintasan dari akar ke daun. Contoh : Tinggi atau kedalaman pad pohon diatas adalah 4 11. Pohon ekspresi (expression tree) Contoh : Gambar dibawah ini, ekspresi dari (M+N)*(O/(P+Q)) dinyatakan dalam pohon biner. Dimana Daun menyatakan operand m,n,o,p,q, dan simpul menyatakan operator +,* dan / Contoh: Mencari nilai Evaluasi dari pohon ekspresi Contoh: Mencari nilai Evaluasi dari pohon ekspresi Jadi nilai evaluasi dari pohon ekspresi adalah 14. 12. Pohon keputusan (decision tree) Contoh : Tiga buah bilangan 1, 2, dan 3. pohon keputusan untuk persoalan ini ditunjukkan pada gambar berikut 13. Kode Huffman (Huffman code) adalah pengkodean sebuah string. Contoh : mengkodekan sebuah string “AABCABC”. Dalam kode ASCII string 7 huruf (AABCABC) butuh representasi 7 × 8 bit = 56 bit (7 byte), sebagai berikut: A = 01000001 A = 01000001 B = 01000010 C = 01000011 A = 01000001 B = 01000010 C = 01000011 • Pertama kali akan menghitung frekuensi kemunculan dari setiap karakater. • String: AABCABC | Simbol | Frekuensi | | A | 3 | | B | 2 | | C | 2 | Penyusunan model pohon Huffman dalam bentuk tabel : 14. Kode Prefiks (Prefix code) Prefix adalah metode penulisan dengan meletakkan operator di depan operand dan tanpa menuliskan tanda kurung. Contoh: +MN – +MNO * + MN – NO.