Nama : Aulia Rahma Salsabilla
NPM : 19312104
Kelas : IF 19D
Mata Kuliah : Analisis dan Strategi Algoritma
Algoritma Divide and Conquer
A. Sejarah
Algoritma divide and
conquer di mana sub-masalah berukuran kira-kira setengah dari ukuran aslinya,
memiliki sejarah yang panjang. Sementara deskripsi yang jelas tentang algoritma
pada komputer muncul pada tahun 1946 dalam sebuah artikel oleh John Mauchly,
gagasan untuk menggunakan daftar item yang disortir untuk memfasilitasi
pencarian berasal dari setidaknya sejauh Babylonia pada 200 SM. Algoritma
divide and conquer kuno lainnya adalah algoritma Euclidean untuk menghitung
pembagi persekutuan terbesar dari dua bilangan dengan mengurangi bilangan
tersebut menjadi subproblem ekuivalen yang lebih kecil dan lebih kecil, yang
berasal dari beberapa abad SM.
Contoh awal dari
algoritma bagi dan aklukkan dengan beberapa subproblem adalah deskripsi Gauss
tahun 1805 tentang apa yang sekarang disebut algoritma Cooley-Tukey fast
Fourier transform (FFT), meskipun dia tidak menganalisis jumlah operasinya
secara kuantitatif, dan FFT tidak tersebar luas sampai ditemukan kembali lebih
dari satu abad kemudian.
Algoritma D&C dua
subproblem awal yang secara khusus dikembangkan untuk komputer dan dianalisis
dengan tepat adalah algoritma pengurutan gabungan, yang ditemukan oleh John von
Neumann pada tahun 1945.
Contoh penting lainnya
adalah algoritma yang ditemukan oleh Anatolii A. Karatsuba pada tahun 1960 yang
dapat mengalikan dua angka n- digit dalam O operasi (dalam
notasi Big O). Algoritma ini membantah dugaan tahun 1956 Andrey
Kolmogorov operasi akan diperlukan untuk tugas itu.
Sebagai contoh lain
dari algoritma bagi-dan-taklukkan yang awalnya tidak melibatkan komputer, Donald
Knuth memberikan metode yang biasanya digunakan kantor pos untuk merutekan
surat: surat diurutkan ke dalam kantong terpisah untuk wilayah geografis yang
berbeda, masing-masing kantong ini diurutkan sendiri ke dalam batch untuk
sub-wilayah yang lebih kecil, dan seterusnya sampai dikirimkan. Ini terkait
dengan jenis radix, dijelaskan untuk mesin sortir kartu berlubang sejak tahun
1929.
B. Definisi
Divide and conquer
adalah paradigma desain algoritma yang didasarkan pada rekursi multi-cabang.
Algoritma divide-dan conquer bekerja dengan memecah masalah secara rekursif
menjadi dua atau leih sub-masalah dari jenis yang sama atau terkait, hingga
masalah ini menjadi cukup sederhana untuk diselesaikan secara langsung. Solusi
untuk sub-masalah kemudian digabungkan untuk memberikan solusi untuk masalah
aslinya.
Teknik divide and
conquer ini adalah dasar dari algoritma yang efisien untuk semua jenis masalah,
seperti pengurutan (misalnya, quicksort, jenis penggabungan), mengalikan
angka-angka besar (misalnya algoritma Karatsuba), menemukan pasangan titik
terdekat, analisis sintaksis (misalnya, parser top-down ), dan menghitung
transformasi Fourier diskrit.
Memahami dan mendesain
algoritma divide and conquer adalah keterampilan kompleks yang membutuhkan
pemahaman yang baik tentang sifat dasar masalah yang akan dipecahkan. Seperti
ketika membuktikan teorema dengan induksi, seringkali masalah asli harus
diganti dengan masalah yang lebih umum atau rumit untuk menginisialisasi
rekursi, dan tidak ada metode sistematis untuk menemukan generalisasi yang
tepat. Komplikasi bagi-dan-taklukkan ini terlihat saat mengoptimalkan
penghitungan angka Fibonacci dengan rekursi ganda yang efisien.
Kebenaran dari
algoritma bagi-dan-taklukkan biasanya dibuktikan dengan induksi matematis, dan
biaya komputasinya sering ditentukan dengan menyelesaikan hubungan pengulangan.
C. Cara Kerja
Objek masalah yang di
bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik),
matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap masalah
mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah
asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema
rekursif. Sesuai dengan karakteristik pembagian dan pemecahan masalah tersebut,
maka algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif
(perulangan dengan memanggil dirinya sendiri). Dengan demikian, algoritma ini
dapat diimplementasikan dengan cara iteratif (perulangan biasa), karena pada
prinsipnya iteratif hampir sama dengan rekursif. Salah satu penggunaan
algoritma ini yang paling populer adalah dalam hal pengolahan data yang bertipe
array (elemen larik). Mengapa ? Karena pengolahan array pada umumnya selalu
menggunakan prinsip rekursif atau iteratif. Penggunaan secara spesifik adalah
untuk mencari nilai minimal dan maksimal serta untuk mengurutkan elemen array.
Dalam hal pengurutan ini ada empat macam algoritma pengurutan yang berdasar
pada algoritma Divide and Conquer, yaitu merge sort, insert sort, quick sort,
dan selection sort. Merge sort dan Quick sort mempunyai kompleksitas algoritma
O(n ²log n). Hal ini lebih baik jika dibandingkan dengan pengurutan biasa
dengan menggunakan algoritma brute force.
Skema umum algoritma Divide And Conquer :
D. Penerpan Algoritma
1. Pemecahan
Masalah Convex Hull dengan Algoritma Divide and Conquer
Pada penyelasaian
masalah pencarian Convex Hull dengan menggunakan algoritma Divide and Conquer,
hal ini dapat dipandang sebagai generalisasi dari algoritma pengurutan merge
sort. Berikut ini merupakan garis besar gambaran dari algoritmanya:
Pertama-tama lakukan
pengurutan terhadap titik-titik dari himpunan S yang diberika berdasarkan
koordinat absis-X, dengan kompleksitas waktu O(n log n).
Jika |S| ≤ 3, maka
lakukan pencarian convex hull secara brute-force dengan kompleksitas waktu
O(1). (Basis).
Jika tidak, partisi
himpunan titik-titik pada S menjadi 2 buah himpunan A dan B, dimana A terdiri
dari setengah jumlah dari |S| dan titik dengan koordinat absix-X yang terendah
dan B terdiri dari setengah dari jumlah |S| dan titik dengan koordinat absis-X
terbesar.
Secara rekursif lakukan
penghitungan terhadap HA = conv(A) dan HB = conv(B).
Lakukan penggabungan
(merge) terhadap kedua hull tersebut menjadi convex hull, H, dengan menghitung
da mencari upper dan lower tangents untuk HA dan HB dengan mengabaikan semua
titik yang berada diantara dua buah tangen ini.
Permasalahan convex
hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang cukup
banyak, seperti pada permasalahan grafika komputer, otomasi desain, pengenalan
pola (pattern recognition), dan penelitian operasi. Divide and Conquer adalah
metode pemecahan masalah yang bekerja dengan membagi masalah menjadi beberapa
upa-masalah yang lebih kecil, kemudian menyelesaikan masing-masing upa-masalah
tersebut secara independent, dan akhirnya menggabungkan solusi masing-masing
upa-masalah sehingga menjadi solusi dari masalah semula.
Algoritma Divide and
Conquer merupakan salah satu solusi dalam penyelesaian masalah convex hull.
Algoritma ini ternyata memiliki kompleksitas waktu yang cukup kecil dan efektif
dalam menyelesaikan permasalahan ini (jika dibandingkan algoritma lain). Selain
itu juga, algoritma ini dapat digeneralisasi untuk permasalahan convex hull
yang berdimensi lebih dari 3.
2. Persoalan
Minimum dan Maksimum (MinMaks)
Persoalan : Misalnya
diketahui table A yang berukuran n eleman sudah berisi nilai integer. Kita
ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam table
tersebut. Misalkan tabel A berisi elemen-elemen sebagai berikut :
Ide dasar algoritma
secara Divide and Conquer :
Ukuran table hasil
pembagian dapat dibuat cukup kecil sehingga mencari minimum dan maksimum dapat
diselesaikan (SOLVE) secara lebih mudah. Dalam hal ini, ukuran kecil yang
dipilih adalah 1 elemen atau 2 elemen.
Algoritma MinMaks :
a. Untuk
kasus n = 1 atau n = 2,
SOLVE : Jika n = 1,
maka min = maks = An. Jika n = 2, maka bandingkan kedua elemen untuk menentukan
min dan maks.
b. Untuk
kasus n > 2,
DIVIDE : Bagi dua table
A secara rekursif menjadi dua bagian yang berukuran sama, yaitu bagian kiri dan
bagian kanan.
CONQUER : Terapkan
algoritma Divide and Conquer untuk masing-masing bagian, dalam hal ini min dan
maks dari table bagian kiri dinyatakan dalam peubah min1 dan maks1, dan min dan
maks dari table bagian kanan dinyatakan dalam peubah min2 dan maks2.
COMBINE : Bandingkan
min1 dan min2 untuk menentukan min table A, serta bandingkan maks1 dan maks2
untuk menentukan maks table A.
3. Optimasi
Konversi Bilangan Desimal Ke Biner
Salah satu cara
optimasi yang bias kita lakukan adalah membagi bilangan decimal yang hendak
diubah dengan angka 8 ( bukan 2 ). Di sinilah prinsip algoritma Divide and
Conquer kita gunakan untuk melakukan optimasi. Kita pecah-pecah angka decimal
yang akan kita gunakan dengan cara membaginya dengan angka 8 secara berulang.
Angka-angka sisa pembagian yang kita peroleh kemudian kita ubah ke dalam
bilangan biner sebelum kita gabungkan menjadi hasil jawaban.
Karena angka pembagi
yang kita pakai adalah 8 (23), maka kita dapat mengurangijumlah pembagian yang
kita lakukan menjadi ± 1/3 dari jumlah semula. Hal ini tentu saja akan sangat
berpengaruh pada kinerja dan waktu yang diperlukan oleh computer mengingat
proses pembagian merupakan salah satu proses yang cukup rumit.
Tentu saja optimasi ini
harus kita bayar dengan menangani konversi bilangan octal ke biner. Akan tetapi
jika kita gunakan teknik perbandingan ( tanpa harus melakukan konversi secara
manual ), maka proses ini akan menjadi sangat cepat dan mudah. Penerapan algoritma
ini adalah dengan menggunakan sintaks case of. Begitu juga dengan permasalahan
pemakaian memori ( kompleksitas ruang ) yang lebih besar yang muncul akibat
penggunaan algoritma rekursif. Karena pada proses rekursif-nya kita tidak
banyak menggunakan variable yang memerlukan tempat yang begitu besar, maka hal
ini bias kita abaikan. Dengan penggunaan optimasi ini, maka seharusnya proses
konversi akan lebih cepat karena pemangkasan jumlah pembagian yang dilakukan.
Skema procedur utama
Konversi dengan optimasi :
Skema procedur rekursif
dengan menerapkan Algoritma Divide and Conquer :
Kompleksitas waktu
algoritma :
T(n) = O(n/3)
dengan n menyatakan
eksponen terkecil dari 2 yang mempunyai nilai 2n lebuh besar dari angka
decimal.
Algoritma konversi
system bilangan dengan menggunakan algoritma dengan optimasi yang menerapkan
algoritma Divide and Conquer lebih mangkus daripada algoritma konversi dengan
metode pembagian sisa biasa jika dilihat dari segi kompleksitas waktunya. Hanya
saja optimasi ini diimbangi dengan kenaikan pada kompleksitas ruangnya,
meskipun pengaruhnya tidak sebesar optimasi yang kita lakukan.
4. Mencari
Pasangan Titik yang Jaraknya Terdekat (Closest Pair)
Persoalan : Diberikan
himpunan titik, P, yang terdiri dari n buah titik, (xi,yi), pada bilangan 2-D.
Tentukan jarak terdekat antara dua buah titik di dalam himpunan P. Jarak dua
buah titik p1 = (x1, y1) dan p2 = (x2, y2) :
Penyelesaian dengan
Algoritma Divide and Conquer :
a. Asumsi : n = 2k dan
titik-titik diurut berdasarkan absis (x).
b. Algoritma Closest
Pair :
SOLVE : jika n = 2,
maka jarak kedua titik dihitung langsung dengan rumus Euclidean.
DIVIDE : Bagi
titik-titik itu ke dalam dua bagian, PLeft dan PRight, setiap bagian mempunyai
jumlah titik yang sama
CONQUER : Secara
rekursif, terapkan algoritma D-and-C pada masingmasing bagian.
Pasangan titik yang
jaraknya terdekat ada tiga kemungkinan letaknya :
Pasangan titik terdekat
terdapat di bagian PLeft.
Pasangan titik terdekat
terdapat di bagian PRight.
Pasangan titik terdekat
dipisahkan oleh garis batas L, yaitu satu titik di PLeft dan satu titik di
PRight.
Jika kasusnya adalah
(c), maka lakukan tahap COMBINE untuk mendapatkan jarak dua titik terdekat
sebagai solusi persoalan semula.
E. Keuntungan Algoritma
1. Memecahkan
masalah yang sulit
Bagilah dan taklukkan
adalah alat yang ampuh untuk memecahkan masalah yang sulit secara konseptual:
yang dibutuhkan hanyalah cara memecahkan masalah menjadi sub-masalah,
memecahkan kasus-kasus sepele dan menggabungkan sub-masalah ke masalah asli.
Demikian pula, mengurangi dan menaklukkan hanya membutuhkan pengurangan masalah
menjadi satu masalah yang lebih kecil, seperti teka-teki Menara Hanoi klasik,
yang mengurangi memindahkan menara dengan ketinggian n untuk memindahkan menara
dengan ketinggian n - 1
2. Efisiensi
algoritma
Paradigma
divide-and-conquer sering membantu dalam penemuan algoritma yang efisien. Itu
adalah kunci, misalnya, untuk metode perkalian cepat Karatsuba, algoritma
quicksort dan mergesort, algoritma Strassen untuk perkalian matriks, dan
transformasi Fourier cepat.
Dalam semua contoh ini,
pendekatan D&C mengarah pada peningkatan biaya asimtotik solusi. Misalnya,
jika (a) kasus dasar memiliki ukuran batas konstan, pekerjaan pemecahan masalah
dan penggabungan solusi parsial sebanding dengan ukuran masalah n dan (b) ada
bilangan terbatas p dari sub-masalah dari size ~ n / p pada setiap tahap, maka
biaya algoritma divide-and-conquer adalah O ( n log p n ).
3. Paralelisme
Algoritme
Divide-and-conquer secara alami diadaptasi untuk eksekusi di mesin
multi-prosesor, terutama sistem memori bersama di mana komunikasi data antara
prosesor tidak perlu direncanakan sebelumnya, karena sub-masalah yang berbeda
dapat dijalankan pada prosesor yang berbeda.
4. Akses
memori
Algoritme
bagi-dan-taklukkan secara alami cenderung memanfaatkan cache memori secara
efisien. Alasannya adalah setelah sub-masalah cukup kecil, sub-masalah itu dan
semua sub-masalah pada prinsipnya dapat diselesaikan di dalam cache, tanpa
mengakses memori utama yang lebih lambat. Algoritme yang dirancang untuk
mengeksploitasi cache dengan cara ini disebut cache-oblivious , karena tidak
memuat ukuran cache sebagai parameter eksplisit. Selain itu, algoritme D&C
dapat dirancang untuk algoritme penting (misalnya, pengurutan, FFT, dan
perkalian matriks) menjadi algoritme yang tidak menyadari cache yang optimal -
algoritme tersebut menggunakan cache dengan cara yang mungkin optimal, dalam
arti asimtotik, terlepas dari ukuran cache. Sebaliknya, pendekatan tradisional
untuk mengeksploitasi cache adalah memblokir , seperti dalam pengoptimalan
sarang loop , di mana masalahnya secara eksplisit dibagi menjadi
potongan-potongan dengan ukuran yang sesuai ini juga dapat
menggunakan cache secara optimal, tetapi hanya jika algoritme disetel untuk
yang spesifik. ukuran cache dari mesin tertentu.
Keuntungan yang sama
terdapat pada sistem penyimpanan hierarki lainnya, seperti NUMA atau memori
virtual , serta untuk beberapa level cache: setelah sub-masalah cukup kecil,
sub-masalah dapat diselesaikan dalam level hierarki tertentu, tanpa mengakses
level yang lebih tinggi (lebih lambat).
5. Roundoff
kontrol
Dalam perhitungan
dengan aritmatika bulat, misalnya dengan bilangan floating-point , algoritme
bagi-dan-taklukkan dapat menghasilkan hasil yang lebih akurat daripada metode
iteratif yang secara dangkal setara. Misalnya, seseorang dapat menambahkan
nomor N baik dengan loop sederhana yang menambahkan setiap datum ke variabel
tunggal, atau dengan algoritma D&C yang disebut penjumlahan berpasangan
yang memecah kumpulan data menjadi dua bagian, secara rekursif menghitung
jumlah setiap setengah, dan kemudian menambahkan dua jumlah. Meskipun metode
kedua melakukan jumlah penambahan yang sama seperti yang pertama, dan membayar
biaya tambahan dari panggilan rekursif, metode ini biasanya lebih akurat.
0 comments:
Post a Comment