Logika Informatika : Sifat Kalimat, Pohon Semantik, dan Pengujian 2 Kalimat, beserta Contoh Soal

Struktur Diskrit : Latihan Soal Struktur Diskrit 1

1. Diberikan sebuah string ”makanmalampakaitimun”. Tentukanlah: 

• Proporsi kemunculan masing-masing huruf !
• Kode Huffman untuk setiap karakter !
• Rata-rata bit yang digunakan untuk mengkodekan karakter-karakter tersebut !
• Kodekan string ”paman” menggunakan kode Huffman yang Anda buat !

2. Diketahui daftar 10 orang anak, yaitu: Beri, Jeri, Ceri, Feri, Hari, Geri, Ari, Deri, Eri, Ira. 

• Bangunlah pohon pencarian biner untuk 10 anak tersebut !
• Berikan hasil penelusuran pohon tersebut secara inorder !

3. Perusahaan Womater ingin membuat pipa air di sebuah kompleks sehingga dari sumber yang merupakan titik a dapat mengalirkan air ke seluruh rumah di kompleks tersebut. Perusahaan Womater ingin meminimalkan panjang pipa yang harus dikeluarkan. Tentukan pipa mana saja yang harus dibangun dan panjang minimal yang dibutuhkan jika diketahui peta rumah di kompleks tersebut beserta letak pipa yang dapat dibangun adalah sebagai berikut:

Bobot sisi merupakan panjang pipa yang dibutuhkan untuk menghubungkan dua rumah. Tuliskan langkahlangkah pemilihan sisi dengan lengkap dan jelas !

4. Diketahui L adalah himpunan semua string biner yang jika terdapat pasangan bit 00, maka harus diikuti oleh bit 1 tepat setelah pasangan bit 00 tersebut. 

• Definisikanlah sebuah grammar G yang membangkitkan L ! 
• Gambarkan non-deterministik FSA yang mengenali L !
• Gambarkan deterministik FSA yang mengenali L !
• Nyatakan L dalam ekspresi regular !

5. Sebuah perusahaan pembuat mesin berencana membuat sebuah mesin penjual cemilan. Cemilan yang disediakan ada tiga macam, yaitu kacang seharga 5000 rupiah, biskuit seharga 8000, dan keripik seharga 10000 rupiah. Mesin tersebut hanya dapat menerima uang kertas 2000 rupiah, 5000 rupiah, dan 10000 rupiah. Terdapat empat tombol pada mesin tersebut: Cancel untuk membatalkan pesanan, N untuk memilih kacang, B untuk memilih biskuit, dan C untuk memilih keripik. Terdapat dua lubang pada mesin tersebut, yaitu lubang untuk memasukkan uang kertas dan lubang untuk mengeluarkan cemilan. Dengan menggunakan FSM, rancanglah cara kerja mesin tersebut jika diinginkan: 

• Pada saat awal lubang untuk memasukkan uang tertutup. Lubang akan terbuka setelah pembeli menekan salah satu tombol pilihan cemilan. Lubang akan kembali tertutup jika pembeli telah memasukkan uang lebih besar atau sama dengan harga cemilan yang dipilih. 
• Setelah pembeli memasukkan uang lebih besar atau sama dengan harga cemilan yang dipilih, maka mesin akan mengeluarkan cemilan sesuai pilihan. Mesin tidak akan mengeluarkan uang kembalian meskipun uang yang diterima lebih besar daripada harga cemilan yang dibeli dan mesin akan kembali ke keadaan awal. 
• Jika pembeli menekan tombol Cancel sebelum uang yang dimasukkan lebih dari atau sama dengan harga cemilan yang dipilih maka mesin tidak akan mengeluarkan apapun dan kembali ke keadaan awal.