Algoritma Divide dan Conquer
Nama : Risa Septiana
Npm : 20312122
Kelas : IF 20 E
Sejarah Algoritma Divide dan Conquer
Awal dari algoritma ini utamanya adalah pengurangan dan penaklukan - masalah asli secara berturut-turut dipecah menjadi sub-masalah tunggal, dan memang dapat diselesaikan secara berulang.
Pencarian 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 diurutkan untuk memfasilitasi pencarian tanggal kembali 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 subproblem ekuivalen yang lebih kecil dan lebih kecil, yang berasal dari beberapa abad SM.
Contoh awal dari algoritma bagi-dan-taklukkan 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 mereka ditemukan kembali lebih dari satu abad kemudian.
Algoritma D&C dua sub problem awal yang secara khusus dikembangkan untuk komputer dan dianalisis dengan benar adalah algoritma pengurutan gabungan, yang ditemukan oleh John von Neumann pada tahun 1945.
Definisi Algoritma Divide dan Conquer
- ✓ Divide: membagi persoalan menjadi beberapaupa-masalah yang memiliki kemiripan denganpersoalan semula namun berukuran lebih kecil(idealnya berukuran hampir sama)
- ✓Conquer (solve): menyelesaikan masing-masingupa-masalah (secara langsung atau secararekursif).
>Divide: membagi persoalan menjadi beberapa sub sub masalah yang memiliki
kemiripan dengan persoalan semula namun berukuran lebih kecil(idealnya
berukuran hampir sama).
>Conquer (solve): dalam langkah ini kita mencoba menyelesaikan masalah atau
data yang telah dipecahkan pada langkah pertama, dengan menggunakan
algoritma sederhana.
>Combine: menggabungkan solusi masing-masing sub sub masalah sehingga
membentuk solusi atau hasil akhir dari persoalan semula.
Komentar
Posting Komentar