Algoritma Divide dan Conquer

Divide and Conquer adalah metode pemecahan

masalah yang bekerja dengan membagi masalah menjadi

beberapa upa-masalah yang lebih kecil, kemudian

menyelesaikan masing-masing upa-masalah tersebut

secara independen, dan akhirnya menggabungkan solusi

masing-masing upamasalah sehingga menjadi solusi dari

masalah semula.

Pada algortima Divide and Conquer ini meiliki tiga proses

utama yaitu:

- Divide: membagi masalah menjadi beberapa upamasalah

yang memiliki kemiripan dengan masalah semula namun

berukuran lebih kecil (idealnya berukuran hampir sama),

- Conquer: memecahkan (menyelesaikan) masingmasing

upa-masalah (secara rekursif), dan

- Combine: mengabungkan solusi masing-masing upamasalah

sehingga membentuk solusi masalah semula.

Pada algoritma ini, 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.

Secara umum, algoritma Divide and Conquer memiliki

sekema sbb:

procedure DIVIDE_and_CONQUER(input n :

integer)

{ Menyelesaikan masalah dengan

algoritma Dand-

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

Dalam Algoritma divide dan conquer Pemrogram 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

Metode

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 : http://pdflost.com/download/5991507/

Algoritma Kruskall

Contoh : Pandang sebuah graph sebagai berikut;

Algoritma Kruskall

Dasar pembentukan algoritma Kruskal berasal dari analogi growing forest. Growing forest maksudnya adalah untuk membentuk pohon merentang minimum T dari grafG adalah dengan cara mengambil satu per satu sisi dari graf G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya iterasi untuk setiap sisi, maka forest akan memiliki pohon yang semakin sedikit. Oleh sebab itu, maka analogi ini disebut dengan growing forest. Algoritma Kruskal akan terus menambahkan sisi – sisi ke dalam hutan yang sesuai hingga akhirnya tidak akan ada lagi forest dengan, melainkan hanyala

h sebuah pohon yang merentang minimum.Soal diatas dapat dijawab dengan menggunakan Algoritma Kruskall seperti ditunjukkan dibawah ini :.

-------Edge----- Cost

1. ( 1,2 )----- 10
   
2. ( 3,6 )----- 15
   
3. ( 4,6 )----- 20
   
4. ( 2,6 )----- 25
   
5. ( 1,4 )----- 30
6. ( 3,5 )----- 35

Maka Spanning Tree- nya adalah

Sehingga total costnya ialah 105

Tugas: (minimum spanning tree dan total cost nya)

TEKNIK SORTING DAN SEARCHING

Teknik Sorting

Sorting bisa didefinisikan sebagai suatu proses pengurutan data yang
sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut
suatu aturan tertentu. Sorting yang kita terapkan menggunakan tipe data array agar
pemahaman serta pengimplementasiannya lebih mudah. Pada umumnya terdapat
dua jenis pengurutan :
- Ascending (Naik).
- Descending (Turun).
Contoh :
Data : Array [1..6] of Byte = (22, 10, 15, 3, 8, 2);
Data Acak : 22 10 15 3 8 2
Terurut Ascending : 2 3 8 10 15 22
Terurut Descending : 22 15 10 8 3 2

Metode Pengurutan Data
- Pengurutan berdasarkan perbandingan (comparison-based sorting)
• Bubble sort, exchange sort
- Pengurutan berdasarkan prioritas (priority queue sorting method)
• Selection sort, heap sort
- Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep
sorted method)
• Insertion sort, tree sort
- Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer
method)
• Quick sort, merge sort
- Pengurutan berkurang menurun (diminishing increment sort method)
• Shell sort

Teknik Searching
Searching merupakan suatu proses pendarian data dari sejumlah data yang
ada. Pencarian data dapat dilakukan pada sejumlah data yang sudah terurut atau
juga pada data yang sama sekali belum terurut. Kita mencoba menggunakan dua
metode pencarian yaitu :
- Pencarian Berurutan (Sequential Searching).
Metode ini merupakan metode paling sederhana, secara garis besar metode
ini bisa dijelaskan sebagai berikut. Dari data yang diketahui, data yang dicari
dibandingkan satu per satu sampai data tersebut ditemukan atau tidak ditemukan.
Pada saat data yang dicari sudah ditemukan, maka proses pencarian langsung
dihentikan. Tetapi jika belum ditemukan, maka pencarian diteruskan sampai
seluruh data dibandingkan.

- Pencarian Biner (Binary Seacrh).
Metode ini digunakan jika sejumlah data telah diurutkan. Jika dibandingkan
dengan metode awal tadi metode ini jauh lebih cepat. Secara garis besar metode
ini bisa dijelaskan sebagai berikut. Urutkan dahulu sejumlah data. Lalu bagi dua
data-data tadi dengan jumlah data yang sama pada masing-masingnya. Kemudian
data dibandingkan dengan data terakhir dari subdata yang pertama. Jika data yang
dicari lebih keci, pencarian dilanjutkan pada sub data pertama dengan terlebih
dahulu membagi dua lagi data-data tersebut dengan jumlah yang sama. Tetapi jika
data yang dicari lebih besar dari data terakhir subdata pertama, berarti data yang
dicari kemungkinan terletak pada subdata yang kedua. Proses diatas dilakukan
berulang sampai data ditemukan atau tidak ditemukan.

STRUKTUR DATA

Struktur data adalah kelompok item data yang terorganisasi yang dianggap sebagai salah satu unit, struktur data disebut juga jenis data kompleks.

Beberapa sturktur data

1. Array
array merupakan set item data yang disusun secara baik menjadi rangkaian dan diacu atau ditunjuk oleh suatu identifier.
contoh : Nilai = (46 78 56 79)

klasifikasi array
- array 1 dimensi
- array multi dimensi

pendeklarasian array
- array 1 dimensi
variable
Nilai : array [1 . . 5] of integer
A : array [1. . 4] of real

-array multi dimensi
Variable
A : array [1 . . 5, 1 . . 2] of integer

2. String
string merupakan karakter yang ditangani sebagai unit data tunggal.
contoh :
variable string
- A : "universitas"
- B : "gunadarma"

klasifikasi string
-fixed length string
yaitu string yang mempunyai jumlah tempat karakter yang tetap yang tersedia, bisa digunakan untuk penyimpanan data.
-viriable length string
yaitu string untuk memberi data sejumlah spasi (ruang) sesuai yang diperlukan.

pendeklarasian string
-fixed length string
variables
Nama : string [5]
-variables length string
Nama : string

PERBANDINGAN BAHASA PEMROGRAMAN

1. Bahasa C

Aplikasi bahasa C :

• Bahasa C pertama kali digunakan di Computer Digital Equipment Corporation PDP-11 yang menggunakan system operasi UNIX.

• Bahasa C juga digunakan untuk menyusun operasi Linux

• Banyak bahasa pemrogaman popular seperti PHP dan Java menggunakan sintaks dasar mirip bahasa C.

Kelebihan dan Kekurangan Bahasa C

Kelebihan Bahasa C

• Bahasa C tersedia hampir di semua jenis computer

• Kode bahasa C sifatnya adalah portable dan fleksible untuk semua jenis computer

• Bahasa C hanya menyediakan sedikit kata-kata kunci, hanya terdapat 32 kata kunci

• Proses executable program bahasa C lebih cepat

• Dukungan pustaka yang banyak

• C adalah bahasa yang terstruktur

• Bahasa C termasuk bahasa tingkat menengah

Kekurangan Bahasa C

• Banyaknya operator serta fleksibilitas penulisan program kadang-kadang membingungkan pemakai

• Bagi pemula pada umumnya akan kesulitan menggunakan pointer

2. Bahasa Pascal

Aplikasi Bahasa Pascal

• Pascal dipakai sebagai landasan pembuatan kode perangkat lunak Delphi (berbasis windows)

• Pascal dipakai sebagai landasan pembuatan kode perangkat lunak Kylix (berbasis Linux)

Kelebihan dan kekurangan

Kelebihan bahasa pascal :

• Tipe data standar, tipe-tipe data standar yang telah tersedia bahasa pemrogaman. Pascal memiliki tipe data standar Boolean, integer, char, real, string.

• User defined data types, programmer dapat membuat tipe data lain yang diturunkan dari tipe data standar.

• Strongly-typed, programmer harus menentukan tipe data dari suatu variable dan variable tersebut tidak dapat dipergunakan untuk menyimpan tipe data selain format yang ditentukan.

• Terstruktur, memiliki sintaks yang memungkinkan penulisan program dipecah menjadi fungsi-fungsi kecil (procedur dan function) yang dapat dipergunakan berulang-ulang.

• Sederhana dan ekspresif, memiliki struktur yang sederhana dan sangat mendekati bahasa manusia (bahasa inggris) sehingga mudah dipelajari dan dipahami.

Kekurangan bahasa pascal :

• Versi awal Pascal kurang cocok untuk aplikasi bisnis karena dukungan basisdata yang terbatas.

• Sintaks Pascal terlalu bertele-tele

• Tidak mendukung pemrograman berorientasi objek

• Pascal tidak fleksibel dan banyak kekurangan yang dibutuhkan untuk membuat aplikasi yang besar.

3. Bahasa Cobol

Aplikasi bahasa COBOL

• Untuk membuat aplikasi bisnis

• Untuk pengolahan data dan database

Kelebihan dan Kekurangan

Kelebihan :

• Program COBOL dibuat dalam instruksi bahasa inggris, sehingga lebih mudah dipelajari dan dibuat.

• Program COBOL sesuai untuk pengolahan data yang banyak diterapkan pada permaslahan .

• Program COBOL sifatnya standard, sehingga dapat dipergunakan pada komputer-komputer yang berbeda, tanpa banyak perbedaan.

• Struktur program COBOL jelas, sehingga dapat dimengerti oleh orang seperti akuntan, auditor, atau manajer-manajer yang hanya mempunayai pengetahuan pengolahan data yang sedikit.

• COBOL menyediakan fasilitas Listing Program, bilamana perlu dapat diperiksa oleh orang lain selain programer.

• Mudah didokumentasikan dan dikembangkan bilamana perlu

• Problem Orientad Language

Kekurangan :

• Operasi masukan dan keluaran yang masih kaku

• Struktur penulisan program yang sangat kaku dan bertele-tele

( sumber : http://ndet.wordpress.com/2008/04/12/bahasa-pemrograman/ )

Algoritma dan Pemerograman

Algoritma

Algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.

Desain dan analisis algoritma adalah suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik dan performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari implementasi algoritma tersebut. Dalam cabang disiplin ini algoritma dipelajari secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama.

Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal, algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.

• Jenis-Jenis Algoritma

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.

• 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.

• 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.

• 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.

• Pemrograman

Pemrograman adalah Pemrograman adalah sebuah seni dalam menggunakan satu atau lebih algoritma yang saling berhubungan dengan menggunakan sebuah bahasa pemrograman tertentu sehingga menjadi sebuah program komputer. Bahasa pemrograman yang berbeda mendukung gaya pemrograman yang berbeda pula.

• Tujuan dari Pemrograman
  

Tujuan dari pemrograman adalah untuk memuat suatu program yang dapat melakukan suatu perhitungan atau 'pekerjaan' sesuai dengan keinginan si pemrogram. Untuk dapat melakukan pemrograman, diperlukan keterampilan dalam algoritma, logika, bahasa pemrograman, dan di banyak kasus, pengetahuan-pengetahuan lain seperti matematika.

• macam-macam bahasa pemrograman

• C, C++, C#, Pascal, Basic, Perl, PHP, ASP, JHP, Java, dll.