UTS Diskrit

Berdo’alah terlebih dahulu agar anda berhasil menyelesaikan ujian ini dengan baik.

Kombinatorial

(Gunakan notasi P(n, r) untuk permutasi dan C(n, r) untuk kombinasi)

1.      Tentukan banyaknya cara agar 4 buku matematika, 3 buku sejarah, 3 buku kimia, dan 2 buku sosiologi dapat disusun sedemikian sehingga

(a)        semua buku yang topiknya sama letaknya bersebelahan,

(b)        urutan buku dalam susunan bebas.                                                        (5+5)

2.      Tentukan banyaknya “kata” yang terbentuk dari huruf-huruf dalam kata “SELEBES” jika:

(a)        setiap “kata” berawal dengan huruf E dan berakhir dengan E,

(b)        pada setiap “kata”, tiga huruf E berdampingan satu sama lain.         (5+5)

3.      Sebuah klub mobil antik beranggotakan 6 orang pria dan 5 orang wanita. Mereka akan membentuk panitia yang terdiri dari lima orang. Berapa banyak jumlah panitia yang dapat dibentuk jika panitianya terdiri dari paling sedikit satu pria dan satu wanita.                                                                              (10)

4.      Palindrom adalah barisan karakter (huruf atau angka) yang bila dibaca dari depan atau dari belakang adalah sama. Contoh: KATAK, MALAM, 21477412, 36963. Untuk soal ini kita hanya meninjau palindrom yang dibentuk dari barisan angka. Berapa banyak bilangan palindrom 9-angka yang dapat dibentuk dari angka 0, 1, …, 9 dengan ketentuan tidak boleh ada pengulangan angka pada setengah bagian (misalnya, 366191663 tidak dibenarkan karena 6 dipakai 2 kali)?                                                                                                    (10)

5.      Dari sejumlah besar CD (compact disc) di dalam kotak yang berisi program-program aplikasi A, B, C, D,  dan E, berapa banyak cara 10 CD dapat diambil?

(10)

6.      Ada 10 soal (diberi nomor 1 sampai 10) di dalam ujian Matematika Diskrit. Berapa banyak cara pemberian nilai (bilangan bulat) pada setiap soal jika jumlah nilai keseluruhan soal adalah 100 dengan ketentuan setiap soal bernomor genap mempunyai nilai paling sedikit 5 dan soal bernomor ganjil mempunyai nilai paling sedikit 4.  (Khusus untuk soal ini, nyatakan jawaban akhir anda dalam C(a, b) saja, tidak perlu dihitung nilainya)                (10)

7.  Gunakan Teorema Binomial untuk membuktikan bahwa

 _n

å 2^{n – k}  (-1)^k C(n, k) = 1                                                                   (5)

                       ^k=0

Aljabar Boolean

8.   Buktikan secara aljabar bahwa dual dari exclusive-or (XOR), f = x Å y, sama dengan komplemennya.                                                                               (10)

9.  Gunakan peta Karnaugh untuk menyederhanakan fungsi

           

f (w, x, y, y) = (w + x + y’) (x’ + y’) (w’ + y + z’ )(y)

Hasil penyederhanaan dalam bentuk POS dan SOP.                                                (10)

10. Rancanglah rangkaian logika untuk menghitung koin uang logam yang dimasukkan pada pengumpul bea otomatis sebagai pembayar jasa tol. Mesin penghitung ditempatkan pada gerbang tol. Tarif tol adalah 15 sen. Mesin hanya dapat menerima koin 5 sen dan koin 10 sen. Bila mesin telah menerima sejumlah koin senilai 15 sen, maka lampu hijau menyala (artinya kendaraan boleh melewat gerbang tol), dan jika belum 15 sen, lampu merah  tetap menyala (artinya belum boleh melewati gerbang tol). Gambarkan rangkaian logika yang dimaksud!                                                                   (15)

Catatan: Pembayaran dapat dilakukan dengan koin 5 sen saja atau koin 10 sen saja atau gabungan keduanya. Karena biaya tol 15 sen, maka jumlah koin 5 sen yang  digunakan maksimal 3  buah (= 15 sen), jumlah koin 10 sen yang digunakan maksimal 2 buah (= 20 sen).  Di luar jumlah koin itu, keluaran mesin tidak penting nilainya (kondisi don’t care). Anda terlebih dahulu harus memikirkan berapa banyak peubah (variable) Boolean yang dibutuhkan.

SELAMAT BERPIKIR DAN BEKERJA