Minggu, 13 April 2014

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


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



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:

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

Reaksi:

0 komentar:

Posting Komentar

WARNING !
Komentar anda tidak boleh mengandung unsur:
1.Penghinaan, Rasis dan Pelecehan
2.Spamming (Spam Comments)
3.Link Iklan, ads etc
Terima Kasih.


Jika ada request ato laporan tentang :
1.Request Software atau Tutorial
2.Bad Link & Re-active link (akibat broken link)
Silakan comment di bawah atau kirim pesan ke saya via facebook >> Akunku : Adhieresthenes Hier Banu Arfakhshad