Reynaldy saputra - Dennis Manthiaha

1.      Suatu Bahasa yang harus mengikuti aturan bahasa pemrograman dan bahasa matematis Seperti aljabar dan loigika proposisi disebut bahasa .... a.      Formal              d. Frasa b.      Natural             e. Automata c.      Verbal Jawab : A 2.      Jenis tatabahasa dalam bahasa formal terdiri dari .... a.      1       b. 2     c. 3       d. 4      e. 5 Jawab : C 3.      Level Terendah dari hirarki mesin dan bahasa disebut ..... a.      Formal                  d. Frasa b.      Natural                  e. Automata terhingga c.      Verbal Jawab :  E 4.      Dalam diagram transisi untuk menyatakan string yang valid telah dikenali ditandai dengan..... a.      Busur                                 d. kategori b.      Lingkaran ganda               e. inisiasi c.      Simbol Jawab : C 5.      Tokoh penemu mesin turing adalah.... a.      Alan                       d. James Turing b.      Automata              e. David Turing c.     

Buat pohon rentang minimum berdasarkan a.      Algoritma prim   b. Algoritma kruskal B.Terminologi pada pohon 1.      Anak dan orang tua Jawab : b dan c adalah anak dari simpul a, dimana a adalah orang Tua mereka 2.      Lintasan (path) Jawab : Lintasan a ke j adalah a,b,d,j 3.      Keturunan (descedant) dan leluhur (ancestor) Jawab : b adalah leluhur dari j dan j adalah keturunan dari b 4.      saudara kandung jawab : simpul g dan h adalah saudara kandung dengan orang tua yang sama yaitu simpul f 5.      Upa Pohon Jawab : Upapohon T’ = ( V’,E’ ) dengan b sebagai akarnya 6.      Derajat (degree) Jawab : Pohon pada gambar berderajat 2, karena derajat tertinggi dari seluruhnya adalah 2 7.      Daun (leaf) Jawab : J,g,h dan i adalah Daun 8.      Simpul Dalam (internal nodes) Jawab : Simpul b,d,f,c dan e pada gambar adalah simpul dalam 9.      Tinggi (height) atau kedalaman (depth) Jawab : Tinggi atau kedalaman pada poho

1.      Untuk Mereprentasikan graf ada ...... cara a.1        b.2         c.3        d.4         e.5 Jawab : C 2.      Dua buah graf sama dengan bentuk yang berbeda disebut graf.... a.      Isomorfik                               d. Hamilton b.      Dual                                    e. Planar c.      Euler Jawab : A 3.      Untuk menyatakan jumlah wilayah dalam graf dinotasikan dengan..... a.      n       b. f         c. e        d. s        e. r Jawab : B 4.      Lintasan atau sirkuit yang melalui sisi graf tepat satu kali disebut ... a.      Isomorfik                           d. Euler b.      Dual                                   e. Hamilton c.      Planar Jawab : D 5.      Graf yang digambarkan pada bidang datar dengan sisi-sisi tidak saling Memotong disebut graf .... a.      Isomorfik                           d. euler b.      Dual                                   e. Hamilton c.      Planar Jawab : C

1.Himpunan simpul-simpul yang dihubungkan oleh sisi-sisi disebut....    a. Graf                                 d. edges    b. Pohon                             e. node    c. vertex    Jawab : D 2.Graf yang tidak mengandung gelang maupun sisi ganda disebut graf....    a. Berhingga                      d. Tak sederhana    b. Sederhana                    e. Tak berhingga    c. Berarah    Jawab : B 3. Dalam penguijian program kita menerapkan jenis graf...     a. Sederhana                                           d. Tak Sederhana     b. Tak berarah                                         e. Tak Berhinggga     c. Berarah     Jawab : C 4. Lintasan elementer dengan simpul awal sama dengan simpul akhir disebut....     a. Derajat                                      d. Siklus     b. Terhubung                                e. Pohon     c. Simpul terpencil     Jawab : D 5. Jumlah sisi pada graf lengkap dirumuskan dengan....     a. n-1              

1.Langkah-langkah logis untuk menyelesaikan masalah disebut dengan......    a. Algoritma                       d. Fungsi    b. Notasi O-besar             e. Relasi    c. Rekurensi    jawab : A 2. Permasalahan pencarian biner akan optimal jka menggunakan algoritma waktu....     a. O(1)                                d. O(n log n)     b. O(n!)                               e. O(n)     c. O(log n)     Jawab : C 3. Jenis cara pencarian data ada.....     a. 1      b. 2     c. 4      d. 5      e. 6     Jawab : B 4. Data  27   80   02   46   16   12   50      Jika diurutkan dengan metode seleksi maka pada langkah ke-3 diperoleh urutan...      a. 02   80    27    46    16    12    50      b. 02   12    27    46    16    80    50      c. 02   12    16    46     27   80    50          d. 02   12    16    27    46    80    50      e. 02   12    16    27    46    80    50      jawab : C 5. Kemampuan memanggil dirinya sendiri dengan paramet

A.Latihan Soal dan konversi dalam bentuk kanonik 1.Nyatakan fungsi Boolean f(x,y,z) = x + y’z dalam SOP dan POS Jawaban : a)SOP : mk harus melengkapi dahulu literal untuk setiap suku agar jumlahnya sama x = x(y + y’)    = xy +  xy’    = xy (z + z’) + xy’(z + z’)    = xyz + xyz’ + xy’z + xy’z’       Y’z = y’z (x + x’)    = xy’z + x’y’z Jadi f(x, y, z) = x + y’z                       = xyz + xyz’ + xy’z + xy’z’ + xy’z + x’y’z                       = x’y’z + xy’z’ + xy’z + xyz’ + xyz Atau f(x, y, z) = m1 + m4 + m5 = m6 = m7 = S (1,4,5,6,7) b) POS            f(x, y, z) = x + y’z                          = (x + y’)(x + z)            x + y’ = x + y’ + zz’            = (x + y’ + z)(x + y’ + z’)                x + z = x + z + yy’                        = (x + y + z)(x + y’ + z)           Jadi, f(x, y, z) = (x + y’ + z)(x + y’ + z’)(x + y + z)(x + y’ + z)                                  = (x + y + z)(x + y’ + z)(x + y’ + z’)           atau f(x, y