Matematika
description
Transcript of Matematika
![Page 1: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/1.jpg)
MATEMATIKA DISKRIT
FADLISYAH, S.Si BUSTAMI, S.Si, M.Si
PENERBIT GRAHA ILMU
![Page 2: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/2.jpg)
DAFTAR ISI Kata Pengantar Daftar Isi
BAB 1 – LOGIKA 1.1 Gerbang Logika 1.2 Aljabar Boolean
1 1 5
BAB 2 – PETA KARNAUGH 11 BAB 3 – METODE QUINE McCLUSKEY 21 BAB 4 – KONVOLUSI
4.1 Pondasi Konvolusi 4.2 Perancangan Program
39 39 43
BAB 5 – BILANGAN FLOATING-POINT 51 BAB 6 – KODE HAMMING 59 BAB 7 – GRAPH 67 Lampiran Daftar Pustaka
![Page 3: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/3.jpg)
KATA PENGANTAR
Dengan rahmat Allah SWT, buku ini telah selesai disusun walaupun dengan situasi yang sangat tidak menguntungkan bagi penulis. Sedikit tertatih-tatih, alasan kesehatan, penulis hadir dengan buku terbarunya berjudul Matematika Diskrit. Representasi data di dalam komputer bersifat tidak kontinu atau diskrit, sehingga keadaan ini telah mengambil suatu wilayah kajian baru dalam bidang matematika khususnya untuk aplikasi pemanipulasian bit-bit. Perkembangan matematika diskrit sendiri dipengaruhi drastis oleh perkembangan mesin Von Neumann, dan oleh karena itu penulis lebih tertarik untuk menyusun buku matematika diskrit yang berfokus kepada pemanipulasian bit-bit.
Adapun materi yang hadir di dalam buku ini meliputi : Logika, Peta Karnaugh, Metode QuineMcCluskey, Konvolusi, Representasi Bilangan Floating-Point, Kode Hamming, dan Teori Graph. Buku ini ditujukan kepada mahasiswa yang mengambil mata kuliah matematika diskrit, sebagai sarana primitif untuk menjangkau konsep-konsep pemanipulasian data yang lebih mendalam.
![Page 4: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/4.jpg)
BBaabb 11
LOGIKA
1.1 Gerbang Logika
Informasi biner direpresentasikan di dalam komputer digital oleh beberapa kuantitas yang disebut juga sebagai sinyal. Sinyal-sinyal elektris yang hadir di dalam komputer seperti voltase, direpresentasikan ke dalam salah satu bentuk satu atau dua state yang dikenal. Untuk representasi ke dalam dua state, variabel biner dapat berupa nilai 1 atau 0. Pada beberapa komputer digital, sinyal 3 volt merepresentasikan nilai biner 1 dan sinyal 0,5 volt merepresentasikan nilai biner 0.
Logika biner bertransaksi dengan berbagai variabel biner dan operasi-operasi yang mengandung berbagai logika, yang selanjutnya digunakan untuk memaparkan, dalam bentuk tabular atau aljabar, pemanipulasian dan pengolahan informasi biner. Pemanipulasian informasi biner dilakukan oleh berbagai sirkuit logika yang disebut juga sebagai gate. Gate (gerbang) merupakan sebuah blok hardware yang memproduksi sinyal-sinyal biner 1 dan 0 ketika input logikal yang diperlukan telah terpenuhi. Masing-masing gate memiliki simbol grafis yang berbeda dan berbagai operasi yang dilakukan berdasarkan maksud-maksud dari ekspresi aljabar. Hubungan input-output dari berbagai variabel biner untuk masing-masing gate direpresentasikan dalam bentuk tabular, sebagai berikut :
![Page 5: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/5.jpg)
2 MATEMATIKA DISKRIT
1. Gerbang AND
Simbol :
Fungsi aljabar :
BAx ⋅= atau ABx =
Tabel kebenaran :
B
A x
A B x
0 0 0
0 1 0
1 0 0
1 1 1
2. Gerbang OR
Simbol :
Fungsi aljabar :
BAx +=
x B
A
![Page 6: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/6.jpg)
LOGIKA 3
Tabel kebenaran :
A B x
0 0 0
0 1 1
1 0 1
1 1 1
3. INVERTER
Simbol :
Fungsi aljabar :
Ax ′=
Tabel kebenaran :
x A
A x
0 1
1 0
4. BUFFER
Simbol :
![Page 7: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/7.jpg)
4 MATEMATIKA DISKRIT
Fungsi aljabar :
Ax =
Tabel kebenaran :
A x
A x
0 0
1 1
5. Gerbang XOR
Simbol :
Fungsi aljabar :
BAx ⊕= atau BABAx ′+′=
Tabel kebenaran :
A
x
B
![Page 8: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/8.jpg)
LOGIKA 5
A B x
0 0 0
0 1 1
1 0 1
1 1 0
1.2 Aljabar Boolean
Aljabar Boolean merupakan bidang aljabar yang berurusan dengan berbagai variabel biner dan operasi-operasi logika. Perhatikan ekspresi fungsi Boolean berikut :
zyxF ′+=
maka dapat kita tentukan tabel kebenaran ekspresi tersebut sebagai :
x y z F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
![Page 9: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/9.jpg)
6 MATEMATIKA DISKRIT
Diagram logikanya :
y
z
x
F
Kegunaan aljabar Boolean adalah untuk memfasilitasi analisis dan desain berbagai sirkuit digital. Aljabar Boolean memberikan suatu perangkat yang tepat terhadap :
1. Pengekspresian secara aljabar terhadap berbagai keterhubungan dalam bentuk tabel kebenaran di antara berbagai variabel biner.
2. Pengekspresian secara aljabar terhadap berbagai bentuk keterhubungan input-output diagram logika.
3. Memungkinkan perancangan berbagai sirkuit yang lebih sederhana terhadap fungsi yang sama.
Berbagai sifat-sifat atau identitas dari aljabar Boolean :
1. xx =+ 0
2. 11=+x3. xxx =+
4. 1=′+ xx5. xyyx +=+
6. zyxzyx ++=++ )()(
7. xzxyzyx +=+ )(
8. yxyx ′′=′+ )(
![Page 10: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/10.jpg)
LOGIKA 7
9. xx =′′)(
10. 00 =⋅x
11. xx =⋅112. xxx =⋅
13. 0=′⋅ xx14. yxxy =
15. zxyyzx )()( =
16. ))(( zxyxyzx ++=+
17. yxxy ′+′=′)(
Berbagai contoh kasus, perhatikan ekspresi aljabar Boolean berikut :
DCBADCBA ′+′+′+′
bila diasumsikan bahwa xDCBA =′+′ , maka ekspresi di atas dapat berupa xx + , dan berdasarkan identitas (3) diperoleh :
DCBADCBADCBA ′+′=′+′+′+′
Untuk ekspresi yang lain kita ambil :
CACABABCF ′+′+=
berturut-turut kita peroleh :
CACABABCF ′+′+=
( ) CACCABF ′+′+=
CAABF ′+=
![Page 11: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/11.jpg)
8 MATEMATIKA DISKRIT
dengan diagram logika sebagai :
untuk CACABABCF ′+′+= , dan
untuk CAABF ′+= .
Komplemen fungsi Boolean
Komplemen suatu fungsi Boolean secara sederhana dapat kita lakukan dengan menukar nilai-nilai 1 dan 0 pada tabel kebenaran. Untuk berbagai bentuk ekspresi aljabar, kita dapat menggunakan teorema DeMorgan sebagai berikut :
F
![Page 12: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/12.jpg)
LOGIKA 9
nn xxxxxxxx ′′′′=′++++ ...)...( 321321
nn xxxxxxxx ′++′+′+′=′ ...)...( 321321
Berdasarkan teorema DeMorgan, maka komplemen fungsi Boolean DBDCABF ′+′′+= adalah ))()(( DBDCBAF ′++′+′=′ .
![Page 13: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/13.jpg)
BBaabb 22
PETA KARNAUGH
Kompleksitas dari diagram logika yang merupakan wujud fungsi Boolean, terkait secara langsung dengan kekompleksitasan ekspresi Boolean yang diimplementasikan. Representasi tabel kebenaran dari suatu fungsi bersifat unik, tetapi fungsi dapat muncul dalam berbagai bentuk ketika diekspresikan secara aljabar. Ekspresi dapat disederhanakan menggunakan relasi-relasi dasar aljabar Boolean. Bagaimanapun, prosedur tersebut kadang-kadang masih terasa sulit bila dihadapkan dengan kurangnya aturan-aturan khusus dalam memprediksikan langkah-langkah yang diperlukan selanjutnya di dalam proses pemanipulasian. Untuk mengatasi hal tersebut, maka diperkenalkanlah metode peta Karnaugh.
Berbagai peta berdasarkan jumlah variabelnya :
1. 2 variabel ( )yx,
0 1
0 0m 1m
1 2m 3m
x y
x
y
![Page 14: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/14.jpg)
12 MATEMATIKA DISKRIT
Keterangan :
nm dibaca minterm ke-n .
minterm merupakan perkalian literal yang mengandung semua varaibel.
2. 3 variabel ( )zyx ,,
y
00 01 11 10
0 0m 1m 3m 2m
1 4m 5m 7m 6m
x yz
x
z
3. 4 variabel ( )zyxw ,,,
y
00 01 11 10
00 0m 1m 3m 2m
01 4m 5m 7m 6m
11 12m 13m 15m 14m
10 8m 9m 11m 10m
wx yz
x
w
z
![Page 15: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/15.jpg)
PETA KARNAUGH 13
4. 5 variabel ( )edcba ,,,,
c
000 001 011 010 110 111 101 100
00 0m 1m 3m 2m 6m 7m 5m 4m
01 8m 9m 10m 11m 14m 15m 13m 12m
11 24m 25m 27m 26m 30m 31m 29m 28m
10 16m 17m 19m 18m 22m 23m 21m 20m
d
e e
ab cde
b
a
Tabel format minterm dan Maxterm untuk 5 variabel :
minterm Maxterm abcde
Term Simbol Term Simbol
00000 edcba ′′′′′ 0m edcba ++++ 0M
00001 edcba ′′′′ 1m edcba ′++++ 1M
00010 edcba ′′′′ 2m edcba +′+++
00011 decba ′′′ 3m edcba ′+′+++
00100 edcba ′′′′ 4m edcba ++′++
:
:
:
![Page 16: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/16.jpg)
14 MATEMATIKA DISKRIT
00101 edcba ′′′ 5m edcba ′++′++
00110 ecdba ′′′ 6m edcba +′+′++
00111 cdeba ′′ 7m edcba ′+′+′++
01000 edcba ′′′′ 8m edcba +++′+
01001 edcba ′′′ 9m edcba ′+++′+
01010 edcba ′′′ 10m edcba +′++′+
01011 decba ′′ 11m edcba ′+′++′+
01100 edbca ′′′ 12m edcba ++′+′+
01101 edbca ′′ 13m edcba ′++′+′+
01110 ebcda ′′ 14m edcba +′+′+′+
01111 bcdea′ 15m edcba ′+′+′+′+
10000 edcba ′′′′ 16m edcba ++++′
10001 edcba ′′′ 17m edcba ′++++′
10010 edcba ′′′ 18m edcba +′+++′
10011 decba ′′ 19m edcba ′+′+++′
10100 edcba ′′′ 20m edcba ++′++′
10101 edcba ′′ 21m edcba ′++′++′
10110 ecdba ′′ 22m edcba +′+′++′
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
![Page 17: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/17.jpg)
PETA KARNAUGH 15
10111 cdeba ′ 23m edcba ′+′+′++′
11000 edcab ′′′ 24m edcba +++′+′
11001 edcab ′′ 25m edcba ′+++′+′
11010 edcab ′′ 26m edcba +′++′+′
11011 decab ′ 27m edcba ′+′++′+′
11100 edabc ′′ 28m edcba ++′+′+′
11101 edabc ′ 29m edcba ′++′+′+′
:
:
:
:
:
:
:
:
:
11110 eabcd ′ 30m edcba +′+′+′+′ 30M
11111 abcde 31m edcba ′+′+′+′+′ 31M
5. 6 variabel ( )edcfba ,,,,,
Berbagai istilah terkait :
minterm atau produk baku merupakan perkalian literal yang mengandung semua variabel.
Maxterm atau jumlah baku merupakan jumlah literal yang mengandung semua variabel.
Literal merupakan ekspresi Boolean yang dibentuk oleh hanya satu variabel atau komplemen dari satu variabel.
![Page 18: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/18.jpg)
16 MATEMATIKA DISKRIT
c
000 001 011 010 110 111 101 100
000 0m 1m 3m 2m 6m 7m 5m 4m
001 8m 9m 10m 11m 14m 15m 13m 12m
011 24m 25m 27m 26m 30m 31m 29m 28m
010 16m 17m 19m 18m 22m 23m 21m 20m
110 48m 49m 51m 50m 54m 55m 53m 52m
111 56m 57m 59m 58m 62m 63m 61m 60m
101 40m 41m 43m 42m 46m 47m 45m 44m
100 32m 33m 35m 34m 38m 39m 37m 36m
abf cde
f
f
b
a
d e e
Soal-soal
1. Minimasikan fungsi Boolean ∑= )5,4,2,3(),,( zyxF menggunakan peta Karnaugh ?
Jawab :
Keterangan : dalam pengelompokkan nilai-nilai 1 (satu), setiap kelompok harus memnuhi elemen (vertikal atau horisontal, tidak berbentuk diagonal).
,....,2,1,0,2 =nn
![Page 19: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/19.jpg)
PETA KARNAUGH 17
Hasil minimasi ⇒ xyyxzyxF ′+′=),,( .
y 00 01 11 10
0 1 1
1 1 1
x yz
x
z
xy ′ yx ′
2. Untuk kasus yang sama, minimasikan :
∑= )14,13,12,9,8,6,5,4,2,1,0(),,,( zyxwF
Hasil minimasi ⇒ xzwzyzyxwF ′+′′+′=),,,( .
y 00 01 11 10
00 1 1 1
01 1 1 1
11 1 1 1
10 1 1
wx yz
x
z
w
wz ′′
xz′
y′
![Page 20: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/20.jpg)
18 MATEMATIKA DISKRIT
3. Untuk kasus yang sama, minimasikan :
∑= )15,11,10,9,8,7,6,4,1(),,,( zyxwF
Hasil minimasi ⇒ xyzzwxxyzxwzyxwF ′′+′′++′=),,,( .
00 01 11 10
00 1
01 1 1 1
11 1
10 1 1 1 1
wx yz
x
y
z
w
wx′
xwz ′′
xyz zxy ′′
4. Minimasikan :
=),,,,( edcbaF
∑= )28,27,26,25,24,19,18,17,16,12,11,10,9,8,3,2,1,0(
Jawab :
![Page 21: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/21.jpg)
PETA KARNAUGH 19
Hasil minimasi ⇒ edbcedcbaF ′′+′=),,,,( .
c 000 001 011 010 110 111 101 100
00 1 1 1 1
01 1 1 1 1 1
11 1 1 1 1 1
10 1 1 1 1
ab cde
d
b
e e edb ′′ c′
a
![Page 22: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/22.jpg)
20 MATEMATIKA DISKRIT
![Page 23: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/23.jpg)
BBaabb 33
METODE QUINE McCLUSKEY
Metode alternatif untuk penyederhanaan ekspresi Boolean adalah metode Quine-McCluskey, dikembangkan oleh W.V. Quine dan E.J. McCluskey pada tahun 1950. Tahapan penyelesaian dalam metode ini adalah sebagai berikut :
Ambil kasus, fungsi Boolean ∑= )5,4,2,3(),,( zyxF ,
Langkah pertama, buat tabel berdasarkan term-term yang terdapat di dalam ekspresi Boolean di atas, secara terurut.
(a) (b)
Term x y z Term x y z
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
Langkah kedua, kelompokkan term-term tersebut berdasarkan posisi bit 1, untuk nilai posisi lainnya yang berbeda, diberikan tanda (-). Term-term yang telah dikelompokkan diberi tanda (√).
![Page 24: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/24.jpg)
22 MATEMATIKA DISKRIT
(a) (b)
Term x y z Term x y z
2 0 1 0 √ 2,3 0 1 -
3 0 1 1 √ 4,5 1 0 -
4 1 0 0 √
5 1 0 1 √
Langkah ketiga, buat tabel baru, dan seluruh term yang tidak ditandai (√) dikelompokkan di dalamnya untuk pengujian lanjutan.
Tandai dengan simbol (*) seluruh minterm yang mengandung satu (x), dan beri tanda (√) di bawah tanda (*).
minterm Term
2 3 4 5
2,3 x x
4,5 x x
* * * *
√ √ √ √
Pada tabel terlihat bahwa semua minterm telah tercakup keseluruhannya, maka tugas kita telah selesai dan fungsi minimasi yang diperoleh adalah, xyyxzyxF ′+′=),,( . Perhatikan ekspresi pembentukannya.
![Page 25: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/25.jpg)
QUINE McCLUSKEY 23
Term x y z
2,3 0 1 -
4,5 1 0 -
Nilai 0 berarti komplemen dari literal, nilai 1 berarti literal asalnya. Untuk 2,3 merepresentasikan yx′ dan untuk 4,5 merepresentasikan
. Pembuktian menggunakan peta Karnaugh diperoleh : yx ′
y
00 01 11 10
0 1 1
1 1 1
x yz
x
z
xy ′
yx ′
Kasus yang lain, minimasikan fungsi Boolean (4 variabel) berikut :
∑= )14,13,12,9,8,6,5,4,2,1,0(),,,( zyxwF , menggunakan metode Quine-McCluskey.
Langkah pertama, buat tabel berdasarkan term-term yang terdapat di dalam ekspresi Boolean di atas, secara terurut.
![Page 26: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/26.jpg)
24 MATEMATIKA DISKRIT
(a)
term w x y z
0 0 0 0 0
1 0 0 0 1
2 0 0 1 0
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
8 1 0 0 0
9 1 0 0 1
12 1 1 0 0
13 1 1 0 1
14 1 1 1 0
Langkah kedua, kelompokkan term-term tersebut berdasarkan posisi bit 1, untuk nilai posisi lainnya yang berbeda, diberikan tanda (-). Term-term yang telah dikelompokkan diberi tanda (√).
![Page 27: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/27.jpg)
QUINE McCLUSKEY 25
(a) (b)
term w x y z term w x y z
0 0 0 0 0 √ 0,1 0 0 0 -
1 0 0 0 1 √ 0,2 0 0 - 0
2 0 0 1 0 √ 0,4 0 - 0 0
4 0 1 0 0 √ 0,8 - 0 0 0
5 0 1 0 1 √ 1,5 0 - 0 1
6 0 1 1 0 √ 1,9 - 0 0 1
8 1 0 0 0 √ 2,6 0 - 1 0
9 1 0 0 1 √ 4,5 0 1 0 -
12 1 1 0 0 √ 4,6 0 1 - 0
13 1 1 0 1 √ 4,12 - 1 0 0
14 1 1 1 0 √ 5,13 - 1 0 1
6,14 - 1 1 0
8,9 1 0 0 -
9,13 1 - 0 1
12,13 1 1 0 -
Setelah sampai pada hasil di atas, maka kita perlu menguji sekali atau beberapa kali lagi, maka kita bentuk tabel (c) untuk pengelompokkan lanjutan dari tabel (b).
![Page 28: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/28.jpg)
26 MATEMATIKA DISKRIT
(b) (c)
term w x y z term w x y z
0,1 0 0 0 - √ 0,1,4,5 0 - 0 -
0,2 0 0 - 0 √ 0,1,8,9 - 0 0 -
0,4 0 - 0 0 √ 0,2,4,6 0 - - 0
0,8 - 0 0 0 √ 0,4,1,5 0 - 0 - ↵
1,5 0 - 0 1 √ 0,4,2,6 0 - - 0 ↵
1,9 - 0 0 1 √ 0,8,1,9 - 0 0 - ↵
2,6 0 - 1 0 √ 1,5,9,13 - - 0 1
4,5 0 1 0 - √ 1,9,5,13 - - 0 1 ↵
4,6 0 1 - 0 √ 4,5,12,13 - 1 0 -
4,12 - 1 0 0 √ 4,12,5,13 - 1 0 - ↵
5,13 - 1 0 1 √ 4,12,6,14 - 1 - 0
6,14 - 1 1 0 √ 8,9,12,13 1 - 0 -
8,9 1 0 0 - √
9,13 1 - 0 1 √
12,13 1 1 0 - √
Tanda (↵) bermaksud bahwa term tersebut memiliki kesamaan dengan term lainnya.
![Page 29: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/29.jpg)
QUINE McCLUSKEY 27
(c) (d)
term w x y z term w x y z
0,1,4,5 0 - 0 - √ 0,1,4,5,8,9,12,13 - - 0 -
0,1,8,9 - 0 0 - 0,4,1,5,8,9,12,13 - - 0 -
0,2,4,6 0 - - 0
0,4,1,5 0 - 0 - √
0,4,2,6 0 - - 0 ↵
0,8,1,9 - 0 0 - ↵
1,5,9,13 - - 0 1
1,9,5,13 - - 0 1 ↵
4,5,12,13 - 1 0 -
4,12,5,13 - 1 0 - ↵
4,12,6,14 - 1 - 0
8,9,12,13 1 - 0 - √
Langkah ketiga, buat tabel baru, dan seluruh term yang tidak ditandai (√) dan (↵) dikelompokkan di dalamnya untuk pengujian lanjutan.
Tandai dengan simbol (*) seluruh minterm yang mengandung satu (x), dan beri tanda (√) di bawah tanda (*).
![Page 30: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/30.jpg)
28 MATEMATIKA DISKRIT
minterm Term
0 1 2 4 5 6 8 9 12 13 14
0,1,8,9 x x x x
0,2,4,6 x x x x √
1,5,9,13 x x x x
4,5,12,13 x x x x
4,12,6,14 x x x x √
0,1,4,5,8,9,12,13 x x x x x x x x
* *
√ √ √ √ √ √
Sampai pada tahap ini, masih ada term-term yang tidak terwakilkan, yaitu : 1,5,8,9,13. Maka kita bentuk tabel baru untuk pengujian,
minterm Term
0 1 2 4 5 6 8 9 12 13 14
0,1,8,9 x x x x
0,2,4,6 x x x x √
1,5,9,13 x x x x
4,5,12,13 x x x x
![Page 31: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/31.jpg)
QUINE McCLUSKEY 29
4,12,6,14 x x x x √
0,1,4,5,8,9,12,13 x X x x x x x x √
* *
√ √ √ √ √ √ √ √ √ √ √
Kita pilih term (0,1,4,5,8,9,12,13) mewakili kolom yang tidak memiliki tanda (√).
Diperoleh, (4,12,6,14) mewakili zx ′ , (0,2,4,6) mewakili , (0,1,4,5,8,9,12,13) mewakili
zw ′′y ′ ,
Untuk mendukung hasil di atas, kita dapat menggunakan peta Karnaugh untuk pengujian,
y 00 01 11 10
00 1 1 1
01 1 1 1
11 1 1 1
10 1 1
wx yz
x
z
w
wz ′′
xz′
y′
Hasil minimasi ⇒ xzwzyzyxwF ′+′′+′=),,,( .
![Page 32: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/32.jpg)
30 MATEMATIKA DISKRIT
Kasus 1
Sederhanakan fungsi Boolean ( ) ∑= )15,14,11,10,8,2,1,0(,,, zyxwf .
Penyelesaian :
(a) (b)
Term w x y z Term w x y z
0 0 0 0 0 √ 0,1 0 0 0 -
1 0 0 0 1 √ 0,2 0 0 - 0 √
2 0 0 1 0 √ 0,8 - 0 0 0 √
8 1 0 0 0 √ 2,10 - 0 1 0 √
10 1 0 1 0 √ 8,10 1 0 - 0 √
11 1 0 1 1 √ 10,11 1 0 1 - √
14 1 1 1 0 √ 10,14 1 - 1 0 √
15 1 1 1 1 √ 11,15 1 - 1 1 √
14,15 1 1 1 - √
(c)
Term w x y z
0,2,8,10 - 0 - 0
0,8,2,10 - 0 - 0
![Page 33: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/33.jpg)
QUINE McCLUSKEY 31
10,11,14,15 1 - 1 -
10,14,11,15 1 - 1 -
minterm Term
0 1 2 8 10 11 14 15
0,1 x x √
0,2,8,10 x x x x √
10,11,14,15 x x x x √
* * * * * *
√ √ √ √ √ √ √ √
Hasil minimasi : ( ) wyzxyxwzyxwf +′′+′′′=,,, .
Kasus 2
Sederhanakan fungsi Boolean ( ) ∑= )15,11,10,9,8,7,6,4,1(,,, zyxwf .
Penyelesaian :
(a) (b)
Term w x y z Term w x y z
1 0 0 0 1 √ 1,9 - 0 0 1
4 0 1 0 0 √ 4,6 0 1 - 0
![Page 34: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/34.jpg)
32 MATEMATIKA DISKRIT
8 1 0 0 0 √ 8,9 1 0 0 - √
6 0 1 1 0 √ 8,10 1 0 - 0 √
9 1 0 0 1 √ 6,7 0 1 1 -
10 1 0 1 0 √ 9,11 1 0 - 1 √
7 0 1 1 1 √ 10,11 1 0 1 - √
11 1 0 1 1 √ 7,15 - 1 1 1
15 1 1 1 1 √ 11,15 1 - 1 1
(c)
Term w x y z
8,9,10,11 1 0 - -
8,10,9,11 1 0 - -
minterm Term
1 4 6 7 8 9 10 11 15
1,9 x x √
4,6 x x √
6,7 x x
7,15 x x
![Page 35: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/35.jpg)
QUINE McCLUSKEY 33
11,15 x x
8,9,10,11 x x x x √
* * * *
√ √ √ √ √ √ √
minterm Term
1 4 6 7 8 9 10 11 15
1,9 x x √
4,6 x x √
6,7 x x
7,15 x x √
11,15 x x
8,9,10,11 x x x x √
* * * *
√ √ √ √ √ √ √ √ √
Hasil minimasi : ( ) xwxyzzxwzyxzyxwf ′++′′+′′=,,, .
![Page 36: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/36.jpg)
34 MATEMATIKA DISKRIT
Kasus 3
Sebagai ketua panitia bazaar di RW setempat, ibu Soffie mengusulkan untuk menjual kue bolu. Dari anggota ibu PKK RW, beberapa orang menyatakan kesediaannya untuk menyumbangkan bahan bakunya. Berikut adalah daftar nama-nama penyumbang beserta bahan baku yang disumbangkan.
Terigu Susu Butter Gula Telur
Susi
Debi
Beti
Tuti
Ruli
Kemudian ibu Soffie menyuruh putrinya, Yovie, untuk mengumpulkan bahan-bahan tersebut. Bantulah Yovie dalam mencari kombinasi penyumbang siapa saja yang perlu dikunjungi, dengan catatan seluruh bahan baku lengkap terkumpul dan sesedikit mungkin yang dikunjungi.
Solusi : Asumsikan bahwa inisial s, d, b, t, r digunakan untuk mewakili nama-nama yang terdaftar pada tabel. Berdasarkan tabel, untuk mendapatkan terigu, Yovie harus mengunjungi Susi atau Beti, atau bila dinotasikan dalam ekspresi boolean adalah : (s + b). Sedangkan untuk mendapatkan susu, Yovie harus mengunjungi Beti atau Tuti atau Ruli, atau (b+t+r). Untuk butter, gula, dan telur masing-masing ekspresi booleannya adalah (s + d + r), (d + r), t. Sehingga ekspresi Boolean untuk mendapatkan kelima bahan adalah :
trdrdsrtbbsrtbdsf ⋅+⋅++⋅++⋅+= )()()()(),,,,(
Dan bila ekspresi Boolean ini kita ubah ke dalam bentuk kanonik minterm, akan kita dapatkan:
![Page 37: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/37.jpg)
QUINE McCLUSKEY 35
),,,,( rtbdsf btrdstrbdsdbtrsrdbtsbtrds ′+′′+′+′′+′′=
sdbtrrsdbttrbsdrtbsd +′+′+′′+
Untuk mendapatkan kombinasi penyumbang yang paling minimum, kita harus mencari bentuk paling sederhana dari fungsi Boolean , untuk itu di sini kita gunakan metode Quine-McCluskey.
f
minterm String minterm String
1 btrds ′' 00111 (1,6) btrd ′ -0111
2 rdbts ′' 01110 (2,8) rdbt ′ -1110
3 rtbsd ′′ 11010 (3,7) tbsd ′ 1101-
4 trbds ′′ 10011 (4,7) trbs ′ 1-011
5 dbtrs' 01111 (5,9) dbtr -1111
6 btrds ′ 10111 (6,9) sbtr 1-111
7 trbsd ′ 11011 (7,9) sdtr 11-11
8 rsdbt ′ 11110 (8,9) sdbt 1111-
9 sdbtr 11111 -
minterm String
(1,5,6,9) btr --111
(2,5,8,9) dbt -111-
(3,7,8,9) sdt 11-1-
![Page 38: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/38.jpg)
36 MATEMATIKA DISKRIT
(4,6,7,9) str 1--11
Diperoleh ( ) strsdtdbtbtrrtbdsf +++=,,,, , dengan kata lain kombinasi yang bisa dikunjungi oleh Yovie untuk mendapatkan seluruh bahan : Beti-Tuti-Ruli, atau Debi-Beti-Tuti, atau Susi-Debi-Tuti, atau Susi-Tuti-Ruli.
Kasus 3 diambil dari buku Pengantar Logika Matematika karya Setiadi Rachmat, Penerbit Informatika, ISBN : 979-3338-35-0. Kasus 1 dan 2 diambil dari buku Matematika Diskrit karya Rinaldi Munir, Penerbit Informatika, ISBN 979-96446-3-1.
Penjelasan untuk kasus 3, merubah ekspresi Boolean berikut, trdrdsrtbbsrtbdsf ⋅+⋅++⋅++⋅+= )()()()(),,,,( ke dalam
bentuk kanonik minterm (SOP).
Bentuk tabel kebenaran berikut :
s d
b t r bs +
rtb ++ rds ++ rd + f
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1
![Page 39: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/39.jpg)
QUINE McCLUSKEY 37
0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Term-term yang diambil merepresentasikan nilai 1=f . Perhatikan pada tabel nilai sangat mempengaruhi nilai daripada . t f
Kasus 1
Sebagai seorang manajer pelatih klub sepakbola AC Milan anda diminta untuk membeli beberapa pemain dengan ketentuan pembelian pemain harus mencakup keseluruhan formasi posisi yang dibutuhkan oleh klub dan pengeluaran biaya belanja sehemat mungkin. Tentukan kombinasi pemain-pemain yang akan anda beli dengan pengeluaran biaya seminimum mungkin.
Petunjuk : Pilih para pemain anda secara bebas dengan syarat jumlah biaya keseluruhan pemain tidak melebih Rp. 40 Milyar (Biaya belanja pemain yang disediakan klub).
Daftar pemain yang masuk bursa transfer adalah sebagai berikut :
![Page 40: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/40.jpg)
38 MATEMATIKA DISKRIT
Defender
Wings
Midfield
Attacking
Midfield
Forward
$
Cannavaro 10 Beckham 10 Zidane 15 Del Piero 15 Kaka 15 Ronaldinho 15 Inzaghi 10 Gattuso 15 Pirlo 10 Xavi 10 Maldini 10
Kasus 2
Jika anda akan memilih isteri dari beberapa calon yang akan dijodohkan kepada anda, dengan berbagai kriteria berikut :
Agama Cantik Keturunan Kaya
Intan Fitri Lisa Rani
Maka tentukan urutan pasangan calon yang akan anda pilih dari berbagai nama pada tabel di atas.
![Page 41: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/41.jpg)
BBaabb 44
KONVOLUSI
4.1 Pondasi konvolusi
Konvolusi 2 buah fungsi ( )xf dan didefinisikan sebagai : ( )xg
( ) ( ) ( ) ( ) ( )∫∞
∞−
−≅⊗= daaxgafxgxfxh
notasi merupakan operator konvolusi. Untuk fungsi diskrit konvolusi didefinisikan sebagai,
⊗
( ) ( ) ( ) ( ) ( )∑∞
−∞=
−≅⊗=a
axgafxgxfxh
di mana merupakan kernel konvolusi atau kernel filter. ( )xg
Untuk fungsi dua dimensi, operasi konvolusi didefinisikan sebagai : (untuk fungsi kontinu)
( ) ( ) ( ) ( ) ( )∫ ∫∞
∞−
∞
∞−
−−≅⊗= dadbbyaxgbafyxgyxfyxh ,,,,,
![Page 42: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/42.jpg)
40 PENGOLAHAN CITRA
dan untuk fungsi diskrit, didefinisikan sebagai :
( ) ( ) ( ) ( ) (∑∑∞
∞−
∞
∞−
−−≅⊗= byaxgbafyxgyxfyxh ,,,,, )
Fungsi filter ( )yxg , disebut juga filter konvolusi, mask konvolusi, kernel konvolusi, atau template. Ilustrasi konvolusi diperlihatkan pada gambar 4.1.
0x 1x 2x
3x 4x 5x
6x 7x 8x
A B C
D E F
G H I
template ( )jif ,
Image
( ) 876543210, IxHxGxFxExDxCxBxAxjif ++++++++=
Gambar 4.1 Ilustrasi Konvolusi
![Page 43: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/43.jpg)
KONVOLUSI 41
Perhatikan kasus berikut, citra dikonvolusi
menggunakan template akan menghasilkan citra yang baru
dengan nilai-nilai = .
44111333123441143311
⎥⎦
⎤⎢⎣
⎡1001
******7723*7742*6752
Template–template yang sering muncul penggunaannya dalam pengolahan citra (meminimalisir noise pada citra, edge detection, filtering, dan lain – lain) adalah template klasikal 3x3. Template yang diaplikasikan sebagai low-pass filter adalah,
111111111
Pengaplikasian untuk high-pass filter digunakan template
010141
010
−−−
−
Template yang lain yang sering juga digunakan untuk melakukan smoothing citra adalah,
1313163131
![Page 44: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/44.jpg)
42 PENGOLAHAN CITRA
Tabel 4.1 memperlihatkan operasi high-pass filter dan low-pass filter pada suatu citra yang memiliki nilai-nilai intensitas pixel berikut :
0000001110016100111001110011100111000000
Tabel 4.1
Citra Sesudah high-pass Sebelum low-pass
0000001110016100111001110011100111000000
…………………
2424204
151101101212
−−−
−
…………………
9119111411111411696696464
…………………
Kasus yang lain, perhatikan tabel 4.2.
![Page 45: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/45.jpg)
KONVOLUSI 43
Tabel 4.2
Citra
Sesudah konvolusi
dengan 1111 −−
Sesudah konvolusi
dengan 1111
−−
⎥⎦
⎤⎢⎣
⎡ −−1111
+ ⎥⎦
⎤⎢⎣
⎡−−
1111
333300333300333300333300000000000000000000
000000000000000666300000000000
000600006000060000300000000000
000600006000060666600000000000
4.2 Perancangan program
Untuk Perancangan program konvolusi menggunakan Delphi dapat kita lakukan langkah-langkah berikut :
1. Jalankan Delphi.
![Page 46: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/46.jpg)
44 PENGOLAHAN CITRA
2. Tambahkan icon Panel1, Panel2, Image1, Image2, MainMenu1 dan OpenPictureDialog pada form :
Untuk Panel1, Nilai-nilai property pada object inspector adalah :
Bevellnner bvLowered
BevelOuter bvLowered
Untuk Image1, icon Image1 letakkan di atas Panel1 pada Form1. Nilai-nilai property pada object inspector adalah :
Stretch True
Untuk Panel2, Nilai-nilai property pada object inspector adalah :
Bevellnner bvLowered
![Page 47: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/47.jpg)
KONVOLUSI 45
BevelOuter bvLowered
Untuk Image2, icon Image2 letakkan di atas Panel2 pada Form1. Nilai-nilai property pada object inspector adalah :
Stretch True
Untuk MainMenu1, klik 2x pada icon MainMenu1, sehingga muncul tampilan :
Atur sedemikian hingga, agar tampilan menjadi :
![Page 48: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/48.jpg)
46 PENGOLAHAN CITRA
File
Open Konvolusi
Image Processing
Klik 2x pada MainMenu1→File Open, setelah muncul halaman editor, tuliskan listing berikut :
→
if not OpenPictureDialog1.Execute then exit else begin gambar := TBitmap.Create; gambar.LoadFromFile(OpenPictureDialog1.filename); Form1.Caption:= 'Image Processing - '+ ExtractFileName
(OpenPictureDialog1.Filename); end;
![Page 49: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/49.jpg)
KONVOLUSI 47
if gambar.PixelFormat <> pf24bit then gambar.PixelFormat := Pf24bit;
Image1.Picture.Bitmap := gambar;
Kembali ke form1, Klik 2x pada MainMenu1 Image Processing→ Konvolusi, setelah muncul halaman editor, tuliskan listing berikut :
→
procedure TForm1.Invert1Click(Sender: TObject); const konvolusi : array[0..1,0..2,0..2] of smallint = (((1,1,1),(1,1,1),(1,1,1)), ((0,0,0),(0,0,0),(0,0,0))); var row : array[0..8] of pbytearray; col : pbytearray; x,y : smallint; i,j,k,p : smallint; image : tbitmap; sum,jum : longint; begin P:=-120; image := tbitmap.Create; Image.Assign(gambar); for y:=1 to gambar.Height-2 do begin for i:=-1 to 1 do row[i+1]:= Image.ScanLine[y+i]; col := gambar.ScanLine[y]; x:=3; repeat sum := 0; for i:=-1 to 1 do for j:=-1 to 1 do sum:=sum+(konvolusi[0,i+1,j+1]*row[i+1,x+j*3]); jum:=0; for i:=-1 to 1 do for j:=-1 to 1 do jum:=jum+(konvolusi[1,i+1,j+1]*row[i+1,x+j*3]); sum := (sum + jum)+p;
![Page 50: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/50.jpg)
48 PENGOLAHAN CITRA
if sum>255 then sum:=255; if sum<0 then sum:=0; for k:=0 to 2 do col[x+k]:=sum; inc(x,3); until x>=3*(gambar.Width-4); end; Image2.Picture.bitmap := gambar; gambar.SaveToFile('Fadlisyah.bmp'); Image.free; end;
3. Eksekusikan program (F9).
Gambar 4.2 Hasil eksekusi citra “Zidane”
![Page 51: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/51.jpg)
KONVOLUSI 49
Dengan sedikit merubah nilai-nilai pada template, eksekusi program akan menghasilkan output sebagai berikut :
Gambar 4.3 Hasil eksekusi citra “Zidane” dengan template
const konvolusi : array[0..1,0..2,0..2] of smallint = (((1,0,1),(1,0,1),(1,0,1)), ((0,0,0),(0,0,0),(0,0,0)));
![Page 52: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/52.jpg)
50 PENGOLAHAN CITRA
![Page 53: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/53.jpg)
BBaabb 55
BILANGAN FLOATING POINT
Bilangan floating-point, berisikan 2 bagian, yaitu mantisa (signifikan atau pecahan), dan eksponen. Gambar 5.1 memperlihatkan bentuk 4 byte dan 8 byte dari bilangan floating-point yang disimpan di dalam sistem Intel. Bilangan floating-point atau bilangan real 4 byte disebut single-precision, dan Bilangan floating-point atau bilangan real 8 byte disebut double-precision.
31 30 23 22 0
S Eksponen Mantisa
(a)
63 62 52 51 0
S Eksponen Mantisa
(b)
Gambar 5.1 (a) Presisi tunggal menggunakan bias 7FH, dan (b) Presisi
Ganda menggunakan bias 3FFH
![Page 54: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/54.jpg)
52 MATEMATIKA DISKRIT
Mantisa 24-bit memiliki bit satu yang tersembunyi (implied), yang memungkinkan mantisa untuk mewakili 24-bit walau hanya disimpan 23-bit. Bit yang disembunyikan adalah bit pertama dari bilangan yang dinormalisasi. Pada saat menormalisasi bilangan, bit ini diatur sehingga nilainya sekurang-kurangnya 1, tetapi kurang dari 2. sebagai contoh, jika 12 diubah ke biner ( )21102 , maka dinormalisasi dan hasilnya . Bit satu yang terdapat di depan tanda koma akan disembunyikan, atau tidak disimpan di dalam bagian mantisa.
321,1 ×
Eksponen disimpan dalam eksponen terbias (biased exponent). Untuk presisi tunggal, Bias 7FH (127) akan dijumlahkan ke eksponen sebelum disimpan ke dalam tempat eksponen, dan untuk presisi ganda sebesar 3FFH (1023).
Ada 2 pengecualian mengenai aturan-aturan yang diterapkan mengenai bilangan floating-point. Angka 0,0 disimpan semuanya sebagai nol. Bilangan tak hingga disimpan dalam eksponen sebagai satu, dan dalam mantisa semuanya sebagai nol. Bit tanda menunjukkan bilangan tak hingga tersebut bernilai positif atau negatif.
Kasus 1
Bagaimana bilangan +12 disimpan dalam bentuk presisi tunggal.
Penyelesaian :
Desimal Biner Normal Tanda
+12 1100 321,1 × 0
s Eksponen
0 1 0 0 0 0 0 1 0
31
30
29
28
27
26
25
24
23
![Page 55: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/55.jpg)
FLOATING POINT 53
Mantisa
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
22
21
20
19
18
17
16
15
14
13
12
11
10
9 8 7 6 5 4 3 2 1 0
Penjelasan :
+ = 0, pangkat pada normalisasi adalah 3 atau dalam bentuk biner sama dengan . Selanjutnya untuk presisi tunggal eksponen dapat diperoleh dengan menambahkan +7FH =
211
211 22 111111111 + = . 210000010
Kasus 2
Bagaimana bilangan -12 disimpan dalam bentuk presisi tunggal.
Penyelesaian :
Desimal Biner Normal Tanda
-12 1100 - 321,1 × 1
s Eksponen
1 1 0 0 0 0 0 1 0
31
30
29
28
27
26
25
24
23
Mantisa
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
22
21
20
19
18
17
16
15
14
13
12
11
10
9 8 7 6 5 4 3 2 1 0
![Page 56: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/56.jpg)
54 MATEMATIKA DISKRIT
Kasus 3
Bagaimana bilangan +100 disimpan dalam bentuk presisi tunggal.
Penyelesaian :
Desimal Biner Normal Tanda
+100 1100100 621001,1 × 0
s Eksponen
0 1 0 0 0 0 1 0 1
31
30
29
28
27
26
25
24
23
Mantisa
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22
21
20
19
18
17
16
15
14
13
12
11
10
9 8 7 6 5 4 3 2 1 0
Penjelasan :
Konversi bilangan 100 menjadi bilangan biner adalah sebagai berikut :
100/2 Sisa 0 3/2 Sisa 1
50/2 Sisa 0 1/2 Sisa 1
25/2 Sisa 1 0
12/2 Sisa 0
6/2 Sisa 0 1100100
![Page 57: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/57.jpg)
FLOATING POINT 55
Kasus 4
Bagaimana bilangan -1,75 disimpan dalam bentuk presisi tunggal.
Penyelesaian :
Desimal Biner Normal Tanda
-1,75 1,11 - 0211,1 × 1
s Eksponen
1 0 1 1 1 1 1 1 1
31
30
29
28
27
26
25
24
23
Mantisa
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22
21
20
19
18
17
16
15
14
13
12
11
10
9 8 7 6 5 4 3 2 1 0
Penjelasan :
Konversi bilangan -1,75 menjadi bilangan biner adalah sebagai berikut: (kita ambil 0,75, 1 desimal = 1 biner), sampai di sini kita sudah dapat menyatakan sebagai 1,…
0,75 x 2
0,5 x 2 Digit 1
1,0 Digit 1
1,11
![Page 58: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/58.jpg)
56 MATEMATIKA DISKRIT
Kasus 5
Bagaimana bilangan +0,25 disimpan dalam bentuk presisi tunggal.
Penyelesaian :
Desimal Biner Normal Tanda
+0,25 0,01 22,1 −× 0
s Eksponen
0 0 1 1 1 1 1 0 1
31
30
29
28
27
26
25
24
23
Mantisa
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22
21
20
19
18
17
16
15
14
13
12
11
10
9 8 7 6 5 4 3 2 1 0
Penjelasan :
Konversi bilangan +0,25 menjadi bilangan biner adalah sebagai berikut: (kita ambil 0,25, 0 desimal = 0 biner), sampai di sini kita sudah dapat menyatakan sebagai 0,…
0,25 x 2
0,5 x 2 Digit 0
1,0 Digit 1
0,01
![Page 59: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/59.jpg)
FLOATING POINT 57
Eksponen terbias kita peroleh dengan menjumlahkan :
7FH 1111111
-2 -0000010
1111101
Berbagai kasus yang lain, ditinggalkan untuk ujicoba para mahasiswa,
Andai diketahui :
Ujicoba 1
s Eksponen
0 1 0 0 0 0 0 0 0
31
30
29
28
27
26
25
24
23
Mantisa
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
22
21
20
19
18
17
16
15
14
13
12
11
10
9 8 7 6 5 4 3 2 1 0
Maka ubahlah bilangan floating-point di atas ke dalam bilangan desimal.
Ujicoba 2
s Eksponen
1 0 1 1 1 1 1 1 1
31
30
29
28
27
26
25
24
23
![Page 60: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/60.jpg)
58 MATEMATIKA DISKRIT
Mantisa
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
22
21
20
19
18
17
16
15
14
13
12
11
10
9 8 7 6 5 4 3 2 1 0
Maka ubahlah bilangan floating-point di atas ke dalam bilangan desimal.
Ujicoba 3
s Eksponen
0 1 0 0 0 0 0 1 0
31
30
29
28
27
26
25
24
23
Mantisa
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
22
21
20
19
18
17
16
15
14
13
12
11
10
9 8 7 6 5 4 3 2 1 0
Maka ubahlah bilangan floating-point di atas ke dalam bilangan desimal.
Keseluruhan bahan dan berbagai kasus yang menyertai bab ini, disadur dari buku Brey, Barry B. 2000. Mikroprosesor Intel 8086/8088, 80186/80188, 80286, 80386, 80486, Pentium, dan Pentium-Pro : Arsitektur, Pemrograman, Antarmuka (Edisi kelima jilid 1), Penerbit Erlangga, yang diterjemahkan oleh Ir. N.R. Poespawati, M.T.
![Page 61: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/61.jpg)
BBaabb 66
KODE HAMMING
Sistem memori semikonduktor dapat mengalami kegagalan (error). Error-error ini dapat dikategorikan sebagai kegagalan yang berat dan error ringan. Kegagalan berat merupakan kerusakan isi yang permanen sehingga sel memori yang mengalaminya tidak dapat lagi digunakan untuk menampung data. Error-error berat dapat disebabkan oleh kesalahan penggunaan, dan kerusakan yang berasal dari pabrik. Error ringan adalah kejadian yang random dan tidak merusak yang mengubah isi sebuah sel memori atau lebih, tanpa merusak memori. Error ringan dapat disebabkan oleh masalah catu daya atau partikel-partikel alpha. Partikel-partikel ini adalah hasil dari peluruhan radioaktif dan merupakan akibat adanya inti radioaktif dalam jumlah kecil yang secara alami terdapat pada seluruh materi. Baik error berat maupun ringan merupakan hal yang tidak diinginkan, hampir semua sistem memori utama modern memiliki logik untuk mendeteksi dan mengoreksi error-error tersebut.
Gambar 6.1 menjelaskan secara umum tentang proses yang terjadi. Ketika data dibaca ke dalam memori, kalkulasi, yang digambarkan sebagai fungsi , dibentuk dengan data tersebut untuk menghasilkan kode. Baik data maupun kode itu disimpan. Jadi, apabila sebuah word M bit data akan disimpan, dan kode memiliki panjang K bit, maka ukuran aktual word yang disimpan adalah M + K bit.
f
![Page 62: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/62.jpg)
60 MATEMATIKA DISKRIT
Ketika word yang sebelumnya tersimpan akan dibaca, maka kode digunakan untuk mendeteksi dan mengoreksi error yang mungkin terjadi. Bit-bit kode K yang baru dihasilkan dari M bit data dan dibandingkan dengan bit kode yang diambil. Perbandingan tersebut akan menghasilkan salah satu dari tiga kemungkinan :
Tidak terdapat error. Data bit yang diperhatikan akan dikirimkan.
Terjadi error, dan dimungkinkan untuk mengoreksinya. Bit-bit data dan bit-bit koreksi error dimasukkan ke korektor, yang menghasilkan bit-bit M yang dikoreksi akan dikirimkan.
Terjadi error, namun tidak dimungkinkan untuk mengoreksinya. Keadaan ini akan dilaporkan.
Kode yang beroperasi dengan cara seperti ini disebut sebagai error-correcting code. Sebuah kode dicirikan oleh sejumlah error bit dalam word yang dapat dikoreksi dan dideteksinya.
Kode perbaikan error yang paling sederhana adalah kode Hamming yang diciptakan oleh Richard Hamming di Laboratorium Bell. Gambar 6.2 menggunakan diagram Venn untuk menjelaskan penggunaan kode ini bagi word 4 bit (M = 4). Dengan tiga buah lingkaran yang berpotongan, terdapat tujuh kompartemen. Kita akan memberikan 4 buah bit data ke kompartemen yang terletak di tengah (Gambar 6.2 a). Kompartemen sisanya diisi dengan apa yang kita sebut bit paritas. Setiap bit paritas dipilih sehingga bilangan 1 di dalam lingkaran berjamlah genap (Gambar 6.2 b). Jadi, karena lingkaran A terdiri dari tiga buah data bilangan l , maka bit paritas di dalam lingkaran itu disetel menjadi l. Sekarang, apabila suatu error mengubah salah satu bit data (Gambar 6.2 c), maka error itu akan dengan mudah ditemukan. Dengan memeriksa bit paritas, cacat-cacat dapat ditemukan pada lingkaran A dan C namun tidak pada lingkaran B. Hanya salah satu dari kompartemen
![Page 63: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/63.jpg)
KODE HAMMING 61
berada pada A dan C namun tidak pada B. Karena itu error dapat dikoreksi dengan mengubah bit tersebut.
Untuk menjelaskan konsep tersebut, kita akan membuatlah kode yang dapat mendeteksi dan mengoreksi error bit tunggal di dalam word 8-bit. Untuk memulainya, kita tentukan panjang kode seharusnya. Sehubungan dengan Gambar 6.1 logik perbandingan menerimanya sebagai input dua nilai K bit. Perbandingan bit demi bit dilakukan dengan memperhatikan exclusive-or kedua input itu. Hasilnya disebut sebagai syndrome word. Jadi, setiap bit syndrome sama dengan 0 atau 1 apabila terdapat atau tidak cocok dalam posisi bit kedua input tersebut.
Error Signal
Corrector
Compare
Memory f
f
Data Out
Data In
M
M M K
K K
Gambar 6.1 Fungsi kode koreksi error
![Page 64: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/64.jpg)
62 MATEMATIKA DISKRIT
1
1
1 0 1
1
1 0
1
0
0
1
1
0 0
1
0
0 1
1
0 0
1
0
0
(a) (b)
(c) (d)
Gambar 6.2 Error-correcting code dari Hamming
Dengan demikian syndrome word mempunyai lebar K bit dan memiliki range yang berada di antara 0 dan K2 12 −K . Nilai 0 berarti bahwa tidak terdeteksi error, yang menyisakan 12 −K buah nilai untuk mengindikasikan bit mana yang mengalami error, bila terdapat error. Karena suatu error dapat terjadi pada sembarang M bit data atau K bit check, maka syarat yang harus dipenuhi,
KMK +≥−12
![Page 65: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/65.jpg)
KODE HAMMING 63
Mekanismenya adalah, atur layout bit-bit data dan bit-bit check
Bit position Position number Check bit Data bit
12 1100 M8
11 1011 M7
10 1010 M6
9 1001 M5
8 1000 C8
7 0111 M4
6 0110 M3
5 0101 M2
4 0100 C4
3 0011 M1
2 0010 C2
1 0001 C1
Bit-bit check dihitung sebagai berikut :
C1 = M1⊕M2⊕M4⊕M5⊕M7 1,2,4,5,7
C2 = M1⊕M3⊕M4⊕M6⊕M7 1,3,4,6,7
C4 = M2⊕M3⊕M4⊕M8 2,3,4,8
C8 = M5⊕M6⊕M7⊕M8 5,6,7,8
![Page 66: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/66.jpg)
64 MATEMATIKA DISKRIT
Kita akan menguji pola ini, apakah efektif untuk menguji kesalahan yang terjadi.
Kasus :
Andaikan word input 8-bit sama dengan 00111001, dengan bit data M1 berada pada posisi paling kanan.
M8 M7 M6 M5 M4 M3 M2 M1
0 0 1 1 1 0 0 1
Perhitungannya adalah sebagai berikut :
C1 = M1⊕M2⊕M4⊕M5⊕M7 1⊕0⊕1⊕1⊕0=1
C2 = M1⊕M3⊕M4⊕M6⊕M7 1⊕0⊕1⊕1⊕0=1
C4 = M2⊕M3⊕M4⊕M8 0⊕0⊕1⊕0=1
C8 = M5⊕M6⊕M7⊕M8 1⊕1⊕0⊕0=0
Seandainya terjadi kesalahan pada bit data ketiga, berubah dari 0 menjadi 1. Maka kalkulasinya adalah :
M8 M7 M6 M5 M4 M3 M2 M1
0 0 1 1 1 1 0 1
C1 = M1⊕M2⊕M4⊕M5⊕M7 1⊕0⊕1⊕1⊕0=1
C2 = M1⊕M3⊕M4⊕M6⊕M7 1⊕1⊕1⊕1⊕0=0
C4 = M2⊕M3⊕M4⊕M8 0⊕1⊕1⊕0=0
C8 = M5⊕M6⊕M7⊕M8 1⊕1⊕0⊕0=0
![Page 67: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/67.jpg)
KODE HAMMING 65
Bit-bit check yang baru dibandingkan dengan bit-bit check yang lama, maka syndrome word yang terbentuk adalah :
C8 C4 C2 C1
0 1 1 1
⊕ 0 0 0 1
0 1 1 0
0110 biner setara dengan nilai 6 desimal, yang mengindikasikan bahwa posisi bit 6 mengalami error, atau bit data 3 mengalami error.
Keseluruhan isi materi bab ini disadur dari Stalling, William. 1998. Organisasi dan Arsitektur Komputer : Perancangan Kinerja (jilid 1), Prentice Hall yang diterjemahkan oleh PT Prenhallindo, Jakarta.
![Page 68: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/68.jpg)
66 MATEMATIKA DISKRIT
![Page 69: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/69.jpg)
B
)
Baabb 77
GRAPH
Graph terdiri dari sebuah himpunan tidak kosong terbatas dari berbagai verteks dan edge yang memuat sebarang himpunan bagian dari berbagai pasangan
( EVG ,=
{ }{ }wvVwvwv ≠∈ ,,:, . Edge { }wv, dapat diekspresikan sebagai atau dan dinyatakan sebagai relasi verteks ke verteks , di mana disebut titik-titik ujung dari edge .
vw wvv w wv,
vw
Contoh, andaikan ( )EVG ,= merupakan graph dengan sekumpulan verteks V={Meryl Streep, Dustin Hoffman, Jeremy Irons, Anne Bancroft, Robert Redford} dan asumsikan pula sekumpulan edge didefinisikan sebagai :
VwvvwE ∈= ,:{ telah membuat film bersama sebelum 1992 }.
Maka ilustrasi yang mungkin adalah sebagai berikut : G
Jeremy Irons Robert Redford Anne Bancroft
Dustin Hoffman Meryl Streep
![Page 70: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/70.jpg)
68 MATEMATIKA DISKRIT
Derajat verteks Vv∈ di dalam graph ( )EVG ,= merupakan jumlah verteks yang terhubung ke , dinyatakan sebagai v vδ . Ambil kasus berikut :
7
Dapat dilihat bahwa graph ( )EVG ,= memiliki 11 verteks dan 10 edge., dengan derajat verteks 7 adalah 4, .47 =δ Jumlah keseluruhan derajat adalah 20, yang mana dua kali jumlah edge.
Kasus : berapa banyak tree yang dapat dibentuk berdasarkan sekumpulan verteks { }5,4,3,2,1 dengan derajat verteks 31=δ ,
22 =δ , 13 =δ , 14 =δ , 15 =δ ?
Solusi :
5 5
3 2 1 4 3 1 2 4
![Page 71: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/71.jpg)
GRAPH 69
5
1
3 2
4
Keterangan : tree merupakan bagian graph yang terstruktur.
Teorema : andaikan , , merupakan bilangan bulat positif dengan jumlah
nddd ,....,, 21 2≥n22 −n . Maka jumlah tree pada himpunan verteks
dengan derajat verteks { n,...,2,1 } nn dd == δδ ,...,1 1 adalah
( )( ) ( ) ( )!1!....1!1
!2
21 −−−−
ndddn
Bukti : kita tinggalkan sebagai tugas mahasiswa.
Teorema : (Cayley) untuk , jumlah tree pada verteks 2≥n { }n,...,2,1 adalah . 2−nn
Bukti : kita tinggalkan sebagai tugas mahasiswa.
Kasus : ada 16 tree pada himpunan verteks { }4,3,2,1 . Ada 16 pasang pasangan bilangan bulat yang berbentuk , di mana a dan dipilih secara bebas dari himpunan verteks
ab b{ }4,3,2,1 , dan oleh karenanya kita
dapat menamakan setiap tree yang ditemukan dengan 16 pasang bilangan bulat di atas berdasarkan ketentuan. (alasan penamaan tree akan dijelaskan kemudian )
Solusi :
![Page 72: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/72.jpg)
70 MATEMATIKA DISKRIT
Algoritma Prüfer
Algoritma Prüfer digunakan untuk menamakan tree, dan nama yang diperoleh disebut sebagai kode Prüfer.
Jika diberikan sebuah tree dengan himpunan verteks { }n,...,2,1 , maka untuk menentukan kode Prüfer adalah,
1. Temukan verteks yang terkecil berderajat 1, katakan . Andaikan merupakan verteks yang dihubungkan ke .
vw v
2. Nyatakan w dan buang verteks v dan edge . vw3. Jika tree yang terbentuk masih memiliki lebih dari satu edge,
ulangi langkah (1), sebaliknya jika tidak, maka algoritma berhenti.
![Page 73: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/73.jpg)
GRAPH 71
Contoh kasus : aplikasikan algoritma Prüfer untuk menamakan tree T yang diilustrasikan berikut :
3
1
2
6
4 5
3
4 5
6
2
T
2
3
2
5
3
2
23
233
6 6
2 2332
6
![Page 74: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/74.jpg)
72 MATEMATIKA DISKRIT
Seandainya kasus yang terjadi adalah kebalikan dari kasus di atas, kode Prüfer diketahui, dan kita ingin mengkonstruksikan tree dari kode Prüfer tersebut, maka algoritma inverse berikut kita gunakan.
Algoritma : diberikan suatu daftar angka-angka yang secara bebas dipilih dari
21... −naa{ }n,...,2,1 , untuk menemukan tree T menggunakan
daftar kode Prüfer adalah :
1. Nyatakan daftar pertama , daftar kedua dan mulai dengan himpunan verteks
21... −naa n,...,2,1{ }n,...,2,1 dan sekumpulan
kosong berbagai edge.
2. Temukan angka terkecil, katakan i , yang hadir pada daftar kedua dan tidak hadir pada daftar pertama. Hapus leading-entry pada daftar pertama, katakan , hapus i dari daftar kedua dan tambahkan edge ij ke himpunan edge.
j
3. Jika terdapat sebarang angka yang masih tertinggal dalam daftar pertama, maka ulangi langkah (2). Sebaliknya, jika daftar pertama kosong, maka daftar kedua akan terdiri dari dua angka. Tambahkan satu edge terakhir ke himpunan edge yang terdiri dari dua angka yang dihubungkan bersama; kemudian algoritma berhenti.
Contoh kasus : rekonstruksikan tree T dengan kode Prüfer 2332?.
Solusi :
2332 123456 Tambahkan edge 12
Keterangan : mulai dari angka terkecil, pada kolom pertama terlihat bahwa angka terkecil adalah 2, dan angka terkecil yang tidak terdapat pada kolom pertama adalah 1.
Maka kita bentuk edge 12,
![Page 75: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/75.jpg)
GRAPH 73
2
1
Buang angka 2 pada kolom pertama dan angka 1 pada kolom kedua sehingga :
332 23456 Tambahkan edge 34
Keterangan : mulai dari angka terkecil, pada kolom pertama terlihat bahwa angka terkecil adalah 3, dan angka terkecil yang tidak terdapat pada kolom pertama adalah 4.
Maka kita bentuk edge 34,
4
1
3
2
Buang angka 3 pada kolom pertama dan angka 4 pada kolom kedua sehingga :
![Page 76: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/76.jpg)
74 MATEMATIKA DISKRIT
32 2356 Tambahkan edge 35
Keterangan : mulai dari angka terkecil, pada kolom pertama terlihat bahwa angka terkecil adalah 3, dan angka terkecil yang tidak terdapat pada kolom pertama adalah 5.
Maka kita bentuk edge 35,
3
4 5
2
1
Buang angka 3 pada kolom pertama dan angka 5 pada kolom kedua sehingga :
2 236 Tambahkan edge 23
Keterangan : mulai dari angka terkecil, pada kolom pertama terlihat bahwa angka terkecil adalah 2, dan angka terkecil yang tidak terdapat pada kolom pertama adalah 3.
Maka kita bentuk edge 23,
![Page 77: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/77.jpg)
GRAPH 75
3
4 5
2
1
Buang angka 2 pada kolom pertama dan angka 3 pada kolom kedua sehingga :
- 26 Tambahkan edge 26
Maka kita bentuk edge 26,
3
4 5
6
2
1
![Page 78: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/78.jpg)
76 MATEMATIKA DISKRIT
Kasus yang ditinggalkan untuk mahasiswa :
Konstruksikan sebuah graph ( )EVG ′′=′ , yang memuat verteks V = { seluruh negara di kawasan Asia } dan edge yang didefinisikan
′E ′=
{vw : v,w memiliki batas negara yang sama}. Setelah berhasil diselesaikan, kasus diperluas untuk kawasan-kawasan wilayah lainnya.
![Page 79: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/79.jpg)
DAFTAR PUSTAKA
Brey, Barry B. 2000. Mikroprosesor Intel 8086/8088, 80186/80188,
80286, 80386, 80486, Pentium, dan Pentium-Pro : Arsitektur, Pemrograman, Antarmuka (Edisi kelima jilid 1), Penerbit Erlangga.
Bryant, Victor. 1993. Aspect of Combinatorics : A Wide-Ranging Introduction, Cambridge University Press.
Fadlisyah, S.Si., 2007. Computer Vision & Pengolahan Citra., Penerbit Andi Yogyakarta.
Fadlisyah, S.Si., 2007. Pengantar Grafika Komputer., Penerbit Andi Yogyakarta.
Gonzalez, Rafael C., dan Wintz, Paul. 1987. Digital Image Processing, Addison Wesley
Hearn, D. dan Baker, MP. 1994. Computer Graphics. Englewood Cliffs, New Jersey : Prentice-Hall
Konishi, Scott., Yuillie, Alan L., Coughlan, James M., dan Zhu, Song Chun., 2003, Statistical Edge Detection : Learning and Evaluating Edge Cues, IEEE Transaction on Pattern Analysis and Machine Intelligence Vol 5, No. 1, 57 - 74
Low, Adrian. 1991, Computer Vision & Image Processing: Introductory, McGraw-Hill International Editions.
Mano, M. Morris. 1993. Computer System Architecture, Prentice-Hall International.
Munir, Rinaldi. 2003, Matematika Diskrit : Edisi Kedua, Informatika Bandung
Munir, Rinaldi. 2004, Pengolahan Citra Digital dengan Pendekatan Algoritmik, Informatika Bandung
Purcell, Edwin J. dan Varberg, Dale. 1987. Kalkulus dan Geometri Analitis Edisi Kelima, Erlangga
![Page 80: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/80.jpg)
Rachmat, Setiadi. 2004. Pengantar Logika Matematika, Penerbit Informatika, Bandung.
Rogers, DF dan Adams, JA.1989. Mathematical Elements For Computer Graphic : McGraw-Hill
Stalling, William. 1998. Organisasi dan Arsitektur Komputer : Perancangan Kinerja (jilid 1), Prentice Hall yang diterjemahkan oleh PT Prenhallindo, Jakarta.
RIWAYAT HIDUP PENULIS
Fadlisyah, S.Si berprofesi sebagai seorang dosen di Universitas Negeri Malikussaleh (UNIMAL). Saat ini beliau menjabat sebagai Kepala Laboratorium Teknik Informatika. Menyelesaikan pendidikannya di Fakultas MIPA program Ilmu Komputer, Universitas Padjadjaran Bandung pada tahun 2000. Selain aktif menulis beberapa buku teks komputer untuk tingkat bacaan mahasiswa, beliau juga aktif melakukan kegiatan riset – riset
yang berkaitan dengan Artificial Intelligence, dan Computer Vision. Adapun buku – buku yang telah dikeluarkannya antara lain : Komputer Visi & Pengolahan Citra, Komputer Visi Biometriks, dan lain – lain yang belum terpublikasi. Mengasuh mata kuliah Komputer Grafik, Pemrograman Matematika, Teori Bahasa & Otomata, Kecerdasan Buatan, Sistem Operasi (Linux), Pengolahan Citra, Komputer Visi, dll. Alamat yang dapat dihubungi : Fakultas Teknik UNIMAL, jln. Samudera No.35. Lhokseumawe. Telepon 0645- 42076.
![Page 81: Matematika](https://reader033.fdokumen.site/reader033/viewer/2022052203/55cf9ae3550346d033a3df77/html5/thumbnails/81.jpg)
MATEMATIKA DISKRIT Representasi data di dalam komputer bersifat tidak kontinu, untuk itu pemanipulasiannya diperlukan suatu teknik khusus. Teknik-teknik ini memiliki kesamaan tujuan yaitu pengolahan diskrit, yang dapat dikatakan sebagai matematika diskrit. Matematika diskrit hadir sebagai suatu bidang kajian yang berkonsentrasi terhadap pemanipulasian berbagai data diskrit. Keunggulan yang ditawarkan buku ini adalah semua pembahasan benar-benar beorientasi kepada pemanipulasian data. Sehingga mahasiswa dapat secara tepat mengasosiakan implementasi dari berbagai materi yang dibahas ke dalam berbagai proses di dalam komputer. Adapun materi yang dibahas di dalam buku ini adalah : Logika, Peta Karnaugh, Metode QuineMcCluskey, Konvolusi, Representasi Bilangan Floating-Point, Kode Hamming, dan Teori Graph. Buku ini ditujukan kepada mahasiswa yang mengambil mata kuliah matematika diskrit, sebagai sarana primitif untuk menjangkau konsep-konsep pemanipulasian data yang lebih mendalam.