Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer

Nama            : Diani Widyaningrum
NPM             : 21382004P
Kelas             : IF 21 Dx         
Mata Kuliah  : Organisasi dan Arsitektur Komputer

Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer

Pada awal algoritma ini, terutama ada pengurangan dan mengatasi masalah aslinya. Ini terus didekomposisi menjadi satu sub-masalah dan dapat diselesaikan secara iteratif. Pencarian biner, algoritma pembagian dan penaklukan, memiliki sejarah panjang karena submasalahnya berukuran sekitar setengah dari ukuran aslinya. Deskripsi yang jelas tentang algoritme pada komputer diterbitkan dalam artikel John Mauchly pada tahun 1946, tetapi setidaknya sampai Babilonia pada tahun 200 SM, idenya adalah menggunakan daftar elemen yang berurutan untuk memudahkan pencarian. Kembali ke SM. Algoritme pengurangan dan penaklukan  kuno lainnya adalah algoritme Euclidean untuk menghitung pembagi persekutuan terbesar dari dua bilangan dengan mereduksi bilangan tersebut menjadi sub-masalah ekuivalen yang ada pada abad sebelum masehi. Kembali ke SM.

 Contoh awal dari algoritma divide-and-conquer dengan beberapa sub-masalah adalah deskripsi Gauss  tentang apa yang  disebut algoritma Cooley-Tukey Fast Fourier Transform (FFT), tetapi tidak menganalisis jumlah operasinya secara kuantitatif. Dan FFT tidak menyebar sampai  ditemukan kembali lebih dari satu abad kemudian.  Algoritma D & C Dua sub-masalah awal yang dikembangkan khusus  untuk komputer dan dianalisis dengan benar adalah algoritma pengurutan komposit yang ditemukan oleh John von Neumann pada tahun 1945.

 Langkah-langkah umum algoritma Divide and Conquer :

• Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).
• Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).
• Combine : Menggabungkan solusi masing-masing upa-masalah sehingga  membentuk solusi masalah semula. 

Strategy Divide and Conquer

Algoritma Divide and Conquer (DANDC) memecah masalah menjadi submasalah-submasalah independen yang lebih kecil sehingga solusi submasalah–submasalah dapat diperoleh secara mudah. Solusi dari submasalah–submasalah kemudian digabung menjadi solusi dari seluruh masalah. Prinsip dasar dari algoritma ini adalah dengan membagi n input menjadi k subset input yang berbeda (1 < k ≤n). Dari k subset input yang berbeda akan terdapat k subproblem. Setiap subproblem mempunyai solusinya masing-masing, sehingga akan diperoleh k subsolusi. Kemudian, dari k subsolusi akan diperoleh solusi yang optimal atau solusi yang diharapkan. 

Jika subproblem dianggap masih terlalu besar, maka metode DANDCdapat digunakan lagi. Dalam keadaan tersebut, pemakaian ulang metodeDANDC dinyatakan menggunakan teknik rekursif. Pemecahan n input menjadi k input sehingga menimbulkan k subproblem dapat dilakukan apabila k subproblem tersebut mempunyai sifat yang sama terhadap persoalan semula atau awalnya.

Skema umum algoritma divide dan conquer

Procedure DNC ( i,j : integer )

Var K : integer ;

If SMALL (i,j) then SOLVE (i,j)

Else begin

K : = DIVIDE (i,j)

COMBINE (DNC(i,k),DNC(k+1,j))

End if

Keterangan :

1.      SMALL adalah fungsi yang mengirim BOOLEAN, menentukan apakah ukuran telah cukup kecil sehingga solusi dapat diperoleh. Ukurandinyatakan sebagai telah berukuran kecil bergantung masalah.

2.      DIVIDE adalah fungsi membagi menjadi 2 bagian pada posisi K. Biasanya bagian berukuran sama.

3.      COMBINE adalah fungsi menggabungkan solusi X dan Y submasalah. Solusi diperoleh dengan memanggil prosedur rekursif DNC.

Jika ukuran kedua submasalah sama, waktu komputasi DNC dideskripsikan hubungan rekuren berikut :

T(n) = g (n), n kecil

2 T (n/2) + f (n), selainnya

dimana :

• T(n) adalah waktu untuk DNC dengan n masukan,
•  g(n) adalah waktu komputasi jawaban secara langsung untuk masukan kecil dan
•  f(n) adalah waktu COMBINE.

Alamat web Program studi, Fakultas, Universitas 
 http://ti.ftik.teknokrat.ac.id, http://ftik.teknokrat.ac.id, www.teknokrat.ac.id