Teknik Divide dan Conquer

   
 Algoritma divide dan conquer diperkenalkan sebagai sumber dari pengendalian proses parallel yang cukup rumit hal ini karena masalah-masalah yang terjadi dapat diatasi secara independen. Banyak arsitektur dana bahasa pemrograman yang mendesain implementasinya (apliasi) dengan struktur dasar dari algoritma divide dan conquer. Pemrograman betanggung jawab atas implementasi suatu solusi. Pembuatan program akan menjadi lebih sederhana jika masalah dapat dipecah menjadi sub-sub masalah yang dapat dikelola. Penyelesaian masalah dengan komputer berhadapan dengan 4 hal, yaitu :

1.      Pemahaman keterhubungan elemen-elemen data yang relevan terhadap solusi secara menyeluruh.

2.      Pengambilan keputusan mengenai operasi-operasi yang dilakukan terhadap elemen-elemen data.

3.      Perancangan representasi elemen-elemen data di memori sehingga memenuhi criteria berikut:

·      Memenuhi keterhubungan logika antara elemen-elemen data.

·      Operasi-operasi terhadap elemen-elemen data dapat dilakukan secara mudah dan efisien.

4.      Pengambilan keputusan mengenai bahasa pemrograman terbaik untuk menerjemahkan solusi persoalan menjadi program.

Divide dan conquer itu sendiri adalah pendekatan yang ditandai dengan pembagian suatu masalah ke dalam submasalah yang bentuknya sama dengan masalah yang lebih besar. Pembagian lebih lanjut ke dalam submasalah yang lebih kecil lagi biasanya dilaksanakan dengan penggulungan, sebuah metode yang dikenal oleh programmer sekuensial. Metode rekursif akan terus-menerus membagi masalah sampai tugas itu tidak dapat dipecahkan lagi menjadi bagian yang lebih kecil. Selanjutnya tugas - tugas yang sangat sederhana akan dilaksanakan dan hasilnya kemudian dikombinasikan, dan diteruskan dengan tugas yang lebih besar lagi.

Pada prinsip dasar algoritma perulangan dibutuhkan sebuah kondisi untuk mengakhiri perulangan tersebut. Biasanya untuk mengecek apakah masalah sudah cukup kecil sehingga dapat diselesaikan secara langsung. Selain dibutuhkan sebuah kondisi, kita juga memerlukan fase devide untuk membagi atau memecahkan masalah menjadi sub-sub masalah yang lebih kecil, dan fase combine untuk menggabungkan kembali solusi dari sub-sub masalah menjadi solusi dari masalah awal.

Langkah utama dalam algoritma divide dan conquer adalah :

a)      Divide => Masalah dibagi menjadi beberapa bagian, setiap bagiannya memiliki permasalahan yang serupa dengan masalah utama.

b)      Conquer => Setiap bagian masalah masing-masing dipecahkan (dalam pemrograman dilakukan rekursif).

c)      Combine => Solusi dari masing-masing bagian masalah digabungkan sehingga membentuk solusi untuk masalah utama.

            Selain dari langkah-langkah utama diatas, berikut ini terdapat empat hal penting yang harus dipahami dalam strategi divide dan conquer :

1)                  Branching Factor

     Branching factor dalam suatu algoritma divide dan conquer adalah jumlah dari sub masalah yang akan dibagi dari sebuah masalah awal. Ini adalah langkah nyata dari algoritma divide dan conquer, didalam proses pembagian yang sebenarnya. Pada Branching factor harus memiliki jumlah dua atau lebih karena jika tidak masalah tidak bisa dibagi.

2)                  Balance

     Sebuah algoritma divide dan conquer dikatakan balance jika masalah awal dibagi menjadi sub-sub masalah dengan ukuran yang sama. Hal ini memiliki arti dimana jumlah dari keseluruhan ukuran sub masalah sama dengan sub masalah awal. Algoritma mengesort dan binary tree, dan sama halnya dengan algoritma reduksi dan prefix sum adalah beberapa contoh algoritma divide dan conquer yang seimbang.

3)                  Data Dependence of Divide Function

    Algoritma divide dan conquer memiliki sebuah fungsi pembagian terhadap data yang memiliki ketergantungan, artinya jika ukuran relative dari sebuah sub masalah tergantung proses input datanya. Salah satu contoh dari algoritma yang tidak seimbang adalah algoritma quicksort yang akan membagi sub masalah dengan fungsi data-dependent divide.

4)                  Control Parallelism of Sequentiality

    Algoritma divide dan conquer dikatakan berurutan (sequential) jika sub masalah di eksekusi dengan perintah program. Parelisasi dari algoritma divide dan conquer yang terurut pertama kali didefinisikan oleh Mou’s Divacon [Mou90],  yang terjadi ketika hasil dari salah satu sub-eksekusi diperlukan oleh sub-eksekusi lain. Dalam kasus ini hasil dari subtree pertama diberikan (passing) kepada proses komputasi subtree kedua, agar hasil akhir tersebut dapat digunakan sebgai nilai awalnya, tetapi sekarang contoh tersebut tidak dapat dijadikan ilustrasi lagi karena teknologi komputer parallel yang semakin canggih dan kompleks.