Top Banner
Pengertian Kloning Gen, Manusia Dan Menurut Agama Islam October 24, 2009 · Posted in Kesehatan lowongan kerja fotos social networking site response Info Terbaru Pengertian Kloning Gen, Manusia Dan Dalam Pandangan Agama Kloning; pengertian sederhanya adalah cangkok; yaitu penggabungan unsur-unsur hayati dua atau lebih untuk memperoleh manfaat tertentu. Di bidang biologi molekuler, pengertian kloning ini sering dikonotasikan dengan teknologi penggabungan fragment (potongan) DNA, sehingga pengertiannya identik dengan teknologi rekombinan DNA atau rekayasa genetik. Namun pengertian di luar itu juga masih tetap digunakan, misalnya kloning domba dsb, yang merupakan “penggabungan” unsur inti sel dengan sel telur tanpa inti. Dengan demikian teknologi kloning ini juga termasuk dalam wacana bioteknologi; malah bisa dikatakan sebagai hal yang mendasar untuk bioteknologi. Teknologi kloning memang memungkinkan untuk dikembangakan ke arah rekayasa pembuatan jaringan atau organ tertentu. Namun mesti memperhatikan masalah etik (mungkin ada yang punya pandangan tertentu mengenai etika ini? Ditinjau dari segi ajaran agama, misalnya?). Mengenai rekayasa darah untuk keperluan transfusi, meskipun sel darahnya sendiri bisa diusahakan melalui teknologi kloning (melalui stimulasi hematopoietic progenitors, atau dari stem cells-nya), namun mesti juga harus memperhatikan komponen-komponen lainnya selain komponen sel-sel darah. Pengertian kloning:Kloning adalah teknik membuat keturunan derngan kode genetik yang sama dengan induknya, pada manusia kloning dilakukan dengan mempersiapkan sel telur yang sudah di ambil intinya lalu disatukan dengan sel somatic dari suatu organ tubu, kemudian hasilnya ditanamkan dalam rahim seperti halnya pada bayi tabung. Macam-macam teknik pengkloningan: kloning dapat dilakukan terhadap semua makhluk hidup tumbuhan,hewandan manusia.Pada tumbuhan kloning dapat dilakukan dengan tekhink okulasi,sedangkan pada hewan dan manusia,ada beberapa tekhnik-tekhnik yan dapat dilakukan, kloning ini dapat berupa kloning embrio dan kloning hewan atau manusia itu sendiri. kloning terhadap hewan atau tumbuhan jika memiliki daya guna bagi kehidupan manusi maka hukumnya mubah/boleh dalilnya : Q.S. Al-Baqoroh:29,Q.S. Al-Jatsiyah berdasarkan pengalaman yang telah dilakukan beberapa ulama’ dapat di ketahui mafsadat dari kloning lebih banyak daripada maslahatnya. oleh karna itu,praktek kloning manusia bertentangan dengan hukum islam dengan demikian kloning manusia dalam islam hukumnya haram.Dalil-dalil keharaman.:Q.S. An-Najm:45-46, Q.S. Al-Qiyamah:37-38,Q.S.Al-Hujurat:13,Q.S.Al- Ahzab:5,Q.S.Al-Israa’:70,Q.S.At-tiin:4 Hukum Kloning, Tranplantasi Organ, Abortus, dan Bayi Tabung Menurut Islam 2 November 2009 — Abied Kloning Kloning adalah teknik membuat keturunan dengan kode genetik yang sama dengan induknya pada mahkluk hidup tertentu baik berupa hewan, tumbuhan, dan manusia, hal ini dapat dilakukan dengan cara mengambil sel tubuh induknya (sel somatik) dan selanjutnya ditanamkan pada sel induk (ovum) wanita yang telah dihilangkan inti selnya dengan suatu metode yang mirip dengan proses pembuahan atau inseminasi buatan. Dengan metode senacam itu, kloning manusia dilaksanakan dengan cara mengambil inti sel dari seorang perempuan, lalu dengan cairan kimiawi khusus dan kejutan listrik inti sel digabungkan dengan sel telur, setelah penggabungan ini terjadi maka akan ditransfer ke dalam rahim seorang perempuan, agar dapat memperbanyak diri, berkembang,berdiferensiasi dan berubah menjadi janin yang sempurna. Setelah itu keturunan yang dihasilkan dapat dilahirkan secara alamiah yang berkode genetik sama dengan induknya. Kloning embrio terjadi pada sel embrio yang berasal dari rahim istri yang terbentuk dari pertemuan antara sperma suaminya dengan sel telur istrinya yang telah dihilangkan intinya. Selanjutnya sel-sel embrio itu dapat ditanamkan pada rahim perempuan asing. Bentuk kloning ini hukumnya haram sebab dalam hal ini terjadi pencampuradukan dan penghilangan nasab (garis katurunan). Tetapi apabila sel-sel embrio itu ditanamkan pada rahim perempuan pemiliknya maka kloning seperti ini hukumnya mubah. Kloning manusia dapat berlangsung dengan adanya laki- laki dan perempuan dan prosesnya dengan mengambil sel dari tubuh laki- laki lalu inti selnya diambil dan kemudian digabungkan dengan sel telur perempuan yang telah dibuang intinya agar dapat memperbanyak diri, berkembang, berduferensiasi kemudian berkembang menjadi janin dan akhirnya dilahirkan. Klonin yang
13

2. Algoritma Kompleksitas Dan Teori Bilangan

Oct 23, 2015

Download

Documents

Khazali Fahmi
Welcome message from author
This document is posted to help you gain knowledge. Please leave a comment to let me know what you think about it! Share it to your friends and learn new things together.
Transcript
Page 1: 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

Page 2: 2. Algoritma Kompleksitas Dan Teori Bilangan

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.

Gb. 2.1 Ilustrai algoritma pencarian biner

a c d f g h j l m o p r s u v x z

pusat pertamapusat kedua

Interval-1Interval-2

Interval-3

pusat ketiga, KETEMU!

2. Algoritma, Kompleksitas dan Teori Bilangan - 2

Page 3: 2. Algoritma Kompleksitas Dan Teori Bilangan

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

2. Algoritma, Kompleksitas dan Teori Bilangan - 3

Page 4: 2. Algoritma Kompleksitas Dan Teori Bilangan

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<n<2k+1. Pada siklus pertama dari loop

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)

2. Algoritma, Kompleksitas dan Teori Bilangan - 4

Page 5: 2. Algoritma Kompleksitas Dan Teori Bilangan

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.

2. Algoritma, Kompleksitas dan Teori Bilangan - 5

Page 6: 2. Algoritma Kompleksitas Dan Teori Bilangan

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)).

2. Algoritma, Kompleksitas dan Teori Bilangan - 6

Page 7: 2. Algoritma Kompleksitas Dan Teori Bilangan

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|

2. Algoritma, Kompleksitas dan Teori Bilangan - 7

Page 8: 2. Algoritma Kompleksitas Dan Teori Bilangan

{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)

2. Algoritma, Kompleksitas dan Teori Bilangan - 8

Page 9: 2. Algoritma Kompleksitas Dan Teori Bilangan

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

Page 10: 2. Algoritma Kompleksitas Dan Teori Bilangan

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.

2. Algoritma, Kompleksitas dan Teori Bilangan - 10

Page 11: 2. Algoritma Kompleksitas Dan Teori Bilangan

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.

2. Algoritma, Kompleksitas dan Teori Bilangan - 11

Page 12: 2. Algoritma Kompleksitas Dan Teori Bilangan

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.

, 1 1 2 2 ... n na p a p a p a= × × × 1 1 2 2 ... n nb p b p b p b= × × ×

dimana 1 2 1... n np p p −< < < p dan ai, bi∈ N untuk 1 ≤ i ≤ n,

maka ( ) ( ) ( ) ( )1 1 1 2 2 2, max , max , ... max ,n nlcm a b p a b p a b p a b= × × × n

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 contoh-

contoh 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, …}

2. Algoritma, Kompleksitas dan Teori Bilangan - 12

Page 13: 2. Algoritma Kompleksitas Dan Teori Bilangan

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

2. Algoritma, Kompleksitas dan Teori Bilangan - 13

Page 14: 2. Algoritma Kompleksitas Dan Teori Bilangan

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:

1 11 1...k k

k kn a b a b a b a−−= × + × + × + 0

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

Page 15: 2. Algoritma Kompleksitas Dan Teori Bilangan

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:

2. Algoritma, Kompleksitas dan Teori Bilangan - 15

Page 16: 2. Algoritma Kompleksitas Dan Teori Bilangan

Desimal: Biner

75834932

12515+

111 carry

( )( )( )

2

2

2

1011

101010101

+

1 1 carry

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.

2. Algoritma, Kompleksitas dan Teori Bilangan - 16

Page 17: 2. Algoritma Kompleksitas Dan Teori Bilangan

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(snsn-

1…s1s0)2}

Matriks adalah susunan bilangan berbentuk persegiempat. Matriks yang memiliki m buah

baris dan n buah kolom disebut sebagai matriks m×n. Contoh:

adalah matriks 3×2 1 1

2.5 0.38 0

−⎡ ⎤⎢= −⎢⎢ ⎥⎣ ⎦

A ⎥⎥

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:

11 12 1

21 22 2

1 2

...

.... . .. . .. . .

...

n

n

m m mn

a a aa a a

a a a

⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦

1

2

.

.

.

j

j

mj

aa

a

⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦

⎥ kolom ke-j dari A

2. Algoritma, Kompleksitas dan Teori Bilangan - 17

Page 18: 2. Algoritma Kompleksitas Dan Teori Bilangan

[ ]1 2, , ...,i i ina a a

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 143 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

1 1 2 21

...k

ij i j i j ik kj it tjt

c a b a b a b a b=

= + + + =∑

Perkalian dua buah matriks dapat dilukiskan sebagia berikut:

3 0 1

2 1 4

0 0 51 1 0

⎡ ⎤⎢ ⎥− −⎢ ⎥=⎢ ⎥⎢ ⎥−⎣ ⎦

A2 10 13 4

⎡ ⎤⎢ ⎥= −⎢ ⎥⎢ ⎥⎣ ⎦

B

• 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,

2. Algoritma, Kompleksitas dan Teori Bilangan - 18

Page 19: 2. Algoritma Kompleksitas Dan Teori Bilangan

tiga, ..dst dari A menghasilkan elemen pada kolom C sisa-nya. Setelah proses ini selesai,

matriks C berisi akan berisi hasil kali AB. Contoh

, maka AB =

3 0 12 1 4

0 0 51 1 0

⎡ ⎤⎢ ⎥− −⎢ ⎥=⎢ ⎥⎢ ⎥−⎣ ⎦

A2 10 13 4

⎡ ⎤⎢= −⎢⎢ ⎥⎣ ⎦

B ⎥⎥

9 78 1515 20

2 2

⎡ ⎤⎢ ⎥⎢ ⎥=⎢ ⎥⎢ ⎥− −⎣ ⎦

C

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

1 0 ... 00 1 ... 0... ... ... ..0 ... 1 00 ... 0 1

⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥=⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦

A

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. Algoritma, Kompleksitas dan Teori Bilangan - 19

Page 20: 2. Algoritma Kompleksitas Dan Teori Bilangan

, maka 2 10 13 4

⎡ ⎤⎢= −⎢⎢ ⎥⎣ ⎦

A ⎥⎥

2 0 31 1 4

t ⎡ ⎤= ⎢ ⎥−⎣ ⎦

A

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

, 5 1 31 2 93 9 4

⎡ ⎤⎢ ⎥= −⎢ ⎥⎢ ⎥−⎣ ⎦

A1 3 11 3 11 3 1

⎡ ⎤⎢ ⎥= ⎢ ⎥⎢ ⎥⎣ ⎦

B

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

, dan maka 1 10 11 0

⎡ ⎤⎢= ⎢⎢ ⎥⎣ ⎦

A ⎥⎥

⎥⎥

0 11 10 0

⎡ ⎤⎢= ⎢⎢ ⎥⎣ ⎦

B

2. Algoritma, Kompleksitas dan Teori Bilangan - 20

Page 21: 2. Algoritma Kompleksitas Dan Teori Bilangan

dan 1 0 1 1 1 10 1 1 1 1 11 0 0 0 1 0

∨ ∨⎡ ⎤ ⎡ ⎤⎥⎥⎥⎦

⎢ ⎥ ⎢∨ = ∨ ∨ =⎢ ⎥ ⎢⎢ ⎥ ⎢∨ ∨⎣ ⎦ ⎣

A B1 0 1 1 0 10 1 1 1 0 11 0 0 0 0 0

∧ ∧⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥∧ = ∧ ∧ =⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥∧ ∧⎣ ⎦ ⎣ ⎦

A B

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

, adalah sebuah matriks m×n yang elemen ke-(i, j)-nya, [cA Bo ij], ditentukan sebagai berikut

( ) ( ) ( )1 1 2 2 ...ij i j i j ik kjc a b a b a b= ∧ ∨ ∧ ∨ ∨ ∧

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

[ ]

[ ]

0

... ( kali)n

r r

=

= −

A I

A A A A Ao o o

2. Algoritma, Kompleksitas dan Teori Bilangan - 21