2. Algoritma, Kompleksitas dan Teori Bilangan

2. Algoritma, Kompleksitas dan Teori Bilangan 2.1 Algoritma dan Fungsi Kompleksitas Algoritma adalah sekumpulan berhingga dari instruksi-instruksi untuk melakukan perhitungan/ komputasi atau memecahkan suatu masalah. Suatu algoritma yang baik harus memiliki sifat-sifat berikut ini:

•

Masukan (input) dari himpunan tertentu

•

Keluaran (output) pada himpunan tertentu (solusi)

•

Definiteness dari setiap langkah perhitungan

•

Kebenaran (correctness) dari keluaran untuk setiap masukan yang mungkin

•

Keberhinggaan (finiteness) dari banyaknya langkah perhitungan

•

Kefektifan (effectiveness) dari setiap langkah perhitungan dan

•

Keterumuman (generality) dalam suatu kelompok permasalahan yang dipecahkan

Kita akan memakai pseudocode untuk menuliskan algoritma, yang mirip dengan bahasa Pascal. Sebagai contoh pertama, tinjau algoritma mencari nilai maksimum dari suatu barisan yang panjangnya berhingga berikut ini. procedure max(a1, a2, …, an: integers) max := a1 for i := 2 to n if max < ai then max := ai {max adalah elemen terbesar dalam barisan}

Dari masukan barisan a1, a2, ..., pertama-tama variabel max di-inisiasi dengan suku pertama barisan. Selanjutnya suku-suku berikutnya diambil dan dibandingkan dengan max, jika lebih besar maka nila lama max diganti dengan nilai baru—yaitu suku sekarang, sedangkan jika (sama atau lebih kecil), algoritma mengambil suku berikutnya—demikian seterusnya. Diakhir proses, suku terbesar dari barisan akan tertampung di dalam max.

2. Algoritma, Kompleksitas dan Teori Bilangan - 1

Contoh kedua adalah algoritma pencarian linier (linear search), yaitu algoritma yang mencari elemen tertentu dari barisan berhingga secara linier. procedure linear_search(x: integer; a1, a2, …, an: integers) i := 1 while (i ≤ n and x ≠ ai) i := i + 1 if i ≤ n then location := i else location := 0

{letak dari elemen yang dicari adalah subscript dari suku yang sama dengan x, atau nol jika tidak ditemukan.}

Pada algoritma pencarian linier, pertama-tama pencacah indeks i di-inisiasi ke harga 1. Selanjutnya suku barisan diambil satu persatu secara ber-urutan dan dibandingkan dengan bilangan yang dicari, yaitu x. Jika ditemukan, maka variable location di-assign dengan indeks dari suku tersebut, sedangkan jika tidak ditemukan, maka variable tersebut diberi harga nol. Eksekusi berakhir setelah ujung barisan dicapai, dengan variable location berisi indeks suku barisan yang dicari atau berisi nol jika tidak ditemukan. Pencarian yang demikian tentu saja akan memakan waktu yang sebanding dengan panjangnya barisan sehingga tidak efisien atau disebut bahwa kompleksitas algoritma ini besar. Interval-1 Interval-2 Interval-3

a

c

d

f

g

h

j

l

m

o

p

r

s

u

v

x

z

pusat pertama

pusat kedua pusat ketiga, KETEMU!

Gb. 2.1 Ilustrai algoritma pencarian biner


Kompleksitas bisa diturunkan jika dipakai teknik pencarian biner (binary search), akan tetapi masukannya harus terlebih dahulu diurutkan (ordered). Dalam pencarian biner, algoritma secara iteratif membatasi interval pencarian yang relevan hingga mendekati posisi suku barisan yang dicari. Berikut ini ilustrasi pencarian biner untuk huruf “j”

Algoritma dalam bentuk pseudocode dari pencarian biner adalah sebagai berikut. procedure binary_search(x: integer; a1, a2, …, an: integers) i := 1

{i is left endpoint of search interval}

j := n

{j is right endpoint of search interval}

while (i < j) begin m := ⎣(i + j)/2⎦ if x > am then i := m + 1 else j := m end if x = ai then location := i else location := 0 {letak dari elemen yang dicari adalah subscript dari suku yang sama dengan x, atau nol jika tidak ditemukan.}

Jelas bahwa dalam barisan yang terurut, pencarian biner lebih efisien daripada pencarian liniar. Selanjutnya muncul pertanyaan bagaimana cara menganalisa efisiensi dari suatu algoritma? Kita dapat mengukur efisiensi ini dengan

•

Waktu (time): yakni banyaknya komputasi elementer dalam algoritma

•

Ruang (space): adalah banyaknya sel memori yang dibutuhkan oleh algoritma.

Ukuran ini secara berturut-turut disebut sebagai kompleksitas komputasi (computational complexity) dan kompleklsitas ruang (space complexity).

Berapakah kompleksitas waktu dari algoritma pencarian linier ? Kita akan menentukan banyaknya proses perbandingan pada kasus terburuk (worst-case) sebagai fungsi dari panjang barisan n. Kasus terburuk dari algoritma pencarian linier muncul ketika elemen yang dicari


ternyata tidak ada didalam barisan masukan. Pada kasus tersebut, setiap suku dalam barisan akan dibandingkan dengan elemen yang dicari. Sehingga, untuk n buah elemen, loop while (i ≤ n and x ≠ ai) i := i + 1

dilaksanakan n kali, sehingga memerlukan 2n buah proses perbandingan. Saat memasuki loop ke (n+1) kalinya, yang dieksekusi hanyalah perbandingan i ≤ n dan loop diakhiri. Akhirnya perbandingan if i ≤ n then location := i

dieksekusi, sehingga pada kasus terburuk kompleksitas waktu adalah 2n + 2. Ini adalah nilai kompleksitas dari algoritma pencarian linier. Selanjutnya, berapakah kompleksitas waktu dari algoritma pencarian biner?

Sekali lagi kita akan menentukan jumlah perbandingan pada kondisi terburuk sebagai fungsi dari banyaknya suku dalam deretan n. Kita asumsikan terdapat n=2k buah elemen di dalam barisan yang berarti bahwa k = log(n). Jika n bukan pangkat 2 dari suatu bilangan, barisan tersebut dapat dianggap sebagai bagian dari barisan lain yang lebih besar, dimana 2k
while (i < j) begin m := ⎣(i + j)/2⎦ if x > am then i := m + 1 else j := m end interval pencarian dibatasi pada (2k–1) buah elemen, menggunakan dua operasi perbandingan. Pada siklus kedua, interval pencarian dibatasi pada sejumlah 2k-2 elemen, sekali lagi dengan dua buah perbandingan. Proses ini diulangi terus hingga terdapat hanya satu buah (=20)


elemen tersisa dalam interval pencarian. Pada kondisi ini, sejumlah 2k perbandingan telah dilakukan.

Kemudian, dilakukan perbandingan: while (i < j). Setelah itu keluar dari loop dan perbandingan akhir adalah

if x = ai then location := i

Menentukan apakah elemen yang dicari sudah ketemu. Dengan demikian, total dari kompleksitas waktu untuk algoritma pencarian biner adalah 2k + 2 = 2 ⎡log(n)⎤ + 2. (NB: kita selalu mengasumsikan logaritma basis dua).

Pada umumnya, untuk input yang kecil, kita tidak tertarik pada kompleksitas ruang maupun waktu. Perbedaan kompleksitas waktu untuk pencarian linier dengan pencarian biner tidak begitu berarti untuk n=10, tetapi sangat signifikan untuk n = 230. Misalkan, ada dua buah algoritma, sebut sebagai algoritma A dan algoritma B yang dapat memecahkan suatu kelas permasalahan. Kompleksitas waktu dari algoritma A adalah 5000n sedangkan kompleksitas dari algoritm B adalah ⎡1.1n⎤ untuk masukan n buah elemen (barisan). Sekarang kita perhatikan perbandingan kompleksitas waktu dari algoritma A dan B sebagai berikut:

Besarnya masukan

Kompleksitas algoritma-A

Kompleksitas algoritma-B

n

5000n

⎡1.1n⎤

10

50.000

3

100

500.000

13.781

1.000

5.000.000

2.5×1041

1000.000

5×109

4,8×1041392

Ini berarti bahwa algoritma B tidak dapat dipakai untuk masukan dengan elemen yang besar, sedangkan dengan algoritma A, hal ini masih bisa diatasi. Jadi, yang paling penting dalam menghitung kompleksitas suatu algoritma adalah pertumbuhan dari fungsi kompleksitas. Pertumbuhan dari kompleksitas dengan meningkatnya besarnya masukan, n, adalah ukuran yang

sesuai

untuk

membandingkan

algoritma.

Pertumbuhan

fungsi

kompleksitas

dilambangkan dengan notasi O (dibaca big-O). Perhatikan definisi berikut ini.


Definisi: Misalkan f dan g adalah dua buah fungsi dari bilangan bulat ke bilangan riil. Kita katakan bahwa f(x) adalah O(g(x)) jika ada suatu konstanta C dan k sedemikian hingga |f(x)| ≤ C|g(x)|, saat x > k.

Saat menganalisa perumbuhan dari fungsi kompleksitas, f(x) dan g(x) selalu positif. Oleh karena itu, kita dapat menyederhanakan persyaratan big-O menjadi f(x) ≤ C⋅g(x) saat x > k.

Jika kita ingin menunjukkan bahwa f(x) adalah O(g(x)), kita hanya perlu menentukan satu buah pasangan (C, k) (yang tidak pernah unik).

Ide dibelakang notasi big-O adalah penentuan batas atas (upper boundary) dari perumbuhan suatu fungsi f(x) untuk x besar. Batas ini diberikan oleh fungsi g(x) yang biasanya jauh lebih sederhana daripada f(x). Kita menerima konstanta C dalam persyaratan f(x) ≤ C⋅g(x) saat x > k.

karena C tidak pernah tumbuh sejalan dengan tumbuhnya x. Kita hanya tertarik pada x besar, sehingga jika f(x) > C⋅g(x) untuk x ≤ k, bukanlah suatu masalah. Perhatikan contoh soal berikut. Soal: Tunjukkan bahwa f(x) = x2 + 2x + 1 adalah O(x2). Jawab: Untuk x > 1: x2 + 2x + 1 ≤ x2 + 2x2 + x2 ⇒ x2 + 2x + 1 ≤ 4 x2 Karena itu, untuk C = 4 dan k = 1:

f(x) ≤ C x2 ketika x > k. ⇒ f(x) adalah O(x2).

Selanjutnya mungkin timbul pertanyaan: “jika f(x) adalah O(x2), apakah f(x) juga O(x3)?”. Jawabnya adalah “ya”, karena x3 tumbuh lebih cepat daripada x2, sehingga x3 juga tumbuh lebih cepat dibandingkan dengan f(x). Karena itu, kita selalu harus menemukan fungsi sederhana terkecil g(x) dimana f(x) adalah O(g(x)).


Fungsi-fungsi g(n) yang populer adalah: n log(n), 1, 2n, n2, n!, n, n3, log(n). Jika diurutkan dari yang pertumbuhannya paling lambat ke paling cepat, kita dapatkan daftar berikut: ¾

1

¾

log(n)

¾

n

¾

n log(n)

¾

n2

¾

n3

¾

2n

¾

n!

Permasalahan yang dapat dipecahkan dengan kompleksitas pada kondisi-terburuk berbentuk polinomial (polynomial worst-case) disebut sebagai permasalahan yang tractable. Permasalahan dengan kompleksitas yang lebih tinggi dari bentuk fungsi polynomial disebut sebagai intractable. Sedangkan permasalahan yang tidak dapat dipecahkan dengan algoritma apapun disebut sebagai unsolvable. Berikut ini beberapa aturan yang berguna untuk big-O. •

Untuk sebarang polinomial f(x) = anxn + an-1xn-1 + … + a0, dimana a0, a1, …, an bilangan riil, maka f(x) adalah O(xn).

•

Jika f1(x) adalah O(g1(x)) dan f2(x) adalah O(g2(x)), maka (f1+f2)(x) adalah O(max(g1(x), g2(x)))

•

Jika f1(x) adalah O(g(x)) dan f2(x) adalah O(g(x)), maka (f1 + f2)(x) adalah O(g(x)).

•

Jika f1(x) adalah O(g1(x)) dan f2(x) adalah O(g2(x)), maka (f1f2)(x) adalah O(g1(x)g2(x)).

Perhatikan contoh permasalahan kompleksitas berikut ini. Apakah yang dikerjakan algoritma berikut ini? procedure who_knows(a1, a2, …, an: integers) m := 0 for i := 1 to n-1 for j := i + 1 to n if |ai – aj| > m then m := |ai – aj|


{m adalah beda maksimum sebarang dua bilangan dari deretan masukan}

Proses perbandingan dalam algoritma ini dilakukan sebanyak: n-1 + n-2 + n-3 + … + 1= (n – 1)n/2 = 0.5n2 – 0.5n Dengan demikian, besarnya kompleksitas waktu dari algoritma ini adalah O(n2). Selanjutnya bandingkan dengan algoritma berikut ini yang juga memecahkan masalah yang sama! procedure max_diff(a1, a2, …, an: integers) min := a1 max := a1 for i := 2 to n if ai < min then min := ai else if ai > max then max := ai m := max – min

Dalam algoritma ini, proses perbandingan dilakukan sebanyak 2n – 2. Dengan demikian, besarnya kompleksitas waktu dari algoritma ini adalah O(n). Terlihat bahwa untuk mengerjakan hal yang sama, dua buah algoritma berbeda bisa memiliki kompleksitas yang jauh berbeda.

2.2 Teori Bilangan Yang dimaksud dengan teori bilangan dalam Matematika Diskrit adalah teori mengenai bilangan bulat dan sifat-sifatnya. Pada bagian ini akan dijelaskan prinsip-prinsip teori bilangan, meliputi :

•

Keterbagian (divisibility)

•

Pembagi persekutuan terbesar (greatest common divisors/gcd)

•

Kelipatan persekutuan terkecil (least common multiples/lcm), dan

•

Aritmetika modular (modular arithmetics)


dan beberapa algoritma terkait. Jika a dan b bilangan bulat dimana a ≠ 0, dikatakan a membagi b (a divides b) jika ada bilangan bulat c sedemikian hingga b = ac. Jika a membagi b, maka a disebut sebagai faktor (factor) dari b, dan b adalah kelipatan (multiple) dari a. Penulisan a|b dibaca sebagai a membagi b, dan notasi a / b berarti a tidak membagi b. Untuk bilangan-bilangan bulat a, b, dan c akan berlaku hal hal berikut ini: •

jika a|b dan a|c, maka a|(b + c). Contoh: 3|6 dan 3|9, maka 3|15.

•

jika a|b, maka a|bc untuk sebarang bilangan bulat c. Contoh: 5|10, jadi 5|20, 5|30, …

•

jika a|b dan b|c, maka a|c. Contoh: 4|8 dan 8|24, maka 4|24.

Suatu bilangan bulat positif p yang lebih besar dari satu disebut sebagai bilangan prima jika faktor positif dari p hanyalah 1 dan p. Bilangan bulat positif lebih besar dari 1 yang bukan bilangan prima disebut sebagai bilangan komposit.

Teorema Fundamental Aritmetika. Setiap bilangan bulat positif bisa dituliskan secara unik sebagai hasil perkalian dari bilangan-bilangan prima, yang

actor primanya bisa dituliskan

secara meningkat berurutan.

Berikut ini contoh dari teorema tersebut: •

15 = 3×5

•

48 = 2×2×2×2×3 = 24×3

•

17 = 17

•

100 = 2×2×5×5 = 22×55

•

512 = 2×2×2×2×2×2×2×2×2 = 29

•

515 = 5×103

•

28 = 2×2×7 = 22×7

Jika n sebuah bilangan bulat komposit, maka n memiliki pembagi prima yang kurang dari atau sama dengan ÷n. Pemikiran: jika n komposit, maka n memiliki dua buah pembagi p1 dan p2 sedemikian hingga p1×p2 = n dan p1≥ 2 dan p2 ≥ 2. Tetapi p1 dan p2 tidak dapat sekaligus lebih besar dari ÷n sebab jika demikian maka p1×p2 akan menjadi lebih besar dari n. Jika bilangan p1 dan p2 sendiri bukan bilangan prima, maka kedua bilangan tersebut dapat diuraikan kedalam faktor prima yang lebih kecil dari dirinya sendiri tetapi ≥ 2. 2. Algoritma, Kompleksitas dan Teori Bilangan - 9

Andaikan a suatu bilangan bulat dan d suatu bilangan bulat positif. Maka ada bilangan bulat q dan r yang unik, dimana 0 ≤ r < d, sedemikian hingga a = d×q + r. Dalam persamaan ini : •

d disebut sebagai pembagi (divisor)

•

a disebut sebagai deviden(dividend)

•

q disebut sebagai kosien (quotient) dan

•

r disebut sebagai sisa pembagian (remainder).

Contoh: Jika 17 dibagi dengan 5, maka akan diperoleh 17 = 5×3 + 2. Dengan demikian, maka: •

17 adalah deviden (dividend)

•

5 adalah pembagi (divisor),

•

3 adalah kosien (quotient), dan

•

2 adalah sisa pembagian (remainder).

Contoh lain: Bagaimana jika -11 dibagi dengan 3 ? Catat bahwa remainder tidak bisa bernilai negative, maka -11 = 3×(-4) + 1. Dengan demikian, maka: •

-11 adalah deviden

•

3 adalah pembagi

•

-4 adalah kosien, dan

•

1 adalah sisa pembagian.

Andaikan a dan b adalah bilangan bulat yang tidak sekaligus keduanya berharga nol. Bilangan bulat terbesar d sedemikian hingga d|a dan d|b disebut sebagai pembagai persekutuan terbesar (greatest common diviso/gcd)r dari a dan b, dan dituliskan gcd(a, b).

Contoh: Berapakah gcd(48, 72)? Pembagi bersama yang bernilai positif dari 48 dan 72 adalah 1, 2, 3, 4, 6, 8, 12, 16, dan 24, sehingga gcd(48, 72) = 24.


Contoh: Berapakah gcd(19, 72)? Satu-satunya pembagi bersama yang positif dari 19 dan 72 adalah 1, sehingga gcd(19, 72) =1.

Nilai gcd dapat ditentukan dengan faktorisasi prima: a = p1a1× p2a2×… × pnan , b = p1b1× p2b2×… × pnbn, dimana p1 < p2 < … < pn dan ai, bi∈N untuk 1 ≤ i ≤ n maka: gcd(a, b) = p1min(a1, b1)× p2min(a2, b2)× … × pnmin(an, bn)

Contoh: •

a = 60 = 22×31×51 , b = 54 = 21×33×50 maka gcd(a, b) = 21×31×50 = 6

Definisi. Dua bilangan bulat, a dan b adalah prima relatif jika gcd(a,b)=1.

Contoh: •

Apakah 15 dan 28 prima relatif? Ya, karena gcd(15, 28) = 1.

•

Apakah 55 dan 28 prima relatif? Ya, karena gcd(55, 28) = 1.

•

Apakah 35 dan 28 prima relatif? Tidak, karena gcd(35, 28) = 7.

Definisi. Bilangan-bilangan a1, a2, …, an adalah prima-relatif-berpasangan (pairwise relatively prime) jika gcd(ai, aj) = 1 untuk 1 ≤ i < j ≤ n.

Dengan demikian, sekumpulan bilangan bisa ditunjukkan apakah prima-relatif-berpasangan atau tidak dengan mengevaluasi gcd dari semua pasangan bilangan yang mungkin. Jika gcd pasangan-pasangan tersebut semuanya bernilai 1, maka syarat prima-relatif-berpasangan dipenuhi. Sebaliknya, jika salah satu gcd dari pasangan bilangan tersebut tidak sama dengan satu, maka kumpulan bilangan tersebut bukan prima-relatif-berpasangan. Perhatikan contoh berikut ini : •

Bilangan-bilangan 15, 17, dan 27 adalah bukan prima relatif berpasangan karena gcd(15, 27) = 3.

•

Bilangan-bilangan 15, 17, dan 28 adalah prima relatif berpasangan karena gcd(15, 17) = 1, gcd(15, 28) = 1 dan gcd(17, 28) = 1.


Definisi. Kelipatan persekutuan terkecil (least common multiple) dari bilangan bulat positif a dan b adalah bilangan bulat positif terkecil yang dapat dibagi oleh a maupun oleh b.

Kelipatan persekutuan terkecil dari a dan b dituliskan sebagai lcm(a, b). Contoh: lcm(3, 7) = 21, lcm(4, 6) = 12, dan lcm(5, 10) = 10

Seperti halnya gcd, nilai lcm dapat dihitung melalui faktorisasi prima sebagai berikut. a = p1a1 × p2 a2 × ... × pn an , b = p1b1 × p2b2 × ... × pnbn dimana p1 < p2 < ... pn −1 < pn dan ai, bi∈ N untuk 1 ≤ i ≤ n, maka lcm ( a, b ) = p1 max ( a1 , b1 ) × p2 max ( a2 , b2 ) × ... × pn max ( an , bn ) Contoh: a = 60 = 22×31×51, b = 54 = 21×33×50 maka lcm(a, b) =22×33×51 = 4×27×5 = 540 sedangkan gcd(a, b) =21×31×50 = 2×3×1 = 6 Teorema. a×b = gcd(a, b) ×lcm(a, b)

Andaikan a bilangan bulat dan m bilangan bulat positif. Notasi a mod m menyatakan sisa pembagian (remainder) dari a dibagi dengan m.

Contoh: 9 mod 4 = 1, 9 mod 3 = 0, 9 mod 10 = 10, dan -13 mod 4 = 3

Andaikan a dan b adalah bilangan-bilangan bulat dan m suatu bilangan bulat positif. Maka, a disebut kongruen dengan b modulo m jika m membagi a – b dan dituliskan a ≡ b (mod m). Dengan kata lain a ≡ b (mod m) jika dan hanya jika a mod m = b mod m. Perhatikan contohcontoh berikut ini: •

Apakah 46 ≡ 68 (mod 11)? Ya, karena 11 | (46 – 68) = 11 | -22.

•

Apakah 46 ≡ 68 (mod 22)? Ya, karena 22 | (46 – 68) = 22 | 22.

•

Tentukan bilangan bulat z sehingga berlaku z ≡ 12 (mod 10)? Jawab: z ∈{…,-28, -18, -8, 2, 12, 22, 32, …}


Teorema. Andaikan m suatu bilangan bulat positif. Bilangan bulat a dan b adalah kongruen modulo m jika dan hanya jika ada bilangn bulat k sedemikian hingga a = b + k×m. Teorema. Andaikan m suatu bilangan bulat positif. Jika a ≡ b (mod m) dan c ≡ d (mod m), maka a + c ≡ b + d (mod m) dan a×c ≡ b×d (mod m).

Algoritma Euklid adalah algoritma untuk mencari gcd dari dua buah bilangan bulat a dan b. Penjelasan diberikan oleh contoh berikut ini: untuk menentukan gcd(287, 91), bilangan 287 (yang lebih besar) dibagai dengan 91 (yang lebih kecil) :

287 = 91×3 + 14 ⇒ 287 - 91×3 = 14 ⇒ 287 + 91× (-3) = 14

Berdasarkan teorema di atas, kita tahu bahwa untuk sebarang bilangan bulat a, b dan c; jika a|b, maka a|b×c untuk semua bilangan bulat c. Oleh karena itu, sebarang pembagi 91 adalah juga pembagi 91×(-3). Maka

287 + 91× (-3) = 14

Berdasarkan teorema, kita juga tahu bahwa untuk bilangan bulat a, b dan c, jika a|b dan a|c, maka a| (b + c). Oleh karena itu, sebarang pembagi dari 287 dan 91 haruslah juga pembagi dari 287 + 91× (-3), yaitu 14. Dengan demikian, gcd dari 287 dan 91 haruslah juga sama dengan gcd dari 14 dan 91:

gcd(287, 91) = gcd(14, 91).

Pada langkah berikutnya, kita bagi 91 dengan 14: 91 = 14×6 + 7. Ini berarti bahwa

gcd(14, 91) = gcd(14, 7).

Selanjutnya 14 dibagi 7: 14 = 7⋅2 + 0. Ditemukan bahwa 7|14, sehingga gcd(14, 7) = 7. Oleh karena itu diperoleh


gcd(287, 91) = 7.

Dari ilustrasi diatas, algoritma Euklid dapat diterjemahkan ke dalam pseudocode berikut ini. procedure gcd(a, b: positive integers) x := a y := b while y ≠ 0 begin r := x mod y x := y y := r end {x adalah gcd(a, b)}

Andaikan b sebagai suatu bilangan bulat positif yang lebih besar dari 1. Jika n bilangan bulat positif, n dapat dinyatakan secara unik dalam bentuk:

n = ak × b k + ak −1 × b k −1 + ...a1 × b1 + a0

dimana k adalah bilangan bulat tak negatif, dan a0, a1, …, ak adalah bilangan bulat tak negatif yang kurang dari b, dan ak ≠ 0.

Contoh: •

untuk b =10 kita peroleh ekspresi desimal: 859 = 8×102 + 5×101 + 9×100

•

untuk b = 2 (ekspansi biner): (10110)2 = 1×24 + 1×22 + 1×21 = (22)10

•

untuk b =16 (ekspansi heksadecimal): (kita gunakan lambing bilangan A hingga F utk angka 10 sampai 15) (3A0F)16 = 3×163 + 10×162 + 15×160 = (14863)10

Untuk membuat ekspansi basis b dari suatu bilangan bulat n kita lakukan hal berikut. Pertama-tama, bagi n dengan b untuk mendapatkan kosien q0 dan sisa a0, yaitu, n = b×q0 + a0, dimana 0 ≤ a0 < b. 2. Algoritma, Kompleksitas dan Teori Bilangan - 14

Sisa a0 menempati dijit paling kanan didalam basis b dari ekspansi n. Berikutnya, bagi q0 dengan b untuk memperoleh: q0 = b×q1 + a1, dimana 0 ≤ a1 < b.

a1 adalah dijit kedua paling kanan pada basis b untuk ekspansi n. Proses ini diteruskan hingga nilai kosien sama dengan nol. Perhatikan contoh berikut ini.

Ekspansikan (12345)10 ke basis 8 dari ! Dengan cara yang diuraikan di atas, maka diperoleh

12345 = 8×1543 + 1 1543 = 8×192 + 7 192 = 8×24 + 0 24 = 8×3 + 0 3 = 8×0 + 3

Hasilnya adalah: (12345)10 = (30071)8. Ekspansi suatu bilangan decimal ke basis b dapat dilakukan dengan algoritma berikut ini. procedure base_b_expansion(n, b: positive integers) q := n k := 0 while q ≠ 0 begin ak := q mod b q := ⎣q/b⎦ k := k + 1 end {ekspansi basis b dari n adalah (ak-1 … a1a0)b}

Berikutnya kita tinjau operasi penjumlahan bilangan. Operasi ini bias dijelaskan dengan contoh berikut:


Desimal:

Biner 1 1 carry

111 carry

(1011)2 (1010 )2 + (10101)2

7583 4932 + 12515

Tinjau dua bilangan biner a = (an-1 an-2… a1 a0)2, b = (bn-1 bn-2… b1b0)2. Bagaimana sebenarnya penambahan kedua bilangan biner ini dilakukan? Pertama-tama, jumlahkan bit paling kanan:

a0 + b0 = c0×2 + s0,

dimana s0 adalah bit paling kanan dalam ekspansi biner a + b, dan c0 adalah nilai carry. Lalu, tambahkan pasangan berikutnya bersama-sama dengan carry:

a1 + b1 + c0 = c1×2 + s1,

dimana s1 adalah bit berikutnya dalam ekspansi biner dari a + b, dan c1 adalah carry. Proses ini dilanjutkan hingga didapatkan cn-1. Bit terdepan (ter-kiri) dari hasil penjumlahan adalah

sn = cn-1. Sehingga hasilnya adalah: a + b = (snsn-1…s1s0)2. Selanjutnya perhatikan contoh berikut ini: jumlahkan a = (1110)2 dan b = (1011)2. Maka dilakukan tahap-tahap berikut ini:

a0 + b0= 0 + 1 = 0⋅2 + 1, shg c0= 0 dan s0= 1. a1+ b1+ c0 = 1 + 1 + 0 = 1⋅2 + 0, shg c1 = 1 dan s1 = 0. a2 + b2 + c1 = 1 + 0 + 1 = 1⋅2 + 0, shg c2 = 1 dan s2 = 0. a3 + b3 + c2 = 1 + 1 + 1 = 1⋅2 + 1, shg c3 = 1 dan s3 = 1. s4 = c3 = 1.


Oleh karena itu, s = a + b = (11001)2. Prosedur penjumlahan bilangan basis dua memiliki algoritma berikut ini. procedure add(a, b: positive integers) c := 0 for j := 0 to n-1 begin d := ⎣(aj + bj + c)/2⎦ sj := aj + bj + c – 2d c := d end sn := c {ekspansi biner dari hasil penjumlahan adalah: s(snsn1…s1s0)2}

Matriks adalah susunan bilangan berbentuk persegiempat. Matriks yang memiliki m buah baris dan n buah kolom disebut sebagai matriks m×n. Contoh: 1 ⎤ ⎡ −1 ⎢ A = ⎢ 2.5 −0.3⎥⎥ ⎢⎣ 8 0 ⎥⎦

adalah matriks 3×2

Sebuah matriks yang jumlah baris dan kolomnya sama disebut sebagai matriks bujursangkar. Dua buah matriks disebut sama jika keduanya memilliki jumlah baris dan jumlah kolom yang sama dan elemen-elemen yang bersesuaian bernilai sama. Suatu matriks m×n, A = [aij], dapat dituliskan sebagai: ⎡ a11 ⎢a ⎢ 21 ⎢ . ⎢ ⎢ . ⎢ . ⎢ ⎣⎢ am1

a12 a22 . . . am 2

... a1n ⎤ ... a2 n ⎥⎥ . ⎥ ⎥ . ⎥ . ⎥ ⎥ ... amn ⎦⎥

⎡ a1 j ⎤ ⎢a ⎥ ⎢ 2j⎥ ⎢ . ⎥ ⎢ ⎥ ⎢ . ⎥ ⎢ . ⎥ ⎢ ⎥ ⎣⎢ amj ⎦⎥

kolom ke-j dari A


[ ai1 ,

ai 2 , ..., ain ]

baris ke-i dari A Tinjau dua buah matriks A = [aij] dan B = [bij] berukuran m×n. Penjumlahan A dan B, dituliskan sbg A + B, adalah matriks m×n dengan elemen ke (i, j) adalah aij + bij, dengan kata lain, A+B = [aij + bij]. Contoh: ⎡ −2 1 ⎤ ⎡ 5 9 ⎤ ⎡ −2 + 5 1 + 9 ⎤ ⎡ 3 10 ⎤ ⎢ 4 8 ⎥ + ⎢ −3 6 ⎥ = ⎢ 4 − 3 8 + 6 ⎥ = ⎢ 1 14 ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎢⎣ −3 0 ⎥⎦ ⎢⎣ −4 1 ⎥⎦ ⎢⎣ −3 − 4 0 + 1⎥⎦ ⎢⎣ −7 1 ⎥⎦

Andaikan A sebuah matriks m×k dan B matriks k×n. Hasil kali A dan B, dituliskan sebagai AB, adalah sebuah matriks dengan elemen ke-(i,j) nya sama dengan penjumlahan dari hasil

perkalian baris ke-i dari A dan kolom ke-j dari B. Dengan kata lain, jika AB = [cij], maka

k

cij = ai1b1 j + ai 2b2 j + ... + aik bkj = ∑ ait btj t =1

Perkalian dua buah matriks dapat dilukiskan sebagia berikut: ⎡3 0 ⎢ −2 −1 A=⎢ ⎢0 0 ⎢ ⎣ −1 1

1⎤ 4 ⎥⎥ 5⎥ ⎥ 0⎦

⎡2 1 ⎤ B = ⎢⎢0 −1⎥⎥ ⎢⎣3 4 ⎥⎦

•

Ambil baris pertama dari A, putar 90o dan pasangkan dengan kolom pertama dari B.

•

Kalikan elemen-elemen yang bersesuaian dari A dan B, kemudian jumlahkan hasil kalinya 3⋅2 + 0⋅0 + 1⋅3 = 9

•

Masukkan hasilnya kedalam posisi paling kiri atas dari C.

Lanjutkan dengan perkalian baris pertama A dengan kolom ke-dua, ketiga ... dst dari B untuk mendapatkan elemen-elemen pada baris pertama C. Ulangi proses ini untuk baris ke-dua,


tiga, ..dst dari A menghasilkan elemen pada kolom C sisa-nya. Setelah proses ini selesai, matriks C berisi akan berisi hasil kali AB. Contoh ⎡3 0 ⎢ −2 −1 A=⎢ ⎢0 0 ⎢ ⎣ −1 1

1⎤ 4 ⎥⎥ 5⎥ ⎥ 0⎦

⎡9 7 ⎤ ⎡2 1 ⎤ ⎢8 15 ⎥ ⎢ ⎥ ⎥ B = ⎢ 0 −1⎥ , maka AB = C = ⎢ ⎢15 20 ⎥ ⎢⎣ 3 4 ⎥⎦ ⎢ ⎥ ⎣ −2 −2 ⎦

Matriks identitas order-n adalah matriks n×n, In=[δij], dimana δij =1 jika i=j dan δij=0 jika i≠j: ⎡1 ⎢0 ⎢ A = ⎢... ⎢ ⎢0 ⎢⎣ 0

0 1 ... ... ...

... ... ... 1 0

0⎤ 0 ⎥⎥ .. ⎥ ⎥ 0⎥ 1 ⎥⎦

Perkalian sebarang matriks A berukuran m×n dengan matriks identitas (dengan dimensi yang sesuai) tidak mengubah matriks tsb:

AIn = ImA = A

Berikut ini kita tinjau kuasa (power) dari suatu matriks. Fungsi kuasa hanya terdefinisi untuk matriks bujursangkar. Jika A sebuah matriks n×n, maka: A0 = In, Ar = AAA …A

(r-buah A)

Transpose dari suatu matriks m×n, A = [aij], dituliskan sbg At, adalah matriks n×m yang diperoleh dengan menukarkan baris dengan kolom dari matriks A. Dengan kata lain, jika At = B = [bij], maka bij = aji untuk i = 1, 2, …, n dan j = 1, 2, …, m. Contoh:


⎡2 1 ⎤ ⎡2 0 3⎤ A = ⎢⎢ 0 −1⎥⎥ , maka A t = ⎢ 1 −1 4 ⎥⎦ ⎣ ⎢⎣ 3 4 ⎥⎦

Suatu matriks bujursangkar A disebut simetrik jika A = At. Jadi A = [aij] adalah simetrik jika aij = aji untuk semua i = 1, 2, …, n dan j = 1, 2, …, m. Tinjau dua buah matriks berikut 3⎤ ⎡5 1 ⎡1 3 1⎤ ⎢ ⎥ A = ⎢1 2 −9 ⎥ , B = ⎢⎢1 3 1⎥⎥ ⎢⎣3 −9 4 ⎥⎦ ⎢⎣1 3 1⎥⎦

Maka, A adalah matriks simetrik sedangkan B bukanlah matriks simetrik.

Sebuah matriks dengan elemen yang berharga 0 atau 1 disebut sebagai matriks Boolean (matriks zero-one). Matriks biner ini sering dipakai sebagai “tabel” untuk me-representasikan suatu struktur diskrit. Kita dapat mendefinisikan operasi Boolean pada elemen-elemen matriks Boolean sebagai berikut

a

b

a∧b

a

b

a∨b

0

0

0

0

0

0

0

1

0

0

1

1

1

0

0

1

0

1

1

1

1

1

1

1

Misalkan A=[aij] dan B=[bij] adalah matriks Boolean berukuran m×n. Maka, join (gabungan) dari A dan B adalah sebuah matriks Boolean yang elemen ke-(i,j)-nya adalah aij∨bij. Join dari A dan B dituliskan sebagai A∨B. Meet (pertemuan) dari A dan B adalah sebuah matriks

Boolean dengan elemen ke-(i,j)-nya aij ∧ bij. Meet dari A dan B dituliskan sebagai A∧B. Contoh: tinjau matriks-matriks berikut ⎡1 1 ⎤ ⎡0 1 ⎤ ⎥ ⎢ A = ⎢ 0 1 ⎥ , dan B = ⎢⎢1 1 ⎥⎥ maka ⎢⎣1 0 ⎥⎦ ⎢⎣0 0 ⎥⎦


⎡1 ∧ 0 1 ∧ 1 ⎤ ⎡0 1 ⎤ ⎡1 ∨ 0 1 ∨ 1 ⎤ ⎡1 1 ⎤ ⎥ ⎢ ⎥ ⎢ A ∨ B = ⎢ 0 ∨ 1 1 ∨ 1 ⎥ = ⎢1 1 ⎥ dan A ∧ B = ⎢⎢ 0 ∧ 1 1 ∧ 1 ⎥⎥ = ⎢⎢0 1 ⎥⎥ ⎢⎣1 ∨ 0 0 ∨ 0 ⎥⎦ ⎢⎣1 0 ⎥⎦ ⎢⎣1 ∧ 0 0 ∧ 0 ⎥⎦ ⎢⎣ 0 0 ⎥⎦

Misalkan A = [aij] adalah suatu matriks Boolean yang berukuran m×k dan B = [bij] adalah matriks Boolean yang berukuran k×n. Perkalian Boolean dari A dan B, dituliskan sebagai

A o B , adalah sebuah matriks m×n yang elemen ke-(i, j)-nya, [cij], ditentukan sebagai berikut cij = ( ai1 ∧ b1 j ) ∨ ( ai 2 ∧ b2 j ) ∨ ... ∨ ( aik ∧ bkj )

Pada dasarnya perkalian Boolean dilakukan seperti perkalian matriks biasa, tetapi operasi perkalian bilangan digantikan dengan konjungsi “∧”, sedangkan operasi penjumlahan bilangan digantikan dengan disjungsi “∨”.

Andaikan A sebuah matriks Boolean bujursangkar dan r adalah bilangan bulat positif. Kuasa Boolean (boolean power) ke-r dari A adalah perkalian Boolean sebanyak r-buah dari matriks

A. Kuasa Boolean ke-r dari A dituliskan sebagai A[r], dengan kurung kotak pada operasi perpangkatannya. Dengan demikian

A[ ] = I n 0

A[ ] = A o A o A ... o A r

( r − kali)


2. Algoritma, Kompleksitas dan Teori Bilangan

Recommend Documents