Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer

 Nama : Rian Pebriawan

Npm : 21312026

Kelas : IF 21A

Sejarah Algoritma Devide dan Conquer

        Pada zaman dahulu, divide and conquer merupakan strategi militer yang dikenal dengan nama divide ut imperes. Saat ini strategi tersebut menjadi strategi fundamental di dalam ilmu komputer dengan nama divide and conquer. Algoritma divide and conquer ini ditemukan oleh seorang ilmuwan Rusia bernama Anatolii Alexeevich Karatsuba pada tahun 1960. Pada mulanya beliau menemukan algoritma yang lebih mangkus untuk mengalikan dua buah bilangan bulat yang besar.

Definisi Divide and Conquer

        Dividide and conquer merupakan algoritma yang sangat popular di dunia ilmu komputer. Divide and conquer merupakan algorita yang berprinsip memecah – mecah suatu permasalahan yang terlalu besar menjadi bagian – bagian kecil, sehingga lebih mudah untuk diselesaikan. Langkah – langkah umum algoritma untuk divide and conquer adalah, sebagai berikut :

• Divide membagi masalah menjadi beberapa upamasalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama).
• Conquer memecahkan atau menyelesaikan masing – masing upa-masalah secara rekursif
• Combine menggabungkan solusi masing – masing upa-masalah sehingga membentuk solusi masalah semula.

Berikut ini merupakan skema umum dari algoritma divide and conquer :

Cara Kerja Algoritma Divide and Conquer

        Dengan menggunakan bahasa dan library yang tepat, kita dapat membagi-bagikan setiap bagian rekursif (left = ... dan right = ...) ke satu unit kerja baru, yang dikenal dengan nama thread. Mekanisme pada sistem operasi atau compiler kemudian akan membagi-bagikan tugas pembagian dan perhitungan lanjutan agar dapat dijalankan secara paralel, misalnya dengan membagikan tugas ke dalam beberapa core prosesor, atau bahkan ke dalam mesin lain (jika terdapat sistem dengan banyak mesin).

        Dengan membagi-bagikan pekerjaan ke dalam banyak unit, tentunya pekerjaan akan lebih cepat selesai! Teknik memecah-mecah pekerjaan untuk kemudian dibagikan kepada banyak pekerja ini dikenal dengan nama divide and conquer.

        Singkatnya, setelah membagikan list menjadi dua bagian terus menerus sampai bagian terkecilnya, kita menjumlahkan kedua nilai list tersebut, seperti pada gambar berikut: