Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer

-

 Nama     : Fajar Romadhon

NPM        : 20312091

Kelas        : IF20C


Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer

 

    1.        Sejarah Algoritma Devide and 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.

Contoh penting lainnya adalah algoritma yang ditemukan oleh Anatolii A. Karatsuba pada tahun 1960 [8] yang dapat mengalikan dua angka n-digit di O (n log 2 ⁡ 3) {\ displaystyle O (n ^ {\ log _ {2} 3} )} O (n ^ {\ log _ {2} 3}) operasi (dalam notasi Big O). algoritma ini menyangkal dugaan Andrey Kolmogorov tahun 1956 bahwa operasi Ω (n 2) {\ displaystyle \ Omega (n ^ {2})} \ Omega (n ^ {2}) diperlukan untuk tugas tersebut. Sebagai contoh lain dari algoritma 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, yang dijelaskan untuk mesin sortir kartu berlubang sejak tahun 1929.


2.        Devinisi Algoritma Devide and Conquer

Dalam ilmu komputer, Algoritma divide and conquer adalah paradigma desain algoritma yang didasarkan pada rekursi multi-cabang. Algoritme bagi-dan-taklukkan 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.

 

3.        Cara Kerja Algoritma Devide 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 upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif. 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 :

 

1.     Merge sort

2.     Insert sort

3.     Quick sort

4.     Selection sort.

 

 

Link teknokrat :

https://www.teknokrat.ac.id/

http://ti.ftik.teknokrat.ac.id

http://ftik.teknokrat.ac.id

Komentar

Posting Komentar

Postingan populer dari blog ini

ALGORITMA BRANCH and BOUND

-
  ALGORITMA  BRANCH and BOUND   Nama       : Fajar Romadhon NPM        : 20312091 Kelas        : IF20C   Implementasi Algoritma  Branch and Bound   Metode Branch and Bound Metode Branch and Bound adalah sebuah teknik algoritma yang secara khusus mempelajari bagaimana caranya memperkecil Search Tree menjadi sekecil mungkin.     Sesuai dengan namanya, metode ini terdiri dari 2 langkah yaitu : 1.           Branch  artinya membangun semua cabang tree yang mungkin menuju solusi.   2.       Bound  artinya menghitung node mana yang merupakan active node (E-node) dan node mana yang merupakan dead node (D-node) dengan menggunakan syarat batas constraint (kendala).   Teknik Branch and Bound Berikut adalah  teknik dalam Branch and Bound yaitu   :   1.       FIFO Branch and Bound adalah teknik Branch and Bound yang menggunakan bantuan queue untuk perhitungan Branch  and Bound secara First In First Out.   2.       LIFO Branch and Bound adalah teknik Branch and Bound yang menggunakan bantuan stack u
Baca selengkapnya

Menjelaskan definisi dan perbedaan antara Threads dan Processes.

-
  Apa itu proses? Sebuah proses, secara umum, adalah serangkaian terus menerus dari tindakan untuk mencapai hasil yang spesifik. Namun, dalam dunia komputer, proses adalah sebuah contoh dari mengeksekusi program komputer. Dengan kata lain, itu adalah konsep dari kejadian tunggal dari program komputer yang berjalan. Proses yang berjalan secara binar akan mengandung satu atau lebih thread. Menurut jumlah thread yang terlibat dalam proses, ada dua jenis proses. Mereka adalah proses single-thread dan proses multi-thread. Seperti namanya, proses tunggal-thread adalah proses yang hanya memiliki satu thread. Oleh karena itu, thread ini adalah sebuah proses, dan hanya ada satu aktivitas yang terjadi. Dalam proses multi-thread, ada lebih dari satu thread, dan ada lebih dari satu aktivitas yang terjadi. Dua atau lebih proses dapat berkomunikasi dalam setiap menggunakan komunikasi antar-proses lain. Tapi itu cukup sulit dan membutuhkan lebih banyak sumber daya. Ketika membuat proses baru programm
Baca selengkapnya