Strategi Algoritma : Divide and Conquare (Kasus Min Max, Merge Sort, Mencari Koin palsu, Knapsack I/O

Apa kabar sobat informatika, sudah lama rasanya aku jarang aktif untuk memposting artikel maupun tutorial, karena akhir-akhir ini aku sedang "ripuh" mengurus laporan kerja praktik dan mempersiapkan untuk skripsi >.<.  Tapi, tetap bersukur masih bisa sempet membuka blogku ini yang udah lama kurang ke urus, seperti rumah berisikan barang usang yang dipenuhi sarang spiderman dan di huni oleh cucu-cucunya? a.k.a (artikel tdk update) hehe, Kok curhat? haduh!

okay, langsung aja deh ke pokok hal yang ingin dibahas,pada hari selasa lalu waktu bandung timur(WBT) ^^, aku di kasih tugas oleh dosen, yaitu disuruh buat algoritma dan program yang menggunakan strategi algoritma divide and conquare. 

Baiklah apa itu Strategi algoritma?

Strategi algoritma merupakan kumpulan algoritma yang disusun dari berbagai macam metode (cara) untuk menyelesaikan masalah dan sudah di definisikan, di gagas, di bukukan oleh si pembuat algoritma menjadi ke banyak metode penyelesaian. 

Nah disini aku ingin membahas salah satu metode yang cukup populer dan terkenal di kalangan mahasiswa informatika atau mungkin mahasiswa matematika. Yaitu, Metode Divide and Conquer dimana dulunya adalah strategi militer yang dikenal dengan nama divide ut imperes.Sekarang strategi tersebut  menjadi strategi fundamental di dalam ilmu komputer.

Definisi

Divide:  membagi masalah menjadi beberapa sub-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),

Conquer: memecahkan (menyelesaikan) masing-masing sub-masalah (secara  rekursif), dan

Combine: mengabungkan solusi masing-masing sub-masalah sehingga membentuk solusi masalah semula.

Obyek permasalahan yang dibagi :
    masukan (input) atau instances yang berukuran n seperti:
    - tabel (larik),
    - matriks,
    - eksponen,
    - dll, bergantung pada masalahnya.

Tiap-tiap sub-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif.

Skema umum algoritma divide and conquare
procedure DIVIDE_and_CONQUER(input n : integer) { Menyelesaikan masalah dengan algoritma D-and-C. Masukan: masukan yang berukuran n Keluaran: solusi dari masalah semula } Deklarasi r, k : integer Algoritma if n <= n0 then {ukuran masalah sudah cukup kecil } SOLVE upa-masalah yang berukuran n ini else Bagi menjadi r upa-masalah, masing-masing berukuran n/k for masing-masing dari r upa-masalah do DIVIDE_and_CONQUER(n/k) endfor COMBINE solusi dari r upa-masalah menjadi solusi masalah semula } endif

Berikut adalah skema umum jika pembagian selalu menghasilkan dua sub masalah yang berukuran sama.
Gunakan T(n) =  g(n),  jika  n <= n0 ;  atau
                2T(n/2) + f(n),  n >n0

procedure DIVIDE_and_CONQUER(input n : integer) { Menyelesaikan masalah dengan algoritma D-and-C. Masukan: masukan yang berukuran n Keluaran: solusi dari masalah semula } Deklarasi r, k : integer Algoritma if n <= n0 then {ukuran masalah sudah cukup kecil } SOLVE upa-masalah yang berukuran n ini else Bagi menjadi 2 upa-masalah, masing-masing berukuran n/2 DIVIDE_and_CONQUER(upa-masalah pertama yang berukuran n/2) DIVIDE_and_CONQUER(upa-masalah kedua yang berukuran n/2) COMBINE solusi dari 2 upa-masalah endif

penyelesaian dengan metode divide & conquare:
Illustrasi Gambar 4.1

• Ukuran tabel hasil pembagian dapat dibuat cukup kecil sehingga mencari minimum dan maksimum dapat diselesaikan (SOLVE) secara lebih mudah.
• Dalam hal ini, ukuran kecil yang dipilih adalah 1 elemen atau 2 elemen. 

 Gambar 4.2

Algoritma cara penyelesaian kasus Min Max dengan Divide & Conquare: MinMaks(A, n, min, maks) Untuk kasus n = 1 atau n = 2, SOLVE: Jika n = 1, maka min = maks = A[n] Jika n = 2, maka bandingkan kedua elemen untuk menentukan min dan maks. Untuk kasus n > 2, (a) DIVIDE: Bagi dua tabel A menjadi dua bagian yang sama, A1 dan A2 (b) CONQUER: MinMaks(A1, n/2, min1, maks1) MInMaks(A2, n/2, min2, maks2) (c) COMBINE: if min1 <min2 then min <- min1 else min <- min2 if maks1 <maks2 then maks <- maks2 else maks <- maks1

Untuk lebih detail silakan download file dibawah ini,  apabila ada kekeliruan di algoritmanya silahkan berikan kritik dan sarannya yang bersifat membangun pada kotak komentar, Trims.
    

Download Materi Diktat Strategi Algoritma 
Download Contoh Kasus Lengkap Algoritma Min Max - Knapsack I/O