TUGAS ANALISIS DAN STRATEGI ALGORITMA - ALGORITMA DIVIDE AND CONQUER

                                               ALGORITMA DIVIDE AND CONQUER

Nama : Senda Wahyu Andika

Kelas : TK 19C

NPM : 19316031

A. PENGERTIAN ALGORITMA DIVIDE AND CONQUER

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 lebih 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. 

B. SEJARAH ALGORITMA DIVIDE AND CONQUER

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 algoritme ini utamanya adalah pengurangan dan penaklukan - masalah asli secara berturut-turut dipecah menjadi sub-masalah tunggal , dan memang dapat diselesaikan secara berulang. Penelusuran biner, algoritma penurunan-dan-taklukkan 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 penurunan dan taklukkan kuno lainnya adalah algoritma Euclidean untuk menghitung pembagi persekutuan terbesar dari dua bilangan dengan mengurangi bilangan tersebut menjadi sub problem ekuivalen yang lebih kecil dan lebih kecil, yang berasal dari beberapa abad SM.

Contoh awal dari algoritma bagi dan taklukkan dengan beberapa sub problem adalah deskripsi Gauss tahun 1805 tentang apa yang sekarang disebut algoritma Cooley - Turkey FastFourier Transform (FFT), meskipun dia tidak menganalisis jumlah operasi nya secara kuantitatif, dan FFT tidak tersebar luas sampai ditemukan kembali lebih dari satu abad kemudian. Algoritma D&C dua sub problem awal yang secara khusus dikembangkan untuk komputer dan dianalisis dengan tepat adalah algoritme 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  {\ displaystyle O (n ^ {\ log _ {2} 3})} operasi (dalam notasi Big O ). Algoritma ini membantah dugaan 1956 Andrey Kolmogorof itu  {\ displaystyle \ Omega (n ^ {2} operasi akan diperlukan untuk tugas itu. Sebagai contoh lain dari algoritme 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. 

C. CARA KERJA ALGORITMA DIVIDE AND CONQUER

 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.

FAKULTAS TEKNIK DAN ILMU KOMPUTER  : http://ti.ftik.teknokrat.ac.id 

UNIVERSITAS TEKNOKRAT INDONESIA        : https://teknokrat.ac.id/