Latihan Soal :
1. Algoritma Prim
2. Algoritma Kruskal
Termologi Pohon
1. Anak Dan Orang Tua
Jawab :
2,3, Dan 4 Adalah Anak Dari Simpul 1, Dimana 1 Adalah Orang Tua Mereka. 5 Dan 6 Adalah Anak Dari Simpul 7, Dimana 7 Adalah Orang Tua Mereka
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.
UpaPohon T' = (V',E') dengan B sebagai akarnya.
Derajat maksimum dari sebuah simpul merupakan derajat pohon itu sendiri. Pohon pada Gambar berderajat 3, karena derajat tertinggi dari seluruh simpulnya adalah 3.
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 :
Contoh:
+MN
– +MNO
* + MN – NO.
a. Pohon d. Level
b. Binary e. Anak
c. Akar
2. Sisi pada pohon rentang disebut dengan……
a. Tali hubung d. Rank
b. Cabang e. Upa Pohon
c. akar
3.Metode yang digunakan untuk menyelesaikan pohon rentang minimum adalah…….
a. Algoritma Prim d. a dan c benar
b. Algoritma Kruskal e. a dan b benar
c. Traveling Salesman
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
1. Algoritma Prim
2. Algoritma Kruskal
Termologi Pohon
1. Anak Dan Orang Tua
Jawab :
2,3, Dan 4 Adalah Anak Dari Simpul 1, Dimana 1 Adalah Orang Tua Mereka. 5 Dan 6 Adalah Anak Dari Simpul 7, Dimana 7 Adalah Orang Tua Mereka
2. Lintasan (Path)
Lintasan Dari Simpul v1 Ke v11 Adalah Runtutan Simpul v1, v2,...,v11 Sedemikian Sehingga 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, Makan 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 Berorang Tua Yang Sama Adalah Saudara Sekandung.
5. Upa Pohon (Sub Tree)
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.
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.
6. Derajat (Degree)
Jumlah Upa pohon (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.
7. Daun (Leaf)
Simpul Yang Berderajat Nol (Tidak Mempunyai Anak)
Simpul 8, 9, 10, 6, 2, 12, Dan 13 Adalah Daun.
8. Simpul Dalam (Internal Nodes)
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 Adalah = 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 :
11. Pohon Ekspresi (Expression Tree)
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
Nilai Evaluasi Dari Pohon Ekspresi Adalah 50.
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)
Kode Huffman 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.
Multipe Choice
1. Graf tak berarah terhubung yang tidak mengandung sirkuit disebut……. a. Pohon d. Level
b. Binary e. Anak
c. Akar
2. Sisi pada pohon rentang disebut dengan……
a. Tali hubung d. Rank
b. Cabang e. Upa Pohon
c. akar
3.Metode yang digunakan untuk menyelesaikan pohon rentang minimum adalah…….
a. Algoritma Prim d. a dan c benar
b. Algoritma Kruskal e. a dan b benar
c. Traveling Salesman
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
Komentar
Posting Komentar