MATEMATIKA DISKRIT01/26/2011
Algoritma
Adalah suatu langkah-langkah logis untuk menyelesaikan masalah. Bedanya kalau algoritma setiap langkah difokuskan pada sistem komputer dan data.
Beberapa hal yang harus dipahami dalam mencari algoritma antara lain:
Ø Masalah seperti apa yang hendak diselesaikan?
ØGagasan apa yang ada pada algoritma tersebut?
ØBeberapa lama yang diperlukan untuk menyelesaikan masalah?
ØBerapa jumlah data yang dapat ditangani oleh algoritma tersebut? Untuk mengetahui seberapa besar kualitas suatu algoritma, dinyatakan dengan notasi-O besar ( big O-notation) untuk menyatakan tingakat kekomplekan suatu algoritma.
Notasi O-besar Menyatakan kelompok kompleksitas suatu algoritma atau jumlah operasi yang dilakukan oleh algoritma.
Definisi:
T(n) = O(f(n)) ( T(n) adalah O(f(n)) yang artinya T(n) berorde paling besar f(n)) bila terdapat C dan n0 sedemikian hingga:
T(n) £ C(f(n))
Untuk n ³ n0, artinya jika sebuah algoritma mempunyai waktu asimtotik O(f(n)), maka jika n dibuat semakin besar waktu yang dibutuhkan tidak akan pernah melebihi suatu tetapan C dikali f(n). Jadi f(n) adalah batas atas dari T(n) untuk n yang besar. T(n) dikatakan berorde paling besar f(n).
Penjelasan masing-masing kelompok algoritma sebagai berikut:
O(1) berarti waktu untuk menjalankan adalah konstan, artinya tidak bergantung pada ukuran data masukan n. Ini berarti waktu tetap sama meskipun n menjadi dua kali semula atau lebih.
O(log n) berarti perubahan waktu akan lebih kecil dari perubahan masukan n. Algoritma yang masuk dalam kelompok ini adalah algoritma yang memcahkan persoalan besar dengan membagi masalah besar menjadi masalah yang kecil yang berukuran sama. Cont: Binary search. Di sini bilangan pokok/basis log tidak terlalu penting karena semua fungsi algoritmik meningkat 2 kali semula jika n dinaikkan menjadi n2.
O(n) algoritma yang waktu bergantung kepada n secara linier, artinya jika n dinaikkan sebesar x kali maka waktu menjalankan algoritma itu juga naik sebesar x kali. Umunya algoritma pencarian beruntun
O(n log n)n Waktu pelaksanaan n log n terdapat pada algoritma yang memecahkan masalah menjadi beberapa bagian yang lebih kecil dimana setiap persoalan diselesaikan secara independen dan akhirnya solusi masing-masing digabung. Cont teknik bagi dan. Bila n dinaikkan menjadi 2 kali maka n log n meningkat tidak sampai dua kalinya, tetapi kalau n dinaikkan lebih dari 10 kali maka n log n naik lebih cepat dari kenaikkan n
O(n2) algoritma ini akan berjalan lebih lambat dari algoritma linier maupun logaritmik, sehingga hanya praktis untuk persoalan yang berukuran kecil. Bila n dinaikkan dua kali maka waktu pelaksanaan algoritma meningkat menjadi empat kali karena prose setiap masukkannya dalam dua buah kalang bersarang.
O(n3) memproses setiap masukkan dalam tiga buah kalang bersarang, misal perkalian matrik. Algoritma ini akan menjadi lebih lambat dari algoritma kuadratik meskipun n kecil atau besar. Bila n dinaikkan dua kali maka waktu pelaksanaan algoritma meningkat menjadi delapan kali.
O(2n) algoritma ini berjalan lebih lambat dari semua algoritma sebelumnya, khususnya untuk n besar. Bila n dinaikkan dua kali, waktu pelaksanaan menjadi kuadrat kali tetapi jika n= 100, maka waktu pelaksanaannya adalah 1000000 sama dengan algoritma n3.
O(n!) jenis ini memproses setiap masukkan dan menghubungkannya dengan n-1 masukkan lainnya, misal algoritma persoalan pedagang keliling. Bila n = 5 maka waktu pelaksanaan algoritma 120. Bila n dinaikkan dua kali, maka waktu pelaksanaan menjadi 2n!
Pencarian Biner
Dilakukan untuk memperkecil jumlah operasi perbandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk data yang besar. Prinsip dasarnya membagi 2 data sampai data ditemuakan.
Algoritmanya:
Input (cari) {meminta niali data yang akan dicari}
Batasatas = 1 {indeks array dimulai dari 1}
Batasbawah = n
Ketemu = false
While (batasatas < batasbawah) and (not ketemu) do
Tengah = (batasatas+batasbawah)div2
If A[tengah] = cari then ketemu = true
else if (A[tengah] <cari) then { cari dibagian kanan}
batasatas = tengah + 1
else batasbawah = tengah-1 {cari dibagian kiri}
endif
endif
endwhile
if (ketemu) then
output (‘ data berada di index nomor’, tengah)
else output (‘data tidak ditemukan’)
endif
Algoritma Pengurutan
Yang akan dibahas meliputi bubble sort, selection sort, dan insertion sort
1.Bubble Sort menggunakan prinsip kerja gelembung udara
Algoritma Bubble sort
For I = 1 to (n-1)
for J = N downto (I+1) do
if data [J] < data [J-1] then
Bubble = data [J]
data [J] = data [J-1]
data [J-1] = bubble
endif
endfor
endfor
2. Selection Sort
salah satu metode pengurutan berdasarkan prioritas antrian.
Algoritma Selection Sort
For I = 1 to (n-1)
for J = (I+1) to N do
if data [J] < data [kecil] then
kecil = J
endif
endfor
sementara = data[I]
data[I] = data[kecil]
data[kecil] = sementara
endfor
3. Insertion Sort
Metode ini dilakukan dengan penyisipan nilai data untuk suatu aaray A yang tidak terurut ke dalam suatu tempat kosong C dan memastikan nilai data C selalu dalam keadaan terurut.
Algoritma Insertion sort
For I = 2 to N do
sementara = data[I]
j = I – 1
while (sementara < data[J]) and (J>1) do
data [J+1] = data [J]
J = J – 1
endwhile
if sementara ³ data[J] then
data[J+1] = sementara
else data [J+1] = data [J]
data [J] = sementara
endif
endfor
Hubungan Rekurensi
Sebuah hubungan rekurensi untuk urutan a0, a1,…adalah sebuah persamaan yang menghubungkan a0 dengan suku tertentu pendahulunya a0,a1,…,an-1. Kondisi awal untuk urutan a0,a1,… secara eksplisit memberikan nilai kepada sejumlah suku-suku tertentu dalam urutan itu.
Rekurensi adalah proses perulangan yaitu memanggil dirinya sendiri (fungsi/prosedur) dengan parameter yang berbeda, sampai pengulangan berhenti.
Cara lain menyelesaikan rekurensi adalah:
1.Memecahkan masalah yang besar menjadi dua submasalah. 2.Submasalah tersebut diselesaikan dengan cara yang sama untuk memecahkan masalah yang besar tersebut.
Algoritma
Adalah suatu langkah-langkah logis untuk menyelesaikan masalah. Bedanya kalau algoritma setiap langkah difokuskan pada sistem komputer dan data.
Beberapa hal yang harus dipahami dalam mencari algoritma antara lain:
Ø Masalah seperti apa yang hendak diselesaikan?
ØGagasan apa yang ada pada algoritma tersebut?
ØBeberapa lama yang diperlukan untuk menyelesaikan masalah?
ØBerapa jumlah data yang dapat ditangani oleh algoritma tersebut? Untuk mengetahui seberapa besar kualitas suatu algoritma, dinyatakan dengan notasi-O besar ( big O-notation) untuk menyatakan tingakat kekomplekan suatu algoritma.
Notasi O-besar Menyatakan kelompok kompleksitas suatu algoritma atau jumlah operasi yang dilakukan oleh algoritma.
Definisi:
T(n) = O(f(n)) ( T(n) adalah O(f(n)) yang artinya T(n) berorde paling besar f(n)) bila terdapat C dan n0 sedemikian hingga:
T(n) £ C(f(n))
Untuk n ³ n0, artinya jika sebuah algoritma mempunyai waktu asimtotik O(f(n)), maka jika n dibuat semakin besar waktu yang dibutuhkan tidak akan pernah melebihi suatu tetapan C dikali f(n). Jadi f(n) adalah batas atas dari T(n) untuk n yang besar. T(n) dikatakan berorde paling besar f(n).
Penjelasan masing-masing kelompok algoritma sebagai berikut:
O(1) berarti waktu untuk menjalankan adalah konstan, artinya tidak bergantung pada ukuran data masukan n. Ini berarti waktu tetap sama meskipun n menjadi dua kali semula atau lebih.
O(log n) berarti perubahan waktu akan lebih kecil dari perubahan masukan n. Algoritma yang masuk dalam kelompok ini adalah algoritma yang memcahkan persoalan besar dengan membagi masalah besar menjadi masalah yang kecil yang berukuran sama. Cont: Binary search. Di sini bilangan pokok/basis log tidak terlalu penting karena semua fungsi algoritmik meningkat 2 kali semula jika n dinaikkan menjadi n2.
O(n) algoritma yang waktu bergantung kepada n secara linier, artinya jika n dinaikkan sebesar x kali maka waktu menjalankan algoritma itu juga naik sebesar x kali. Umunya algoritma pencarian beruntun
O(n log n)n Waktu pelaksanaan n log n terdapat pada algoritma yang memecahkan masalah menjadi beberapa bagian yang lebih kecil dimana setiap persoalan diselesaikan secara independen dan akhirnya solusi masing-masing digabung. Cont teknik bagi dan. Bila n dinaikkan menjadi 2 kali maka n log n meningkat tidak sampai dua kalinya, tetapi kalau n dinaikkan lebih dari 10 kali maka n log n naik lebih cepat dari kenaikkan n
O(n2) algoritma ini akan berjalan lebih lambat dari algoritma linier maupun logaritmik, sehingga hanya praktis untuk persoalan yang berukuran kecil. Bila n dinaikkan dua kali maka waktu pelaksanaan algoritma meningkat menjadi empat kali karena prose setiap masukkannya dalam dua buah kalang bersarang.
O(n3) memproses setiap masukkan dalam tiga buah kalang bersarang, misal perkalian matrik. Algoritma ini akan menjadi lebih lambat dari algoritma kuadratik meskipun n kecil atau besar. Bila n dinaikkan dua kali maka waktu pelaksanaan algoritma meningkat menjadi delapan kali.
O(2n) algoritma ini berjalan lebih lambat dari semua algoritma sebelumnya, khususnya untuk n besar. Bila n dinaikkan dua kali, waktu pelaksanaan menjadi kuadrat kali tetapi jika n= 100, maka waktu pelaksanaannya adalah 1000000 sama dengan algoritma n3.
O(n!) jenis ini memproses setiap masukkan dan menghubungkannya dengan n-1 masukkan lainnya, misal algoritma persoalan pedagang keliling. Bila n = 5 maka waktu pelaksanaan algoritma 120. Bila n dinaikkan dua kali, maka waktu pelaksanaan menjadi 2n!
Pencarian Biner
Dilakukan untuk memperkecil jumlah operasi perbandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk data yang besar. Prinsip dasarnya membagi 2 data sampai data ditemuakan.
Algoritmanya:
Input (cari) {meminta niali data yang akan dicari}
Batasatas = 1 {indeks array dimulai dari 1}
Batasbawah = n
Ketemu = false
While (batasatas < batasbawah) and (not ketemu) do
Tengah = (batasatas+batasbawah)div2
If A[tengah] = cari then ketemu = true
else if (A[tengah] <cari) then { cari dibagian kanan}
batasatas = tengah + 1
else batasbawah = tengah-1 {cari dibagian kiri}
endif
endif
endwhile
if (ketemu) then
output (‘ data berada di index nomor’, tengah)
else output (‘data tidak ditemukan’)
endif
Algoritma Pengurutan
Yang akan dibahas meliputi bubble sort, selection sort, dan insertion sort
1.Bubble Sort menggunakan prinsip kerja gelembung udara
Algoritma Bubble sort
For I = 1 to (n-1)
for J = N downto (I+1) do
if data [J] < data [J-1] then
Bubble = data [J]
data [J] = data [J-1]
data [J-1] = bubble
endif
endfor
endfor
2. Selection Sort
salah satu metode pengurutan berdasarkan prioritas antrian.
Algoritma Selection Sort
For I = 1 to (n-1)
for J = (I+1) to N do
if data [J] < data [kecil] then
kecil = J
endif
endfor
sementara = data[I]
data[I] = data[kecil]
data[kecil] = sementara
endfor
3. Insertion Sort
Metode ini dilakukan dengan penyisipan nilai data untuk suatu aaray A yang tidak terurut ke dalam suatu tempat kosong C dan memastikan nilai data C selalu dalam keadaan terurut.
Algoritma Insertion sort
For I = 2 to N do
sementara = data[I]
j = I – 1
while (sementara < data[J]) and (J>1) do
data [J+1] = data [J]
J = J – 1
endwhile
if sementara ³ data[J] then
data[J+1] = sementara
else data [J+1] = data [J]
data [J] = sementara
endif
endfor
Hubungan Rekurensi
Sebuah hubungan rekurensi untuk urutan a0, a1,…adalah sebuah persamaan yang menghubungkan a0 dengan suku tertentu pendahulunya a0,a1,…,an-1. Kondisi awal untuk urutan a0,a1,… secara eksplisit memberikan nilai kepada sejumlah suku-suku tertentu dalam urutan itu.
Rekurensi adalah proses perulangan yaitu memanggil dirinya sendiri (fungsi/prosedur) dengan parameter yang berbeda, sampai pengulangan berhenti.
Cara lain menyelesaikan rekurensi adalah:
1.Memecahkan masalah yang besar menjadi dua submasalah. 2.Submasalah tersebut diselesaikan dengan cara yang sama untuk memecahkan masalah yang besar tersebut.