Tim Penyusun Bundel Soal Elektroteknik Semester 3 Kementerian Kesejahteraan Anggota Kementerian Kewirausahaan
Bundel Soal Elektroteknik Semester 3 | Tahun 2013/2014 tambahan Matematika Diskrit (ET 2012)
DAFTAR ISI Daftar Isi ......................................................................................................................................................... 2 Matematika Diskrit ...................................................................................................................................... 245 Soal ..................................................................................................................................................................... 246 UTS - 2012/2013 ............................................................................................................................................. 246 UTS - 2010/2011 ............................................................................................................................................. 248 UAS - 2012/2013 ............................................................................................................................................ 250 UAS - 2011/2012 ............................................................................................................................................ 252 Solusi .................................................................................................................................................................. 254 UTS - 2012/2013 ............................................................................................................................................. 254 UAS - 2012/2013 ............................................................................................................................................ 261
2
Bundel Soal Elektroteknik >> Semester 3 - 2013/2014 Kementerian Kesejahteraan Anggota - Kementerian Kewirausahaan >> Himpunan Mahasiswa Elektroteknik ITB
ET2001 MATEMATIKA DISKRIT khusus untuk jurusan Teknik Telekomunikasi
SOAL UTS - 2012/2013 Soal Nomor 1 a. Periksa apakah implikasi ini tautology : [(
)
(
) (
)]
[
(
)]
b. Nyatakanlah bagian yang diarsir dari diagram Venn berikut dalam bentuk operasi Set!
A
B
C
Soal Nomor 2 a. Berikan estimasi big-O terbaik dari fungsi berikut ini ( b. Untuk ( )
(
)(
(√
)
)
)⁄ dari R ke R. Apakah ( ) suatu fungsi? Kalau ya, bijektifkah? Apakah ( ) punya
invers? Jika ya, tentukan
( )
Soal Nomor 3 Tentukan suku-suku deret berikut a. b. c.
Soal Nomor 4 Selesaikan: a.
246
Tentukan:
Bundel Soal Elektroteknik >> Semester 3 - 2013/2014 Kementerian Kesejahteraan Anggota - Kementerian Kewirausahaan >> Himpunan Mahasiswa Elektroteknik ITB
∑ ∑(
b.
)
Tentukan: ∑ ∑(
c.
)
Tunjukkan apakah kelompok bilangan bulat berikut prima secara relative berpasang (pairwise relatively prime) : (12, 17, 31, 37), (22, 212, 754)
Soal Nomor 5 a.
Melalui metode induksi buktikan, (
b.
Tentukan koefisien suku
c.
Tentukan koefisien suku
)
(
dalam persamaan ( dalam persamaan (
)
(
)
) )
Soal Nomor 6 Dengan menggunakan fungsi deskripsi ( )
(
)
, translasikan EKSUSMIEAPA.
Soal Nomor 7 Suatu dadu octahedral memiliki 8 buah sisi. Setiap sisi diberi nomor dari 1 sampai dengan 8. Diketahui bahwa dadu ini bersifat bias, dimana nomor mata dadu ganjil pada octahedron memiliki peluang muncul 2 kali dibandingkan dengan nomor mata datu genap, tentukan: a. b.
Nilai harap (expectation value) dari nomor dadu yang muncul Variansi dari nomor dadu yang muncul
Soal Nomor 8 a.
Diketahui ( )
dan ( )
b. c.
Diketahui ( ) dan ( ) Untuk X bilangan integer dan
. Tentukan (
) ( ) . Tentukan ( , tentukan himpunan solusi dari kongruensi (
Matematika Diskrit Soal >> UTS - 2012/2013
) ( )
)
(
)
247
UTS - 2010/2011 Soal Nomor 1 Diketahui U 0,1,2,4,5,6,7,8,9. A 2,4,6,8. B 2,4,5,9. C x Z x 2 16. D 1,7,8 B A ,
A B ,
B A B C C ,
a.
Tentukanlah:
b.
Gambarkanlah masing-masing dari Venn diagramnya
A B ,
C D
Soal Nomor 2 Tentukan
2150,1258 10 16 b. 710228 : 768 8 c. 2578 778 8 a.
Soal Nomor 3 Periksalah apakah implikasi berikut ini adalah tautologi, kontradiksi, atau bukan keduanya:
p q q r r q r r q r q r p r Soal Nomor 4 Tentukan nilai berikut ini:
a.
0.5 0.5 0.5 0.5 5 2
b.
3k 2 2 j 3 5 7
4
j 2 k 1
Soal Nomor 5 Tentukan koefisien suku a.
X101 Y99 dalam persamaan 2 X 3Y 200
b.
X9 dalam persamaan 2 X 19
Soal Nomor 6 Data yang dienkripsi dengan chirp f p 7p 3mod26 , dikirimkan berbentuk ELUS WITIKIRP. Tentukan data yang diterima setelah dideskripsikan.
248
Bundel Soal Elektroteknik >> Semester 3 - 2013/2014 Kementerian Kesejahteraan Anggota - Kementerian Kewirausahaan >> Himpunan Mahasiswa Elektroteknik ITB
Soal Nomor 7 Tentukan gcd dan lcm dari pasangan bilangan berikut: a. b.
(1529 , 14039) (1111 , 111111)
Soal Nomor 8 Untuk deret bilangan berikut, tentukan bentuk formulanya. a. b. c.
1, 5, 5, 9, 9, 13, 13, 17, 17, 21, .... 2, 9, 20, 35, 54, 77, .... 4, 8, 18, 44, 114, 308, ....
Soal Nomor 9 Perhatikan matrik zero-one berikut:
0 0 A 1 0
1
0
0
1
1
0
0
1
0 1 0 0
AK 4
0 1 1 1
1
1
0
1
1
0
1
1
1 1 . 1 0
Tentukan a.
A AK4
b.
A 3 AK 4 2
Soal Nomor 9 Buktikan bahwa untuk n ≥ 1: a.
1 1!2 2! n n! n 1!1
b.
n 3 n 13 n 23 dapat dibagi dengan 9.
Matematika Diskrit Soal >> UTS - 2010/2011
249
UAS - 2012/2013 Soal Nomor 1 (bobot 3x soal nomor lainnya) Dari graph berbobot berikut, tentukanlah: a) b) c) d) e) f) g) h) i) j)
Lintasan dan sirkit Hamilton (jika ada) Lintasan dan sirkit Euler (jika ada) Solusi dari ‘traveling salesman problem’ Lintasan terpendek dari a ke z Tentukan ‘chromatic number’-nya Apakah graph tersebut ‘planar’ Tentukan ‘incidence matrix’-nya Tentukan ‘adjacency matrix’-nya Minimum spanning tree Periksa apakah graph tersebut bipartite
Soal Nomor 2 (bobot 2x soal nomor lainnya) Diketahui Poset ({2, 3, 4, 5, 8, 9, 10, 15, 18, 24, 36, 45, 60}, |). Tentukan: a. b. c. d. e. f. g. h. i. j.
Diagram Hasse dari Poset tersebut Elemen-elemen maksimal Elemen-elemen minimal Greatest elemen (bila ada) Least elemen (bila ada) Semua upper bounds dari {3, 5} LUB dari {3, 5} (bila ada) Semua lower bounds dari {15, 45}, dan GLB dari {15, 45} (bila ada) Periksa apakah Poset tersebut Lattice
Soal Nomor 3 Diketahui A = {1, 2, 3, 4} adalah set, dan R relasi pada A yang dinyatakan oleh matriks relasi sbb. MR = [ ]
1
0
1
1
1
1
1
0
0
0
0
1
0
1
0
0
Tentukan : a. Gambarkan representasi R dalam bentuk graph b. Tentukan transitive closure dari R
250
Bundel Soal Elektroteknik >> Semester 3 - 2013/2014 Kementerian Kesejahteraan Anggota - Kementerian Kewirausahaan >> Himpunan Mahasiswa Elektroteknik ITB
c. Periksalah apakah relasi tersebut termasuk kelas setara (equivalent class)
Soal Nomor 4 Gunakan metoda Backtracking untuk menyelesaikan masalah n-queen, dengan n = 7
Soal Nomor 5 Suatu system mempunyai sirkit dengan probabilitas keberhasilan dari masing-masing elemennya sebagai berikut ini:
Tentukan berapa probabilitas bahwa seluruh system akan bekerja dengan baik!
Soal Nomor 6 a) Bentuklah pohon pengkodean Huffman (Huffman Coding Tree) untuk mengkodekan string berikut ini : mencontekadalahtermasukdalamperbuatankriminal b) Berapa bit diperlukan untuk merepresentasikan seluruh string tersebut dalam kode dengan panjang variable (Variable-length Code)? Bandingkan jika dengan menggunakan kode dengan panjang yang tetap (fixed-length Code)!
Soal Nomor 7 Selidiki dan analisis, apakah pasangan graph berikut ini isomorphic?
Matematika Diskrit Soal >> UAS - 2012/2013
251
UAS - 2011/2012 Soal Nomor 1 bobotnya 3 kali soal nomor yang lainnya Soal 1 m
Dari graph berbobot berikut, tentukanlah: a. b. c. d. e. f. g. h. i. j.
Lintasan dan sirkit Hamilton (jika ada) Lintasan dan sirkit Euler (jika ada) Solusi dari “traveling salesman problem” Lintasan terpendek dari a ke z Tentukan “chromatic number”-nya Apakah graph tersebut “planar”? Representasi dalam “incidence matrix”-nya Representasi dalam “incidence matrix”-nya Minimum spanning tree dengan algoritma Prim Minimum spanning tree dengan algoritma Kruskal
4
b
4
f
1
j
3
n
5
z
7
h
9
8
7
5
k
7
o
7
5
l
9
d
2
5
6 a
6
g
6
7
i
c
6
4 e
8
8
Soal 2 Hitunglah berapa banyak bit string sepanjang 9 dijit yang berawal dengan 10 atau berakhir dengan 01 tapi tidak keduanya (tidak berawal dengan 10 dan berakhir 01 sekaligus), dan digit tengah-tengahnya (digit ke-5) bernilai 1?
Soal 3 Tentukan solusi dari relasi rekursif berikut ini: an 4an1 3an2 n 2 , dengan a0 = 1 dan a1 = 2
Soal 4 z2
u1
v1
w1
x1
y1
v3
w3
v4
z4
w2 x3
x2
u4 w4
u2 v2
z1
u3
y3
z3
x4
y4
y2
Tinjau empat buah graf G1, G2, G3, dan G4 berikut ini. Apakah ada pasangan-pasangan graf yang isomorfis? Tunjukkan/buktikan isomorfisme pasangan graf berikut jika ada.
252
Bundel Soal Elektroteknik >> Semester 3 - 2013/2014 Kementerian Kesejahteraan Anggota - Kementerian Kewirausahaan >> Himpunan Mahasiswa Elektroteknik ITB
Soal 5 Dengan pohon pengkode Huffman prefix-code, tentukan hasil pengkodean dari pesan berikut: prikitiewsusiekatasuledalamovj Hitung jumlah bit minimum untuk menyatakan pesan berikut, sebelum dan sesudah dikodekan.
Soal 6 Buat dan gambarkanlah sebuah Poset (dalam Hasse diagram dengan 7 buah node) yang memiliki: a. b. c. d. e.
Sebuah elemen minimal tetapi tidak memiliki elemen maksimal Sebuah elemen maksimal tetapi tidak memiliki elemen minimal Sebuah elemen minimal dan sebuah elemen maksimal Tidak memiliki elemen minimal maupun maksimal Struktur lattice
Soal 7 Buatlah suatu relasi R pada set {1,2,3,4} yang: a. b.
Reflektif, simetrik, tetapi tidak transitif Irreflektif, antisimetrik, dan transitif
Tentukan ‘transitive closure’ dari masing-masing R tersebut.
Soal 8 1 1 1 1 12 23 3 4 n n 1
a.
Carilah formula untuk
b.
Tentukan fungsi rekursif dari formula tersebut.
Matematika Diskrit Soal >> UAS - 2011/2012
253
SOLUSI UTS - 2012/2013 Soal Nomor 1 a. Periksa apakah implikasi ini tautology : [(
)
(
) (
)]
(
[
)]
Jawab : Bila suatu implikasi tautology, hasil implikasi tersebut pada tabel kebenaran selalu bernilai 1 (benar). Sebut [(
)
(
) (
)] sebagai “A” dan [
(
)] sebagai “B”
Tabel kebenaran : (
) (
)
(
)
(
)
0
0
0
1
1
1
0
1
0
0
0
1
1
0
0
1
1
1
0
0
1
1
1
1
1
1
0
1
0
1
0
1
0
1
1
1
1
1
1
0
1
1
1
0
0
0
1
1
0
1
0
0
1
0
0
0
1
1
0
0
0
0
0
1
1
1
0
1
0
1
0
0
1
1
1
1
1
1
1
1
0
0
0
1
1
0
1
1
1
1
1
1
1
1
0
0
0
1
1
1
0
1
0
0
Karena hasil implikasi tidak selalu bernilai “1”, maka pernyataan implikasi tersebut bukan tautology.
b. Nyatakanlah bagian yang diarsir dari diagram Venn berikut dalam bentuk operasi Set!
A
B
C
Jawab
254
:
Bundel Soal Elektroteknik >> Semester 3 - 2013/2014 Kementerian Kesejahteraan Anggota - Kementerian Kewirausahaan >> Himpunan Mahasiswa Elektroteknik ITB
[
(
)]
[
]
Soal Nomor 2 a.
Berikan estimasi big-O terbaik dari fungsi berikut ini (
)(
(√
)
)
Jawab :
(
(
) : suku dengan pertumbuhan tercepat adalah (√
)
) : suku dengan pertumbuhan tercepat adalah
Jadi estimasi big-O nya adalah :
Keterangan : Urutan fungsi-fungsi umum dari yang tercepat pertumbuhannya :
b.
Untuk ( )
(
)⁄ dari R ke R. Apakah ( ) suatu fungsi? Kalau ya, bijektifkah? Apakah ( ) punya
invers? Jika ya, tentukan
( )
Jawab : ( ) suatu fungsi, karena setiap anggota
dipasangkan dengan tepat satu anggota ( )
( ) adalah fungsi bijektif, karena memenuhi 2 syarat fungsi bijektif yaitu bersifat injective/satu ke satu
dan surjective/onto
Injective/satu ke satu : setiap anggota ( ) dipasangkan dengan tidak lebih dari satu anggota (tidak ada anggota kodomain yang punya pasangan double, triple, dst.) Surjective / onto : setiap anggota ( ) memiliki pasangan anggota (kodomain=range, tidak ada anggota kodomain yang tidak berpasangan)
Sifat dari fungsi bijektif adalah fungsi bijektif memiliki invers Menentukan invers : ( )
(
(
)
)
Maka, ( )
Matematika Diskrit Solusi >> UTS - 2012/2013
(
)
255
Soal Nomor 3 Jawab : d. e. f.
Soal Nomor 4 a.
∑
∑
(
) )
∑{( ∑{ {( {
∑
∑
(
)
(
(
)}
)
(
)
(
}
)
∑ ∑(
b.
(
)
(
)}
∑(
)
( {
)
)
∑(
(
)} }
)
) )
∑{( ∑{ {( {
(
)
( )
∑ ∑(
) )}
(
(
(
) )
(
)
∑( ( }
) )
{
(
)} )
∑(
(
)} }
)
c. Tunjukkan apakah kelompok bilangan bulat berikut prima secara relative berpasang (pairwise relatively prime) : (12, 17, 31, 37), (22, 212, 754) Jawab : Kelompok bilangan dikatakan pairwise relatively prime jika dan hanya jika nilai GCD nya sama dengan 1 Untuk kelompok bilangan (12, 17, 31, 37) Lakukan faktorisasi prima
256
Bundel Soal Elektroteknik >> Semester 3 - 2013/2014 Kementerian Kesejahteraan Anggota - Kementerian Kewirausahaan >> Himpunan Mahasiswa Elektroteknik ITB
GCD (greatest common divider) atau KPK dari keempat bilangan tersebut adalah 1, maka kelompok bilangan bulat tersebut pairwise relatively prime Untuk kelompok bilangan (22, 212, 754) Lakukan faktorisasi prima
GCD (greatest common divider) atau KPK dari ketiga bilangan tersebut adalah 2, maka kelompok bilangan bulat tersebut tidak pairwise relatively prime
Soal Nomor 5 a. Misalkan ( ) merupakan proposisi yang menyatakan bahwa (
)
(
)
)⁄
(
Basis Step: (
( ) terbukti benar karena
)
(
)
Inductive Step: Asumsikan ( ) benar, dalam inductive step ini harus dibuktikan bahwa diasumsikan benar maka dengan kata lain ( (
)
(
)
(
(
) benar. Karena
( )
)
) menyatakan bahwa (
)
(
)(
)
(
(
Sesuai dengan asumsi sebelumnya ) diatas dapat diubah menjadi persamaan ( (
) ( ( ) ( ( ) ( ( ) (
) ) ( ) )
( )( ( ) ( ) ( ( ) ( (
)
( ) (
)
)
) )
( ( ( (
)( ) ( ) ( ) (
)
(
) (
) )
) (
)(
(
)
( (
)
( )(
){( )
)
(
){( ) ) )
) )
} , sehingga
}
)
Karena ruas kiri sama dengan ruas kanan dapat disimpulkan bahwa (
) benar
Dan karena ( ) memenuhi 2 syarat diatas, maka melalui metode induksi terbukti bahwa (
Matematika Diskrit Solusi >> UTS - 2012/2013
)
(
)
(
)
257
b. Bila dijabarkan persamaan ( (
) (
)
menjadi
)
(
(
)(
(
)
c. Bila dijabarkan persamaan (
Sehingga suku
)
)
(
)
(
(
)
(
)
)
( )
) (
sama dengan
)
menjadi
)
(
dalam persamaan (
) )
( )
(
)
( )
(
)( )
akan berupa (
dalam persamaan (
Jadi koefisien suku
)
akan berupa
dalam persamaan (
Jadi koefisien suku
(
)
dalam persamaan (
Sehingga suku
(
)
)
)
( )
sama dengan (
)
Soal Nomor 6 Dengan menggunakan fungsi deskripsi ( ) Huruf Pesan
(
)
Huruf Translasi
dapat ditentukan tabel translasi seperti dibawah Huruf Pesan
Huruf Translasi
A
0
25
Z
N
13
25
Z
B
1
1
A
O
14
1
A
C
2
3
C
P
15
3
C
D
3
5
F
Q
16
5
F
E
4
7
H
R
17
7
H
F
5
9
J
S
18
9
J
G
6
11
L
T
19
11
L
H
7
13
N
U
20
13
N
I
8
15
P
V
21
15
P
J
9
17
R
W
22
17
R
K
10
19
T
X
23
19
T
L
11
21
V
Y
24
21
V
M
12
23
X
Z
25
23
X
Dengan menggunakan tabel diatas dapat ditranslasikan pesan EKSUSMIEAPA menjadi HTJNJXPHZCZ
Soal Nomor 7 Suatu dadu octahedral memiliki 8 buah sisi. Setiap sisi diberi nomor dari 1 sampai dengan 8. Diketahui bahwa dadu ini bersifat bias, dimana nomor mata dadu ganjil pada octahedron memiliki peluang muncul 2 kali dibandingkan dengan nomor mata datu genap, tentukan:
258
Bundel Soal Elektroteknik >> Semester 3 - 2013/2014 Kementerian Kesejahteraan Anggota - Kementerian Kewirausahaan >> Himpunan Mahasiswa Elektroteknik ITB
a.
Nilai harap (expectation value) dari nomor dadu yang muncul
Jawab : P(odd) = 2. P(even) Karena dadu memiliki 4 nomor ganjil dan 4 nomor genap dan jumlah peluang semuanya adalah 1, maka : 4. P(odd) + 4. P(even) = 1 4. [2. P(even)] + 4. P(even) = 12. P(even) = 1 Maka P(even) =
dan P(odd) =
Nilai harap adalah total penjumlahan dari tiap nilai yang dikali dengan peluang munculnya nilai tersebut ( )
∑ ( )
( )
( ) ( ) Berarti jika kita melempar dadu tersebut berkali-kali lalu bilangan yang muncul dijumlahkan dan hasil keseluruhan dibagi dengan banyaknya percobaan, kita bisa berharap memperoleh angka b.
.
Variansi dari nomor dadu yang muncul ( )
∑[ ( )
( )]
( )
Kita masukkan nilai harap yang telah didapat sebelumnya ( )
[(
[(
)
)
]
]
[(
[(
) )
] ]
[(
)
[(
)
] ]
[(
)
[(
)
] ]
( )
Soal Nomor 8 a) (
)( )
( ( ))
Untuk menentukan (
(
)
(
) (
)
) ( ), kita misalkan (
)( ) ( ( (
)
(
)
) )
Sehingga (
Matematika Diskrit Solusi >> UTS - 2012/2013
) ( )
( (
) )
259
b) (
)( )
( ( ))
Untuk menentukan (
(
)
) ( ), kita misalkan (
)( )
Sehingga (
) ( )
c) Untuk X bilangan integer dan 0<X<25, tentukan himpunan solusi dari kongruensi 2(X+3) = 1 (mod 7). Jawab : 2 (x+3) = 1
2 (x+3) = 1+7
2 (x+3) = 1+2.7
2 (x+3) = 1+3.7
2x + 6 = 1
2x + 6 = 8
2x + 6 = 15
2x + 6 = 22
x = -2,5 (tidak integer)
x = 1 (integer, memenuhi)
x = 4,5 (tidak integer)
x = 8 (integer, memenuhi)
2(x+3) = 1+4.7
2 (x+3) = 1+5.7
2 (x+3) = 1+6.7
2 (x+3) = 1+7.7
2x+6=29
2x + 6 = 36
2x+6 = 43
2x+6 = 50
x = 11,5 (tidak integer)
x = 15 (integer, memenuhi)
x = 18,5 (tidak integer)
x = 22 (integer, memenuhi)
Himpunan solusi : x = { 1, 8, 15, 22 }
260
Bundel Soal Elektroteknik >> Semester 3 - 2013/2014 Kementerian Kesejahteraan Anggota - Kementerian Kewirausahaan >> Himpunan Mahasiswa Elektroteknik ITB
UAS - 2012/2013 Soal Nomor 1 a. Lintasan dan sirkuit Hamilton : melewati semua vertex (titik) tepat sekali. Dari definisi tersebut, ada banyak jawaban yang benar dari soal ini. Salah satunya adalah sebagai berikut. g
f
e
k
j
a
z
a
d
z
k
j
p
n h Lintasan Hamilton
g
f
e
n
p
d
h
Sirkuit Hamilton
b. Lintasan dan sirkuit Euler : melewati semua edge (garis) tepat sekali Graph ini tidak memiliki sirkuit Euler c. Solusi dari ‘travelling salesman problem’ 4
e
g
f 6
12
8 6
j
5
z
4
e
f
k
a
n
12
6
j 5 3
6 h
Sirkuit Hamilton A
5
d
z 4
p
7
g
4
5 3
8
a
n
k
p
2 2
5 6 h
d
Sirkuit Hamilton B
Ada 2 kemungkinan sirkuit Hamilton, yaitu sirkuit Hamilton A dan sirkuit Hamilton B (gambar lihat diatas). Sirkuit Hamilton A mempunyai panjang lintasan sepanjang 4+6+6+8+5+4+5+6+7+3+12=66, sedangkan sirkuit Hamilton B mempunyai panjang lintasan sepanjang 3+12+4+8+5+6+2+6+5=60. Sehingga solusi dari travelling salesman problem merupakan sirkuit Hamilton B d. Lintasan terpendek dari a ke z
Matematika Diskrit Solusi >> UAS - 2012/2013
261
z 4 6
j
k
5 p
5 a
3
n
Panjang lintasan= 3+5+6+5+4=23 e. Chromatic number : jumlah warna minimal sehingga tidak ada vertex bertetangga yang berwarna sama Chromatic number dari graph ini = 3. Berikut penjabarannya. 1
2
1
2
3
1
2
1
2
2
1
3
1
2
3
1
2
1
2
1
2
1
f. Graph ini planar karena bisa digambar pada bidang datar g. Incidence matrix dengan urutan baris e, f, g, z, j, k, p, a, n, h, d dan urutan kolom 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 adalah :
[ ] Penjelasan (lihat gambar dibawah): Nomer yang dilingkari merupakan nomer lintasan pada matriks insiden
262
Bundel Soal Elektroteknik >> Semester 3 - 2013/2014 Kementerian Kesejahteraan Anggota - Kementerian Kewirausahaan >> Himpunan Mahasiswa Elektroteknik ITB
e
1 4
6
5
10 3 13
g
k
5 n
3 5
6 8 6 8
j
4 12
a
2 8
f
4
7 5 9
p
11 2 7 14
z
h
12 5 6 15
d
h. Adjacency matrix dengan urutan baris dan kolom e, f, g, z, j, k, p, a, n, h, d adalah :
[ i.
Minimum spanning tree : tree yang menghubungkan semua vertex dengan total edge minimum f
e
a
g
k
j
j.
]
n
z
p
h
d
Bila sebuah graph bipartite, vertex-vertexnya bisa dibagi menjadi 2 himpunan dimana ada hubungan antar vertex pada himpunan berbeda tapi tidak ada hubungan antar vertex pada himpunan yang sama Graph ini tidak bipartite
Matematika Diskrit Solusi >> UAS - 2012/2013
263
Soal Nomor 2 a. Poset {{2, 3, 4, 5, 8, 9, 10, 15, 18, 24, 36, 45, 60}, |} Diagram Hasse : 60
45
24 36
b. c. d. e. f. g. h. i. j.
264
8
18
4
9
2
3
15
10
5
Elemen maksimal : 24, 36, 45, 60 Elemen minimal : 2, 3, 5 Greatest element : tidak ada Least element : tidak ada Upper bounds dari {3, 5} : 15, 45, 60 LUB {3, 5} : 15 Lower bounds dari {15, 45} : 3, 5, 15 GLB {15, 45} : 15 Poset Lattice : poset dimana setiap pasang elemen punya LUB dan GLB Poset ini tidak Lattice, karena ada pasangan elemen tidak punya LUB dan GLB. Contohnya saja {2, 3} tidak memiliki upper bound
Bundel Soal Elektroteknik >> Semester 3 - 2013/2014 Kementerian Kesejahteraan Anggota - Kementerian Kewirausahaan >> Himpunan Mahasiswa Elektroteknik ITB
Soal Nomor 3 Bagian a : Dari matriks relasi : ke [1] [2] [3] [4] d
[1] 1
0
1
1
a
[2] 1
1
1
0
r
[3] 0
0
0
1
i
[4] 0
1
0
0
Maka representasi R dalam bentuk graph adalah :
1
2
4
3
Bagian b : [
]
[ ]
[
][
]
[
].
[ ]
[
] [
]
[
]
[ ]
[
] [
]
[
]
Transitive closure dari R adalah Karena
[ ]
[ ]
[ ]
semuanya sudah bernilai 1, maka matriks gabungannya juga semuanya bernilai 1
Matematika Diskrit Solusi >> UAS - 2012/2013
265
Jadi transitive closure dari R adalah : {(1,1), (1,2), (1,3), (1,4), (2, 1), (2,2), (2,3), (2,4), (3,1), (3,2), (3,3), (3,4), (4,1), (4,2), (4,3), (4,4)}
Bagian c : Syarat suatu relasi termasuk kelas setara adalah relasi tersebut simetrik, transitif, dan reflektif
Relasi R tidak simetrik, misalnya saja ada pasangan (1, 3) tapi tidak ada pasangan (3, 1) Relasi R tidak reflektif, tidak ada pasangan (3, 3) dan (4, 4) Relasi R tidak transitif, ada pasangan (2, 1) dan (1, 4) tetapi tidak ada pasangan (2, 4)
Jadi relasi R tidak termasuk kelas setara
Soal Nomor 4 Gunakan metode Backtracking untuk menyelesaikan masalah n-queen dengan n = 7 Jawab : Tempatkan queen dengan nomor urut seperti pada gambar : 1
Lanjutkan untuk nomor 2, 3, 4, dan 5 1 2 3 4 5
266
Bundel Soal Elektroteknik >> Semester 3 - 2013/2014 Kementerian Kesejahteraan Anggota - Kementerian Kewirausahaan >> Himpunan Mahasiswa Elektroteknik ITB
Ternyata gagal, maka kembali ke langkah 3, letakkan nomor 4 di tempat yang berbeda, dan lakukan lagi langkahlangkah di atas 1 2 3 4 5 6 7
Tidak ada queen yang bisa saling memakan pada ketujuh posisi, maka gambar di atas adalah jawabannya
Soal Nomor 5 Bila elemen A seri dengan elemen B, probabilitas total keberhasilan sirkuit adalah : P(A). P(B) Bila eleman A paralel dengan elemen B, probabilitas total keberhasilan sirkuit adalah : 1- [P(A’).P(B’)] Ada 4 kemungkinan jalur : -
0,7. 0,7 = 0,49 0,7. 0,5. 0,8 = 0,28 0,8. 0,8. 0,5. 0,7 = 0,224 0,8. 0,8. 0,8 = 0,512
Keempat jalur ini paralel satu dengan yang lainnya. Maka probabilitas keberhasilan sistem adalah : 1 - [(1-0,49). (1-0,28). (1-0,224). (1-0,512)] = 1 – [0,51. 0,72. 0,776. 0,448] = 0,87
Soal Nomor 6 Bagian a : Dari string “mencontekadalahtermasukdalamperbuatankriminal” pertama daftar huruf apa saja yang ada dan berapa jumlahnya a:9
h:1
m:4
r:3
b:1
i:2
n:4
s:1
c:1
k:3
o:1
t:3
d:2
l:3
p:1
u:2
e:4
Setelah itu, urutkan dari frekuensi terjarang hingga frekuensi tersering. Dimulai dari frekuensi terjarang, pasangpasangkan dan gabungkan menjadi ‘binary tree’ dan usahakan agar kaki kiri dan kanan dari semua binary tree tersebut memiliki jumlah yang relatif seimbang.
Matematika Diskrit Solusi >> UAS - 2012/2013
267
Beri kode ‘0’ pada setiap kaki kiri dan kode ‘1’ pada setiap kaki kanan. Karena binary tree pada solusi ini dibuat dari atas ke bawah, maka kode ‘0’ pada kaki atas dan kode ‘1’ pada kaki bawah.
2
7
4 3 [r]
2
14 7 28 7 14
45
7 17
8 9 [a]
4 [m]
4 3 [l] 4 3 [k]
2 2 [d]
1 [b] 1 [c]
1 [h] 1 [o] 1 [p] 1 [s]
2 [i] 2 [u]
3 [t] 4 [e]
4 [n]
Bagian b : Ada 17 jenis huruf pada string ini, sehingga dengan fixed-length code dibutuhkan minimal 5 bit untuk merepresentasikan setiap hurufnya (5 bit -> 25 : cukup untuk menampung hingga 32 karakter) Maka jumlah total bit yang dibutuhkan untuk fixed-length code adalah : 5 bit/huruf x 45 huruf = 225 bit Untuk variable-length code, ini adalah representasi bit tiap karakter dengan panjang bit bervariasi a : 11 [2]
h : 000010 [6]
m : 100 [3]
r : 0001 [4]
b : 000000 [6]
i : 01000 [5]
n : 101 [3]
s : 001001 [6]
c : 000001 [6]
k : 0101 [4]
o : 000011 [6]
t : 0110 [4]
d : 00101 [5]
l : 0011 [4]
p : 001000 [6]
u : 01001 [5]
e : 0111 [4]
Maka jumlah total bit yang dibutuhkan untuk variable-length code adalah : ∑
= 2.9+6.1+6.1+5.2+4.4+6.1+5.2+4.3+4.3+3.4+3.4+6.1+6.1+4.3+6.1+4.3+5.2 = 172
bit Kesimpulan : pada soal ini, bit yang dibutuhkan untuk merepresentasikan string dengan variable-length code lebih sedikit dibandingkan dengan bit yang dibutuhkan untuk merepresentasikan string dengan fixed-length code.
268
Bundel Soal Elektroteknik >> Semester 3 - 2013/2014 Kementerian Kesejahteraan Anggota - Kementerian Kewirausahaan >> Himpunan Mahasiswa Elektroteknik ITB
Soal Nomor 7 Jawab : Ya, kedua graph isomorphic. Bila kita petakan : -
1 ke a 2 ke c 3 ke e 4 ke b 5 ke d
Tetangga 1 adalah 2 dan 5. Demikian juga dengan pasangannya, tetangga a (pasangan 1) adalah c (pasangan 2) dan d (pasangan 5). Hal ini berlaku untuk kelima node pada pasangan graph. Dengan demikian, dapat disimpulkan bahwa kedua graph isomorfis.
Matematika Diskrit Solusi >> UAS - 2012/2013
269
