Algoritma dan Bilangan Bulat Matematika Diskret (TKE132107) Program Studi Teknik Elektro, Unsoed Iwan Setiawan <stwn at unsoed.ac.id>
Tahun Ajaran 2013/2014
Algoritma
Masalah.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Kemiripan substansi masalah.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Pengurutan, pencarian, perutean, ...
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Masalah memiliki parameter.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Instance of a problem. (pemberian nilai untuk semua parameter masalah)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Ide.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Solusi. (pemecahan masalah)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Urutan langkah-langkah untuk memecahkan masalah. (dengan metode tertentu)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Proses: menjalankan sepeda motor. Algoritma: panduan menjalankan sepeda motor. Langkah-langkah: 1. siapkan sepeda motor, 2. naiklah ke tempat duduknya, 3. kembalikan penyangga, 4. masukkan kunci kontak, 5. putar kunci kontak ke posisi on, 6. tekan tombol starter, 7. ... Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Berikan 1 contoh algoritma!
Membuat kue, menanak nasi, percobaan kimia, ...
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Algoritma Program Penjumlahan 1. Deklarasikan variabel a, b, dan c. 2. Baca variabel a dan b dari masukan. 3. Jumlahkan variabel a dan b, kemudian simpan hasilnya ke variabel c. 4. Tampilkan isi variabel c ke layar. Ada sebagian orang yang memulai algoritma dengan kata “mulai” dan diakhiri dengan “selesai” untuk menandai bahwa langkah-langkah dalam sebuah algoritma dimulai atau telah selesai. Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Setiap langkah algoritma harus diikuti.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Bagaimana jika tidak?
Notasi Algoritma
Kalimat deskriptif.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
PROGRAM Penjumlahan Diberikan dua buah bilangan positif a dan b. Algoritma penjumlahan akan menjumlahkan kedua bilangan tersebut dan menyimpan hasilnya ke dalam sebuah variabel. ALGORITMA 1. Deklarasikan variabel a, b, dan c. 2. Baca variabel a dan b dari masukan. 3. Jumlahkan variabel a dan b, kemudian simpan hasilnya ke variabel c. 4. Tampilkan isi variabel c ke layar. Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Apa yang dapat kita simpulkan dari konsep algoritma yang sudah dibahas?
Menggunakan kata kerja, aktif.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Bagaimana dengan pernyataan bersyarat?
Jika …, (maka) ...
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Diagram alir?
Algoritma dalam bentuk diagram, dengan simbol-simbol standar.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Mulai atau Selesai
Pengambilan Keputusan
Masukan atau Keluaran
Proses Terdefinisi
Penghubung Proses Aliran Langkah
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Mulai
Deklarasi a, b, c
Baca a dan b
c=a+b
Tampilkan c
Selesai
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
? ?
https://en.wikipedia.org/wiki/File:Euclid_flowchart_1.png
?
? Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Relatif susah digunakan untuk program dengan algoritma yang panjang dan rumit.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Pseudocode?
Semu.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Kode informal sebuah (algoritma) program.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Lebih dekat ke kode pemrograman, tapi tidak spesifik ke bahasa pemrograman tertentu.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Tidak ada standar baku.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Gunakan kata kunci pemrograman.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
set, read, get, print, write, compute, run, if-then, else-if, while, do-while, for, goto, ...
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
declare variabel a, b get a, b if (b tidak sama dengan nol) then compute c = a / b print c else print “Nilai b tidak boleh nol.” return status sukses
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
PROGRAM FahrenheitCelcius { Program untuk mencetak tabel konversi Fahrenheit ke Celcius dari x sampai y dengan kenaikan sebesar step. Masukan: suhu awal, suhu akhir, step. Keluaran: tabel konversi suhu dalam Celcius (C) dan Fahrenheit (F). } DEKLARASI fahr, celc: real x, y, step: integer ALGORITMA read (x, y, step) fahr ← x while fahr ≤ y do celc = 5/9 * (fahr – 32) write(fahr,celc) fahr ← fahr + step endwhile Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Buatlah algoritma dengan kalimat deskriptif untuk mencari elemen terbesar dari sebuah himpunan yang berisi n buah elemen bilangan bulat!
a1, a2, a3, a4, …, an
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Algoritma dengan Kalimat Deskriptif maks
a1, a2, a3, a4, …, an
maks = a1
1) Asumsikan a1 sebagai elemen terbesar sementara. Simpan a1 ke dalam variabel maks. 2) Bandingkan maks dengan elemen a 2. Jika a2 lebih besar dari maks, maka nilai maks diganti dengan a 2. 3) Ulangi langkah kedua untuk elemen-elemen berikutnya (a3, a4, a5, ..., an) . 4) Berhenti jika sudah tidak ada lagi elemen yang dibandingkan. Jadi, variabel maks berisi nilai dari elemen terbesar. Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Algoritma dengan Kalimat Deskriptif a2 > maks?
a1, a2, a3, a4, …, an
maks = a1
1) Asumsikan a1 sebagai elemen terbesar sementara. Simpan a1 ke dalam variabel maks. 2) Bandingkan maks dengan elemen a 2. Jika a2 lebih besar dari maks, maka nilai maks diganti dengan a 2. 3) Ulangi langkah kedua untuk elemen-elemen berikutnya (a3, a4, a5, ..., an) . 4) Berhenti jika sudah tidak ada lagi elemen yang dibandingkan. Jadi, variabel maks berisi nilai dari elemen terbesar. Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Algoritma dengan Kalimat Deskriptif a2 > maks? Jika ya
a1, a2, a3, a4, …, an
maks maks = a = a21
1) Asumsikan a1 sebagai elemen terbesar sementara. Simpan a1 ke dalam variabel maks. 2) Bandingkan maks dengan elemen a 2. Jika a2 lebih besar dari maks, maka nilai maks diganti dengan a 2. 3) Ulangi langkah kedua untuk elemen-elemen berikutnya (a3, a4, a5, ..., an) . 4) Berhenti jika sudah tidak ada lagi elemen yang dibandingkan. Jadi, variabel maks berisi nilai dari elemen terbesar. Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Algoritma dengan Kalimat Deskriptif a2 > maks? Jika ya
a1, a2, a3, a4, …, an
maks maks = a = a21
1) Asumsikan a1 sebagai elemen terbesar sementara. Simpan a1 ke dalam variabel maks. 2) Bandingkan maks dengan elemen a 2. Jika a2 lebih besar dari maks, maka nilai maks diganti dengan a 2. 3) Ulangi langkah kedua untuk elemen-elemen berikutnya (a3, a4, a5, ..., an) . 4) Berhenti jika sudah tidak ada lagi elemen yang dibandingkan. Jadi, variabel maks berisi nilai dari elemen terbesar. Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
PROGRAM CariElemenTerbesar { Program untuk mencari elemen terbesar dari sebuah himpunan bilangan bulat a1, a2, …, an. Elemen terbesar akan disimpan di dalam variabel maks. Masukan: a1, a2, …, an. Keluaran: maks. } DEKLARASI i: integer maks: integer ALGORITMA maks ← a for i ← 2 to n do if ai > maks then maks ← ai endif endfor Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
procedure CariElemenTerbesar (input: a1, a2, …, an: integer, output maks: integer) { Prosedur mencari elemen terbesar dari sebuah himpunan bilangan bulat a1, a2, …, an. Elemen terbesar akan disimpan di dalam variabel maks. Masukan: a1, a2, …, an. Keluaran: maks. } Deklarasi i: integer Algoritma maks ← a for i ← 2 to n do if ai > maks then maks ← ai endif endfor Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Tajuk, deklarasi, algoritma.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Intinya adalah memudahkan deskripsi algoritma dalam bentuk terstruktur, dan memudahkan pula saat melakukan penulisan kode yang spesifik ke bahasa pemrograman.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Beberapa Contoh Algoritma
Buatlah algoritma dalam kalimat deskriptif dan pseudocode untuk algoritma berikut. 1) Algoritma mempertukarkan nilai dari 2 buah variabel. 2) Algoritma mencari nilai tertentu di dalam himpunan elemen.
Algoritma pengurutan.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Bilangan Bulat (Integer)
Bilangan yang bulat :-) (bukan pecahan, positif dan negatif)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Diskret atau kontinyu?
Bilangan bulat banyak dibahas pada Teori Bilangan.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Sifat pembagian bilangan bulat melahirkan konsep bilangan prima, aritmatika modulo, dan algoritma Euclidean.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Sifat Pembagian pada Bilangan Bulat
Salah satu konsep yang berguna.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Bilangan prima. (bilangan yang hanya habis dibagi oleh 1 dan dirinya sendiri)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Sembarang bilangan bulat positif dapat dinyatakan sebagai hasil perkalian satu atau lebih bilangan prima?
Definisi sifat pembagian: misal a dan b adalah 2 buah bilangan bulat dengan syarat a ≠ 0. Kita dapat menyatakan bahwa a habis membagi b jika terdapat bilangan bulat c sedemikian sehingga b = ac.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Notasi: a|b jika b = ac, c ∈ Z dan a ≠ 0.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Jika b dibagi dengan a, maka hasil pembagiannya berupa bilangan bulat.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Pernyataan “a habis membagi b” dapat ditulis dengan “b kelipatan a”.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
4|12 karena 12/4 = 3 Bulat, tak bersisa.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
12 = 4x3
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Apakah 4|13?
Hasil Pembagian Bilangan Bulat Jika hasil pembagian bilangan bulat dinyatakan sebagai bilangan bulat pula, maka sembarang bilangan bulat bila dibagi dengan sebuah bilangan bulat positif akan selalu terdapat: 1) hasil bagi, 2) sisa pembagian. Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
13 dibagi dengan 4, akan memberikan hasil bagi 3, dan sisa (hasil bagi) 1.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Pada kasus 4|12, sisa hasil baginya adalah 0.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Sisa hasil pembagian selalu lebih besar atau sama dengan nol, tetapi lebih kecil dari pembaginya. 0≤r
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Teorema Euclidean Misal m dan n adalah 2 buah bilangan bulat dengan syarat n > 0. Jika m dibagi dengan n maka terdapat 2 buah bilangan bulat unik q (quotinent) dan r (remainder), sedemikian sehingga: pembagi/divisor
m = nq + r
q disebut hasil bagi/quotinent r disebut sisa/remainder
yang dibagi/divident
dengan 0 ≤ r < n. Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Notasi yang digunakan untuk mengekspresikan hasil bagi dan sisa adalah dengan menggunakan operator div dan mod. q = m div n, r = m mod n
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Berapa hasil bagi dan sisa jika 1987 dibagi dengan 97?
Hasil bagi 20, sisa 47.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Tuliskan dalam ekspresi Teorema Euclidean!
1987 = 97 . 20 + 47
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Tulis dengan operator div dan mod!
1987 div 97 = 20
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
1987 mod 97 = 47
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Sisa pembagian tak boleh negatif.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Pembagi Bersama terBesar (PBB)
Dua buah bilangan bulat dapat memiliki faktor pembagi yang sama.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Faktor pembagi bersama yang penting adalah faktor Pembagi Bersama terBesar (PBB). (greatest common divisor, gcd atau faktor persekutuan terbesar, FPB)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Bilangan 45 dan 36 memiliki faktor pembagi berapa saja?
Faktor pembagi 45: 1, 3, 5, 9, 15, 45 Faktor pembagi 36: 1, 2, 3, 4, 9, 12, 18, 36 Faktor pembagi bersama: 1, 3, 9 Jadi, PBB(45,36) = 9
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
terbesar: 9
Definisi Pembagi Bersama Terbesar
Misal a dan b adalah 2 buah bilangan bulat tidak nol. Pembagi bersama terbesar (PBB) dari a dan b adalah bilangan bulat terbesar d, sedemikian sehingga d|a dan d|b. Jadi, dapat kita nyatakan bahwa PBB(a,b) = d.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Sifat-sifat PBB dapat dinyatakan dengan Teorema 5.2. Baca pada buku referensi.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Teorema PBB(m,n) = PBB(n,r)
Misal m dan n adalah 2 buah bilangan bulat dengan syarat n > 0 sedemikian sehingga: m = nq + r, 0 ≤ r < n maka PBB(m,n) = PBB(n,r).
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Algoritma Euclidean
Mencari PBB dari 2 Buah Bilangan Untuk mencari PBB dari 2 buah bilangan bulat m dan n adalah dengan: 1) mendaftar semua pembagi dari masing-masing bilangan m dan n, 2) memilih pembagi persekutuan yang mempunyai nilai terbesar.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Terdapat algoritma yang mangkus/efektif untuk mencari PBB, yaitu dengan Algoritma Euclidean.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Didasarkan pada “Teorema PBB(m,n) = PBB(n,r)” yang dilakukan berturut-turut. (sampai kita temukan sisa nol)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Algoritma Euclidean 1) Jika n = 0, m adalah PBB(m,n); selesai.
Catatan: jika m < n, maka tukar dulu nilai m dan n.
tetapi jika n ≠ 0, lanjutkan ke langkah 2. 2) Bagilah m dengan n dengan sisa r. 3) Ganti nilai m dengan nilai n, dan nilai n dengan nilai r, lalu ulang kembali langkah 1. Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
? ?
https://en.wikipedia.org/wiki/File:Euclid_flowchart_1.png
?
? Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
PBB(80,12)?
Algoritma Euclidean (1) 1) Jika n = 0, m adalah PBB(m,n);
m = 80, n = 12
selesai. tetapi jika n ≠ 0, lanjutkan ke langkah 2. 2) Bagilah m dengan n dengan sisa r.
80 dibagi 12, sisa 8 (r)
3) Ganti nilai m dengan nilai n, dan nilai n dengan nilai r, lalu ulang kembali langkah 1. Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
m = 12, n = 8
Algoritma Euclidean (2) 1) Jika n = 0, m adalah PBB(m,n);
m = 12, n = 8
selesai. tetapi jika n ≠ 0, lanjutkan ke langkah 2. 2) Bagilah m dengan n dengan sisa r.
12 dibagi 8, sisa 4 (r)
3) Ganti nilai m dengan nilai n, dan nilai n dengan nilai r, lalu ulang kembali langkah 1. Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
m = 8, n = 4
Algoritma Euclidean (3) 1) Jika n = 0, m adalah PBB(m,n);
m = 8, n = 4
selesai. tetapi jika n ≠ 0, lanjutkan ke langkah 2. 2) Bagilah m dengan n dengan sisa r.
8 dibagi 4, sisa 0 (r)
3) Ganti nilai m dengan nilai n, dan nilai n dengan nilai r, lalu ulang kembali langkah 1. Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
m = 4, n = 0
Algoritma Euclidean (4) 1) Jika n = 0, m adalah PBB(m,n); selesai.
m = 4, n = 0 Selesai!
tetapi jika n ≠ 0, lanjutkan ke langkah 2.
PBB(80,12)=4
2) Bagilah m dengan n dengan sisa r. 3) Ganti nilai m dengan nilai n, dan nilai n dengan nilai r, lalu ulang kembali langkah 1. Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Notasi pseudocode untuk Algoritma Euclidean dapat dilihat pada buku referensi, halaman 189.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Teorema Kombinasi Lanjar
Misal a dan b adalah 2 buah bilangan bulat positif, maka terdapat bilangan bulat m dan n sedemikian sehingga PBB(a,b) = ma + nb.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
PBB(80,12) = 4 m.80 + n.12 = 4 (-1).80 + 7.12 = 4 m = -1 dan n = 7
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Untuk menemukan kombinasi lanjar a dan b pada PBB(a,b) adalah dengan melakukan pembagian secara mundur pada Algoritma Euclidean.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Definisi Relatif Prima
Dua buah bilangan bulat a dan b dikatakan relatif prima jika PBB(a,b) = 1.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Apakah bilangan 7 dan 11 relatif prima?
Jika a dan b relatif prima maka dengan teorema kombinasi lanjar dapat dinyatakan: PBB(a,b) = ma + nb 1 = ma + nb ma + nb = 1
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Aritmatika Modulo
Operator yang digunakan adalah mod.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Hasil bagi dan sisa.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Definisi Operator mod
Misal a adalah bilangan bulat dan m adalah bilangan bulat > 0. Operasi a mod m memberikan sisa jika a dibagi dengan m. Dengan kata lain, a mod m = r, sedemikian sehingga a = mq + r, dengan 0 ≤ r < m.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
modulus atau modulo
Notasi: a mod m = r, sedemikian sehingga a = mq + r, dengan 0 ≤ r < m. Hasil aritmatika modulo m terletak di dalam himpunan {0, 1, 2, ..., m-1}.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Bilangan a dan b kongruen dalam modulo m jika kedua bilangan tersebut mempunyai sisa (r) yang sama jika dibagi dengan bilangan bulat positif m. a mod m = r b mod m = r
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
a ≡ b (mod m)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
a ≡/ b (mod m)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Definisi Kekongruenan
Misal a dan b adalah bilangan bulat, dan m adalah bilangan > 0, maka a ≡ b (mod m) jika m habis membagi a – b.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Apakah 17 dan 2 kongruen dalam modulo 3?
Dengan definisi operator mod, maka a mod m = r dapat ditulis a ≡ r (mod m).
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Terdapat sifat-sifat pengerjaan hitung pada aritmatika modulo, baca Teorema 5.5 pada buku referensi, halaman 193.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Inversi Modulo.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Kekongruenan lanjar, ax ≡ b (mod m).
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Chinese remainder problem.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Bilangan Prima
Bilangan bulat positif p (p > 1) disebut bilangan prima jika pembaginya 1 dan p.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Bilangan selain prima disebut komposit (composite).
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Teori fundamental aritmatik: Setiap bilangan bulat positif yang lebih besar atau sama dengan 2 dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Bilangan prima dan komposit dapat dinyatakan sebagai perkalian dari satu atau lebih faktor prima.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Faktor prima dari sebuah bilangan selalu lebih kecil atau sama dengan akar kuadrat dari bilangan tersebut.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Misal a adalah faktor prima dari n, dengan 1 < a < n, maka a habis membagi n dengan hasil bagi b sedemikian sehingga n = ab. Nilai a dan b harus ≤ n agar ab > √n . √n = n
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Faktor prima dari n selalu lebih kecil atau sama dengan √n.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Teorema bilangan komposit: jika n adalah bilangan komposit, maka n mempunyai faktor prima yang lebih kecil atau sama dengan √n.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Apakah 199 merupakan bilangan prima atau komposit?
Teorema bilangan komposit: jika n adalah bilangan komposit, maka n mempunyai faktor prima yang lebih kecil atau sama dengan √n.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
√199 = … ?
Bilangan prima yang ≤ √199?
Karena 199 tidak habis dibagi 2, 3, 5, 7, 11, dan 13, maka 199 adalah bilangan prima.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Kriptografi
Aritmatika modulo dan bilangan prima.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
“secret writing”
Onkel Tuca, CC BY-SA, http://en.wikipedia.org/wiki/File:Parthenon.JPG
Ilmu dan seni untuk menjaga keamanan pesan. – Bruce Schneier
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Untuk menjaga kerahasiaan.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
plainteks versus chiperteks
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
plainteks: ambil hatinya, jangan dompetnya chiperteks: e|}{!%@$#87)+32ihkdsf+_)+-12
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
practicalowl, CC BY-NC-SA, https://secure.flickr.com/photos/practicalowl/256628505/
Munir, 2011.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
1) Pengiriman data melalui jalur komunikasi 2) Penyimpanan data di media penyimpan
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Plainteks (plain.txt): Ketika saya berjalan-jalan di pantai, saya menemukan banyak sekali kepiting yang merangkak menuju laut. Mereka adalah anak-anak kepiting yang baru menetas dari dalam pasir. Naluri mereka mengatakan bahwa laut adalah tempat kehidupan mereka.
Ztâxzp/épêp/qtüyp{p}
Munir, 2011.
Cipherteks (cipher.txt):
Nomor PIN, siaran televisi melalui parabola, ...
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Sparta, 400 SM
Onkel Tuca, CC BY-SA, http://en.wikipedia.org/wiki/File:Parthenon.JPG
in Lur
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
, gen
B CC
A, Y-S
wi en. / / : s http
kip
rg a.o edi
ki / wi
a ky t e :S l i F /
scytale
ng le.p
E(P) = C
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
D(C) = P
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
D(E(P)) = P
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Algoritma tertutup/restricted dan terbuka.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
practicalowl, CC BY-NC-SA, https://secure.flickr.com/photos/practicalowl/256628505/
otorisasi versus enkripsi-dekripsi
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Caesar Chiper ●
●
Algoritma enkripsi sederhana pada masa raja Julius Caesar Tiap huruf alfabet digeser 3 huruf ke kanan secara wrapping
Munir, 2011.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Misalkan setiap huruf dikodekan dengan angka: A = 0, B = 1, C = 2, …, Z = 25
maka secara matematis enkripsi dan dekripsi pada Caesar Cipher dirumuskan sebagai berikut: Enkripsi: ci = E(pi) = (pi + 3) mod 26 Dekripsi: pi = D(ci) = (ci – 3) mod 26
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Contoh: Plainteks: AWASI ASTERIX DAN TEMANNYA OBELIX Cipherteks: DZDVL DVWHULA GDQ WHPDQQBA REHOLA p1 = ‘A’ = 0 p2 = ‘W’ = 22 p3 = ‘A’ = 0 p4 = ‘S’ = 18 dst…
c1 = E(0) = (0 + 3) mod 26 = 3 = ‘D’ c2 = E(22) = (22 + 3) mod 26 = 25 = ‘Z’ c3 = E(0) = (0 + 3) mod 26 = 3 = ‘D’ c4 = E(18) = (18 + 3) mod 26 = 21 = ‘V’
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Jika pergeseran huruf sejauh k, maka: Enkripsi: ci = E(pi) = (pi + k) mod 26 Dekripsi: pi = D(ci) = (ci – k) mod 26 k = kunci rahasia Pada Caesar Cipher, k = 3, untuk alfabet ASCII 256 karakter, Enkripsi: ci = E(pi) = (pi + k) mod 256 Dekripsi: pi = D(ci) = (ci – k) mod 256
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Munir, 2011.
Sistem Kriptografi
Munir, 2011.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
✔ K1 = K2, sistem kriptografi kunci simetri, contoh: Data Encryption Standard (DES) ✔ K1 ≠ K2, sistem kriptografi kunci asimetri, contoh: RSA. Melibatkan kunci pribadi dan kunci publik.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Rivest-Shamir-Adleman (RSA) ●
● ●
Dibuat oleh tiga peneliti dari Massachussets Institute of Technology (MIT), yaitu Ron Rivest, Adi Shamir, dan Len Adleman, pada tahun 1976. Termasuk algoritma kriptografi asimetri. Asimetri: kunci untuk proses enkripsi berbeda dengan kunci untuk proses dekripsi.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
RSA ●
Setiap pengguna memiliki sepasang kunci: 1. Kunci publik, e: untuk enkripsi pesan 2. Kunci privat, d: untuk dekripsi pesan
●
Kunci publik tidak rahasia, kunci privat rahasia Kunci publik, e
Plainteks, m
Enkripsi Ee (m) = c
Kunci privat, d
Cipherteks, c
Dekripsi Dd (c) = m Munir, 2011.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Plainteks, m
Pembangkitan Pasangan Kunci ●
Pilih 2 bilangan prima sembarang, a dan b yang bersifat rahasia
●
Hitung n = a b. Nilai n tidak perlu dirahasiakan
●
Hitung m = (a – 1)(b – 1); Hapus kunci a dan b
●
●
Pilih sebuah bilangan bulat untuk kunci publik, e, yang relatif prima terhadap m Hitung kunci dekripsi, d, melalui kekongruenan ed ≡ 1 (mod m)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Contoh. Misalkan a = 47 dan b = 71 (keduanya prima), maka dapat dihitung n = a . b = 3337 m = (a – 1) (b – 1) = 3220. Pilih kunci publik e = 79 (yang relatif prima dengan 3220.) Nilai e dan n dapat dipublikasikan. Catatan: Dalam praktik, nilai a dan b adalah bilangan yang sangat besar, disarankan masing-masing 100 digit.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Selanjutnya dihitung kunci dekripsi d dengan kekongruenan: e × d ≡ 1 (mod m)
1 + ( k × 3220) d= 79 Diperoleh nilai d = 1019. Ini adalah kunci dekripsi.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Algoritma enkripsi-dekripsi: Enkripsi: ci = pie mod n Dekripsi: pi = cid mod n,
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Misalkan plainteks: ‘HARI INI’ atau dalam desimal ASCII: 7265827332737873 Pecah pesan menjadi blok yang lebih kecil (misal 3 digit): p1 = 726 p2 = 582 p3 = 733
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
p4 = 273 p5 = 787 p6 = 003
Enkripsi setiap blok: c1 = 72679 mod 3337 = 215 c2 = 58279 mod 3337 = 776 dst. untuk sisa blok lainnya Keluaran: chiperteks C = 215 776 1743 933 1731 158. Dekripsi (menggunakan kunci privat d = 1019) p1 = 2151019 mod 3337 = 726 p2 = 7761019 mod 3337 = 582 dst. untuk sisi blok lainnya Keluaran: plainteks = 7265827332737873 atau dalam kode ASCII karakternya adalah HARI INI.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Daftar Bacaan ●
●
●
●
●
Daviduck, B. 2000. Introduction to Programming in C++: Algorithms, Flowcharts and Pseudocode. Kusuma, E.D. 2009. Pemrograman Dasar: Pendahuluan, Presentasi. Munir, R. 2009. Algoritma dan Pemrograman dalam Bahasa Pascal dan C, Penerbit Informatika. Munir, R. 2010. Matematika Diskrit, Revisi Keempat, Penerbit Informatika. Munir, R. 2011. Teori Bilangan, presentasi.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed