Failure is an Options!

Keep Strugle for what you want to achieve

The Future is in your hand,

Future bright only if you have a plan and action to making happen.

The Maturity and Wisely!

Success people always have positive vibe with maturity of thinking and wisely attitude in living

The time is limited

Never waste your time, Because time is precious like a life and money

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