MATEMATIKA DISKRIT

1.      a.  De Morgan                                                                        Dualitas
f (g,h,i) = (gh+hi)’                                                        f(g,h,i) = (gh+hi)’
f(g,h,i)’ = ((gh+hi)’)                                                     Dual (g,h,i)  = (g’+h’).(h’+i’)   
            = (g’h’+h’i’)’                                                     f’ (g,h,i)        = (g+h).(h+i)
            = (g+h) . (h+i)
b.  Tabel Kebenaran
g
h
i
g’
h’
i’
g’h’
h’i’
(g’h’+h’i’)
0
0
0
0
1
1
1
1
1
1
1
0
0
1
1
1
0
1
0
1
2
0
1
0
1
0
1
0
0
1
3
0
1
1
1
0
0
0
0
0
4
1
0
0
0
1
1
0
1
1
5
1
0
1
0
1
0
0
0
0
6
1
1
0
0
0
1
0
0
0
7
1
1
1
0
0
0
0
0
0

SOP = ∑ (0,1,4)
POS = π (2,3,5,6,7)

c. Peta Karnaugh
SOP = ∑ (0,1,4)
g\hi
h’i’
h’i
hi
hi’
00
01
11
10
g’
0
1
1
0
0
g
1
1
0
0
0
           




            SOP = g’h’+h’i’                                   

POS = π (2,3,5,6,7)
g\hi
hi
hi’
h’i’
h’i
00
01
11
10
g
0
1
1
0
0
g’
1
1
0
0
0

POS = (h’+i’).(g’+i’)

  1. a.  Simpul : A, B, C, D, E
     Sisi      : e1, e2, e3, e4, e5, e6, e7, e8

b.  Matriks Bertetanggaan
A
B
C
D
E
A
0
1
1
0
0
B
1
0
1
1
1
C
1
1
0
1
0
D
0
1
1
0
1
E
0
1
0
1
0




   Matriks Bersisian
e1
e2
e3
e4
e5
e6
e7
e8
A
1
1
0
0
0
0
0
1
B
1
0
1
1
1
0
0
0
C
0
1
1
0
0
0
1
1
D
0
0
0
1
0
1
1
0
E
0
0
0
0
1
1
0
0
           
   Senarai Ketetanggaan
            A : B, C                                                                        D : B, C, E
            B : A, C, D, E                                                    E : B, D
            C : A, B, D
            c.  Lintasan Terpendek
contoh : A menuju D
A-B-E-D                       : 5+1+2 = 8
A-B-D                           : 5+4 = 9
A-C-B-D                       : 10+3+4 = 17
A-C-B-E-D                    : 10+3+1+2 = 16
Lintasan Terpendek   : A-B-E-D
d.  Pewarnaan Graf                                      
d (A) = 3                              
d (B) = 4
d (C) = 4
d (D) = 3
d (E) = 2


Urutan Pewarnaan graf : B-C-A-D-E
Jumlah minimum warna (bilangan kromatik) = 3
A : kuning
B : merah
C : hijau
D : kuning
E : hijau
 








  1. a.  Gambar pohon merentang

 










b.  Algoritma Prim & Kruskal
A-B = 15          B-F = 5             C-D = 30          E-F = 40
A-C = 10          B-E = 45           D-E = 50
A-F = 20           B-C = 25          D-F = 35
Algoritma Prim
1.       




2.     





3.       









4.       









5.       

















Algoritma Kruskal
1.     


 



2.                                   




3.     






4.       












5.       










6.       













  1. a.  Ekspresi min 6 variabel
variabel : A, B, C, D, E, F
((A*B)/C)+((D-E)/F))
b.  Gambar pohon ekspresi dengan operator
 










c.  Infix : ((A*B)/C)+((D-E)/F))
     Prefix :
1.      ((*AB)/C)+((-DE)/F)
2.      (/*ABC)+(/-DEF)
3.      +/*ABC/-DEF
Postfix :
1.      ((AB*)/C)+((DE-)/F)
2.      (AB*C/)+(DE-F/)
3.      AB*C/DE-F/+




d.  Gambar pohon ekspresi tanpa operator
    Variabel : a, b, c, d, e, f, g, h, i








e.  In order : d b e a h f i c g
     Pre order :  
1.      b d e a f h i c g
2.      b d e a c f h i g
3.      a b d e c f h i g
    Post order :
1.      d e b a h i f c g
2.      d e b a h i f g c
3.      d e b h i f g c a







f.  Kode Huffman dari AABBCCCAD
Simbol
Kerapatan
Probabilita
Kode Huffman
A
3
3/9
0
B
2
2/9
111
C
3
3/9
10
D
1
1/9
110
                                                  9

Gambar pohon untuk mementukan Kode Huffman berdasarkan 2 probabilita terkecil.
Tentukan nilai:
Kiri       : 0
Kanan  : 1






Jadi kode untuk AABBCCCAD = 0 0 111 111 10 10 10 0 110

 1.      a.  De Morgan                                                                        Dualitas
f (g,h,i) = (gh+hi)’                                                        f(g,h,i) = (gh+hi)’
f(g,h,i)’ = ((gh+hi)’)                                                     Dual (g,h,i)  = (g’+h’).(h’+i’)   
            = (g’h’+h’i’)’                                                     f’ (g,h,i)        = (g+h).(h+i)
            = (g+h) . (h+i)
b.  Tabel Kebenaran
g
h
i
g’
h’
i’
g’h’
h’i’
(g’h’+h’i’)
0
0
0
0
1
1
1
1
1
1
1
0
0
1
1
1
0
1
0
1
2
0
1
0
1
0
1
0
0
1
3
0
1
1
1
0
0
0
0
0
4
1
0
0
0
1
1
0
1
1
5
1
0
1
0
1
0
0
0
0
6
1
1
0
0
0
1
0
0
0
7
1
1
1
0
0
0
0
0
0

SOP = ∑ (0,1,4)
POS = π (2,3,5,6,7)

c. Peta Karnaugh
SOP = ∑ (0,1,4)
g\hi
h’i’
h’i
hi
hi’
00
01
11
10
g’
0
1
1
0
0
g
1
1
0
0
0
           




            SOP = g’h’+h’i’                                   

POS = π (2,3,5,6,7)
g\hi
hi
hi’
h’i’
h’i
00
01
11
10
g
0
1
1
0
0
g’
1
1
0
0
0

POS = (h’+i’).(g’+i’)

  1. a.  Simpul : A, B, C, D, E
     Sisi      : e1, e2, e3, e4, e5, e6, e7, e8

b.  Matriks Bertetanggaan
A
B
C
D
E
A
0
1
1
0
0
B
1
0
1
1
1
C
1
1
0
1
0
D
0
1
1
0
1
E
0
1
0
1
0




   Matriks Bersisian
e1
e2
e3
e4
e5
e6
e7
e8
A
1
1
0
0
0
0
0
1
B
1
0
1
1
1
0
0
0
C
0
1
1
0
0
0
1
1
D
0
0
0
1
0
1
1
0
E
0
0
0
0
1
1
0
0
           
   Senarai Ketetanggaan
            A : B, C                                                                        D : B, C, E
            B : A, C, D, E                                                    E : B, D
            C : A, B, D
            c.  Lintasan Terpendek
contoh : A menuju D
A-B-E-D                       : 5+1+2 = 8
A-B-D                           : 5+4 = 9
A-C-B-D                       : 10+3+4 = 17
A-C-B-E-D                    : 10+3+1+2 = 16
Lintasan Terpendek   : A-B-E-D
d.  Pewarnaan Graf                                      
d (A) = 3                              
d (B) = 4
d (C) = 4
d (D) = 3
d (E) = 2


Urutan Pewarnaan graf : B-C-A-D-E
Jumlah minimum warna (bilangan kromatik) = 3
A : kuning
B : merah
C : hijau
D : kuning
E : hijau
 








  1. a.  Gambar pohon merentang

 









b.  Algoritma Prim & Kruskal
A-B = 15          B-F = 5             C-D = 30          E-F = 40
A-C = 10          B-E = 45           D-E = 50
A-F = 20           B-C = 25          D-F = 35
Algoritma Prim
1.       




2.     





3.       









4.       









5.       
















Algoritma Kruskal
1.     


 


2.                                   




3.     






4.       












5.       










6.       













  1. a.  Ekspresi min 6 variabel
variabel : A, B, C, D, E, F
((A*B)/C)+((D-E)/F))
b.  Gambar pohon ekspresi dengan operator
 









c.  Infix : ((A*B)/C)+((D-E)/F))
     Prefix :
1.      ((*AB)/C)+((-DE)/F)
2.      (/*ABC)+(/-DEF)
3.      +/*ABC/-DEF
Postfix :
1.      ((AB*)/C)+((DE-)/F)
2.      (AB*C/)+(DE-F/)
3.      AB*C/DE-F/+




d.  Gambar pohon ekspresi tanpa operator
    Variabel : a, b, c, d, e, f, g, h, i








e.  In order : d b e a h f i c g
     Pre order :  
1.      b d e a f h i c g
2.      b d e a c f h i g
3.      a b d e c f h i g
    Post order :
1.      d e b a h i f c g
2.      d e b a h i f g c
3.      d e b h i f g c a







f.  Kode Huffman dari AABBCCCAD
Simbol
Kerapatan
Probabilita
Kode Huffman
A
3
3/9
0
B
2
2/9
111
C
3
3/9
10
D
1
1/9
110
                                                  9

Gambar pohon untuk mementukan Kode Huffman berdasarkan 2 probabilita terkecil.
Tentukan nilai:
Kiri       : 0
Kanan  : 1






Jadi kode untuk AABBCCCAD = 0 0 111 111 10 10 10 0 110

at
Labels:

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.

Subscribe to: Post Comments (Atom)