TUGAS PERTEMUAN 12,13,14

NAMA :

1.  GENIJYANTI WARUWU : 12190279
2. JETA ARIS SURETNO      : 12190241

KELAS : 12.2A.05

MULTIPLE CHOICE     

1. Untuk merepresentasikan graf ada ……..cara

    a. 1 

    b. 2

    c. 3 

    d. 4

     e. 5

2. Dua buah graf sama dengan bentuk yang berbeda

disebut graf…….

    a. Isomorfik

    b. Dual

    c. Euler

    d. Hamilton

    e. Planar

 

3. Untuk menyatakan jumlah wilayah dalam graf

dinotasikan dengan…….

    a. n

    b. f

    c. e

    d. s 

    e. r

4. Lintasan atau sirkuit yang melalui sisi-sisi graf tepat satu

kali disebut…..

    a. Isomorfik

    b. Dual

    c. Planar

    d. Euler

    e. Hamilton

 

5. Graf yang dapat digambarkan pada bidang datar dengan

sisi-sisi tidak saling memotong disebut graf……..

    a. Isomorfik

    b. Dual

    c. Planar

    d. Euler

    e. Hamilton

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.

PERTEMUAN 14

BAHASA FORMAL DAN MESIN STATUS TERHINGGA

MULTIPLE CHOICE  

            1.       suatu bahasa yang harus mengikuti aturan bahasa

pemrograman dan bahasa matematis seperti aljabar

dan logika proposisi disebut bahasa

a.       Formal                                 d Frasa

b.       Natural                                                 e.Automata

c.       Verbal

             2.       Jenis tatabahasa dalam bahasa formal terdiri dari

    a.1

    b. 2

    c. 3

    d. 4

    e. 5

             3.       Level terendah dari hirarki mesin dan bahasa disebut

    a.       Formal                                          d.  Frasa

    b.       Natural                                         e.  Automata terhingga

    c.       Verbal

            4.       Dalam diagram transisi untuk menyatakan string yang

valid telah dikenali ditandai dengan

a.       Busur                                           d. Kategori

b.       Lingkaran ganda                       e. inisiasi

c.       Simbol

            5.       Tokoh penemu mesin Turing adalah

a.       Alan                                               d. James Turing

b.       Automata                                    e. David Turing

c.       Alan Turing