NPM : 10407113
Kelas : 3 Ib01 B
Mata Kuliah : Algoritma dan pemrograman
Algoritma Devide and Conquer
Terdapat beragam klasifikasi algoritma dan setiap klasifikasi mempunyai alasan tersendiri. Salah satu cara untuk melakukan klasifikasi jenis-jenis algoritma adalah dengan memperhatikan paradigma dan metode yang digunakan untuk mendesain algoritma tersebut. Beberapa paradigma yang digunakan dalam menyusun suatu algoritma akan dipaparkan dibagian ini. Masing-masing paradigma dapat digunakan dalam banyak algoritma yang berbeda.
1.Divide and Conquer, paradigma untuk membagi suatu permasalahan besar menjadi permasalahan-permasalahan yang lebih kecil. Pembagian masalah ini dilakukan terus menerus sampai ditemukan bagian masalah kecil yang mudah untuk dipecahkan. Singkatnya menyelesaikan keseluruhan masalah dengan membagi masalah besar dan kemudian memecahkan permasalahan-permasalahan kecil yang terbentuk.
Divide and Conquer dulunya adalah strategi militer yang dikenal dengan nama divide ut imperes. Sekarang strategi tersebut menjadi strategi fundamental di dalam ilmu komputer dengan nama Divide and Conquer .
Definisi :
1.Divide: membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),
2.Conquer: memecahkan (menyelesaikan) masing-masing upa-masalah (secara rekursif),
Obyek permasalahan yang dibagi :
masukan (input) atau instances yang berukuran n seperti:
- tabel (larik),
- matriks,
- eksponen,
- dll, 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.
2.Dynamic programming, paradigma pemrograman dinamik akan sesuai jika digunakan pada suatu masalah yang mengandung sub-struktur yang optimal (, dan mengandung beberapa bagian permasalahan yang tumpang tindih . Paradigma ini sekilas terlihat mirip dengan paradigma Divide and Conquer, sama-sama mencoba untuk membagi permasalahan menjadi sub permasalahan yang lebih kecil, tapi secara intrinsik ada perbedaan dari karakter permasalahan yang dihadapi.
3.Metode serakah. Sebuah algoritma serakah mirip dengan sebuah Pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap; dan menggunakan pilihan "serakah" apa yang dilihat terbaik pada saat itu.
Pembuat program bertanggung jawab atas implementasi solusi. Pembuatan program akan menjadi lebih sederhana jika masalah dapat dipecah menjadi sub masalah - 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 kriteria berikut:
a. Memenuhi keterhubungan logik antara elemen-elemen data.
b. Operasi-operasi terhadap elemen-elemen data dapat dilakukan secara mudah dan efisien.
4. Pengambilan keputusan mengenai mengenai bahasa pemrograman terbaik untuk menerjemahkan solusi persoalan menjadi program.
Strategi Divide dan Conquer
Strategi Divide dan Conquer memecah masalah menjadi submasalah-submasalah independen yang lebih kecil sehingga solusi submasalah-submasalah dapat diperoleh secara mudah, solusi submasalah-submasalah digabung menjadi solusi seluruh masalah.
Skema umum algoritma divide dan conquer:
Procedure DNC ( i,j : integer )
Var K : integer ;
If SMALL (i,j) then SOLVE (i,j)
Else begin
K : = DIVIDE (i,j)
COMBINE (DNC(i,k),DNC(k+1,j))
End if
Keterangan:
1. SMALL adalah fungsi yang mengirim BOOLEAN, menentukan apakah ukuran telah cukup kecil sehingga solusi dapat diperoleh. Ukuran dinyatakan sebagai telah berukuran kecil bergantung masalah.
2. DIVIDE adalah fungsi membagi menjadi 2 bagian pada posisi K. Biasanya bagian berukuran sama.
3. COMBINE adalah fungsi menggabungkan solusi X dan Y submasalah. Solusi diperoleh dengan memanggil prosedur rekursif DNC.
Jika ukuran kedua submasalah sama, waktu komputasi DNC dideskripsikan hubungan rekuren berikut :
T(n) = g (n), n kecil
2 T (n/2) + f (n), selainnya
dimana :
• T(n) adalah waktu untuk DNC dengan n masukan,
• g(n) adalah waktu komputasi jawaban secara langsung untuk masukan kecil dan
• f(n) adalah waktu COMBINE.
Untuk algoritma divide dan conquer yang menghasilkan submasalah-submasalah dengan tipe masalah yang sama dengan masalah awal, sangat alami untuk mendeskripsikan algoritma secara rekursi. Kemudian untuk meningkatkan efisiensi dilakukan penerjemahan menjadi bentuk iterasi.
Pemakaian teknik Divide dan Conquer banyak digunakan dalam menyelesaikan berbagai macam persoalan, antara lain :
1. Searching
2. Sorting
Sumber:
1. http://mita.staff.gunadarma.ac.id/Downloads/files/14268/Divide%26Conquer.doc (21 Mei 2010)
2. : http://chelseafansclub.multiply.com/journal
http://www.informatika.org/~rinaldi/Stmik/Algoritma %20Divide%20and%20Conquer.ppt
Tidak ada komentar:
Posting Komentar