"Selamat Datang Di Blog Diah Afrianti Rahayu": LANJUTAN LOGIKA DAN ALGORITMA :)

Kamis, Maret 13, 2014

LANJUTAN LOGIKA DAN ALGORITMA :)

PERTEMUAN 9 DAN 10

LARIK (ARRAY)

Didalam Bahasa Pemrograman Pascal (juga di bahasa pemrog. Yang lain) memiliki berbagai macam tipe data.

Tipe data dikelompokkan menjadi :

Tipe data sederhana
Tipe data terstruktur
Tipe data enumerated
Tipe data Pointer

Di Pertemuan telah dibahas:

tipe data sederhana (integer, Boolean, real, string, char dsb).

Tipe data terstruktur

Didalam tipe data terstruktur dikenal ada 2 tipe data:

Larik (array)
Record.

Larik/ Array à sekumpulan kotak (variable) yang menyimpan sekumpulan elemen bertipe sama secara berurutan (sequential).

Bentuk umum :

Nama _larik:array[tipe indeks] of tipe larik

Ciri-ciri Array :

- setiap elemen data array diacu melalui indeksnya

- karena elemen disimpan secara berurutan , indek array harus lah suatu tipe yang mempunyai keterurutan (ada suksesor dan predecessor).

Contoh bertipe data : integer, karakter atau tipe data enumerasi.

Jika indeks integer maka keterturutan indeks sesuai dengan urutan integer (0,1,2,3,4,5,6,..)

Jika indeks Karakter maka keterturutan indeks sesuai dengan urutan karakter (a,b,c,d,e ….).

contoh : x:array[1..11] of integer;
var gaji:array[5..10] of char;

DIMENSI LARIK /ARRAY

Larik dimensi 1 à larik yang memiliki 1 index
Larik Dimensi 2 atau lebih à larik yang memiliki indek > 1. (larik dengan banyak dimensi)

Untuk deklarasi Array 1 dimensi ada pada contoh diatas.

Untuk deklarasi Array 2 dimensi:

nama array=array[tipeindeks1,tipeindeks2] of tipe array

contoh :

A : array[1..3,1..2] of byte;

Sallah satu implemantasi array 2 dimensi ini digunakan untuk membuat program MATRIK (Aljabar Linear).

Contoh Matrik dengan ordo 2 x 2

Matrik A diatas adalah matrik dengan ordo 2x2 sehingga matrik tersebut memiliki elemen : A[1,1] = 1, A[1,2] = 5, A[2,1]= 2 dan A[2,2]=4.

Untuk membuat deklarasi tipe array dari kasus diatas (dalam Bahasa Pascal) :

Var A : array [1..2,1..2] of integer;

Untuk mengisi elemen matrik A diatas :

A[1,1] := 1;

A[1,2] := 5;

A[2,1] := 2;

A[2,2] := 4;

Untuk menampilkan isi elemen matrik A :

Write(A[1,1]);

Write(A[1,2]);

Write(A[2,1]);

Write(A[2,2]);

Selain cara diatas, untuk mengefisienkan penulisan kode program dalam menampilkan isi Matrik A, maka digunakan proses perulangan :

For i:=1 to 2 do

For j:=1 to 2 do

Write(A[i,j]);

METODE DEVIDE AND CONQUER

Pengurutan (Sorting).

· proses mangatur sekumpulan obyek/data menurut urutan atau susunan tertentu.

· Urutan obyek/data tersebut dapat menaik (ascending) atau menurun (desencending).

· Data yang diurutkan dapat berupa data bertipe dasar atau data bertipe struktur

· Data yang sudah terurut memiliki keuntungan yaitu Mempercepat proses pencarian data.

Metode Pengurutan

Algoritma pengurutan / sorting bermacam-macam dan setiap algoritma ini memiliki kinerja yang berbeda-beda. Berikut ini macam-macam algoritma pengurutan:

1. Metode Selection Sort

2. Metode Buble Sort

3. Metode Merge Sort

4. Metode Quick Sort

5. Metode Insertion

Hal yg mempengaruhi Kecepatan Algoritma Sorting adalah Jumlah Operasi Perbandingan & Jumlah OperasiPemindahan Data

1. Selection Sort (Metode Seleksi).

Tehnik pengurutan dengan cara pemilihan elemen dgn memilih elemen data terkecil utk kemudian dibandingkan & ditukarkan dgn elemen pd data awal, dst s/d seluruh elemen shg akan menghasilkan pola data yg telah disort.

• Merupakan kombinasi antara sorting dan searching

• Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array.

• Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]).

ALGORITMA SELECTION SORT.

Pengecekan dimulai data ke-1 sampai dengan data ke-n
Tentukan bilangan dengan Index terkecil dari data bilangan tersebut
Tukar bilangan dengan Index terkecil tersebut dengan bilangan pertama ( I = 1 ) dari data bilangan tersebut
Lakukan langkah 2 dan 3 untuk bilangan berikutnya ( I= I+1 ) sampai didapatkan urutan yg optimal

Ilustrasi Algoritma Selection Sort

PENULISAN ALGORITMA KE DALAM PROGRAM

Algoritma metode seleksi :

- langkah 0 : Baca vector yang akan diurutkan (dalam program utama)

- langkah 1 : Kerjakan langkah 2 sampai 4 untuk i = 1 sampai N -1

- langkah 2 : Tentukan awal = i , kerjakan langkah 3 untuk j = i +1 sampai N

- langkah 3 : (Mencari data terkecil)

Tes : apakah A[awal] > A[j], jika ya maka ubah awal = j

- langkah 4 : Tukarkan nilai A[awal] dengan A[i]

- langkah 5 : selesai

program pascal;

uses crt;

VAR

Data : array[1..10] of integer;

i,j,n,bantu : integer;

BEGIN

clrscr;

Writeln('Masukkan data anda !');writeln;

Write('jumlah data anda ? ');readln(n);

writeln('Mulai memasukan data ');

for i:=1 to n do

begin

Write('Data ke-',i,' = ');

readln(data[i]);

end;

for i:=1 to N-1 do

for j := i+1 to N do

begin

if data[i] > data[j] then

begin

Bantu := data[i];

data[i] := data[j];

data[j] := Bantu;

end;

for i:=1 to n do

write('(',data[i],'),');

readln;

end.

Hasil program

Masukkan data anda !

jumlah data anda ? 5

Mulai memasukan data

Data ke-1 = 4

Data ke-2 = 6

Data ke-3 = 2

Data ke-4 = 8

Data ke-5 = 5

(2),(4),(5),(6),(8),

2. Metode Bubble Sort (Gelembung)

Teknik yang diinspirasi oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung lebih ringan dari pada air, maka gelembung akan naik keatas.

(benda yang berat akan terbenam, benda ringan terapung).

Elemen data yang paling kecil diapungkan “diangkat keatas” melalui proses pertukaran.

Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya

Algoritma Bubble Sort

Pengecekan mulai dari data ke-1 sampai data ke-n
Bandingkan data ke-n dengan data sebelumnya (n-1)
Jika lebih kecil maka pindahkan bilangan tersebut dengan bilangan yg ada didepannya ( sebelumnya ) satu persatu (n-1,n-2,n-3,....dst)
Jika lebih besar maka tidak terjadi pemindahan
Ulangi langkah 2 dan 3 s/d sort optimal.

Analogi :

Larik dengan urut menaik, elemen larik yang berharga paling kecil ‘diapungkan’, artinya diangkat ke atas (atau ke ujung kiri larik) melalui proses pertukaran.

Proses pengapungan ini dilakukan sebanyak N-1 langkah dengan N adalah ukuran larik.

Pada akhir setiap langkah ke-I, larik L[1..N] akan terdiri atas dua bagian yaitu bagian yang sudah terurut, yaitu L[1..I] dan bagian yang belum terurut L[I+1..N]. Setelah langkah terakhir, diperoleh larik L[1..N] yang terurut menaik.

Contoh 2 :

Contoh 3 :

Bubble Sort Disebut juga dengan metode Penukaran (Exchange Sort), yaitu metoda yang mendasarkan pada penukaran elemen untuk mencapai keadaan urut yang diinginkan.

Algoritma Metode gelembung :

- langkah 0 : Baca vector yang akan diurutkan (dalam program utama)

- langkah 1 : Kerjakan langkah 2 untuk i = 1 sampai N-1

- langkah 2 : Kerjakan langkah 3 untuk j = 1 sampai N- i

- langkah 3 : Tes apakah A[j] > A[j +1] ? Jika ya, tukarkan nilai kedua elemen ini

- langkah 4 : Selesai

Contoh Program Buble Sort

program pascal;

uses crt;

VAR

Data : array[1..10] of integer;

i,j,n,bantu : integer;

BEGIN

clrscr;

Writeln('Masukkan data anda !');writeln;

Write('jumlah data anda ? ');readln(n);

writeln('Mulai memasukan data ');

for i:=1 to n do

begin

Write('Data ke-',i,' = ');

readln(data[i]);

end;

for i:=1 to N-1 do

for j := 1 to N-i do

begin

if data[j] > data[j+1] then

begin

Bantu := data[j];

data[j] := data[j+1];

data[j+1] := Bantu;

end;

for i:=1 to n do

write('(',data[i],'),');

readln;

end.

Hasil :

Masukkan data anda !

jumlah data anda ? 5

Mulai memasukan data

Data ke-1 = 5

Data ke-2 = 3

Data ke-3 = 6

Data ke-4 = 2

Data ke-5 = 3

(2),(3),(3),(5),(6),

3. Metode INSERTION SORT (Sisip)

Algoritma ini dianalogikan seperti mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya.

Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya.

Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang

Analogi :

mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.

Seluruh kartu diletakkan pada meja, kita sebut meja pertama, disusun dari kiri ke kanan dan atas ke bawah.

Kemudian pada meja kedua tempat meletakkan kartu yang diurutkan.

Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama dan letakkan pada meja kedua.

Ambil kartu kedua dari meja pertama, bandingkan dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang sesuai setelah perbandingan.

Proses tersebut akan berlangsung hingga seluruh kartu pada meja pertama telah diletakkan berurutan pada meja kedua.

Contoh :

Jika sudah terurut 3,6,9, dan selanjutnya belum terurut 5,7,2,....
5 akan disisipkan di antara 3 dan 6, sehingga menjadi 3,5,6,9.

7 akan disisipkan di antara 6 dan 9, sehingga menjadi 3,5,6,7,9.
2 akan disisipkan sebelum 3, sehingga menjadi 2,3,5,6,7,9.

Contoh :

METODE DEVIDE AND CONQUER

Devide and Qonquer adalah metode pemecahan masalah yang bekerja dengan membagi masalah/problem menjadi beberapa sub-masalah/sub-problem yang lebih kecil, kemudian menyhelesaikan masing-masing sub-masalah secara independen dan akhirnya menggabungkan solusi masing-masing sub masalah sehingga menjadi solusi masalah semula.

Masalah à sub masalah 1 à Sub solusi 1 à Solusi masalah

Sub masalah 2 à sub solusi 2

Sub-masalah 3 à Sub solusi 3

Algortima devide and conquer menawarkan penyederhanaan masalah dengan pendekatan 3 langkah masalah:

pembagian masalah menjadi sekecil mungkin
penyelesaian masalah-masalah yang dikecilkan
penggabungan solusi untuk mendapatkan solusi optimal secara keseluruhan.

tipe algoritma yang mengimplementasikan/kategori D&C antara lain

merge sort

4. Metode Merge Sort

Merge sort adalah algoritma yang digunakan untuk menyusun list yang diberikan dengan cara membagi list yang diberikan menjadi dua bagian yang lebih kecil. Kedua list yang baru ini kemudian akan disusun secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk list baru yang merupakan hasil penggabungan dua buah list sebelumnya

Konsep :

1). Array yang belum terurut, dibagi menjadi separuh

– Proses diulang terus sampai ditemukan bagian terkecil

2). Hasil dari setiap proses digabungkan :

– membandingkan elemen pertama dari setiap bagian

– hapus elemen terkecil dan letakan pada hasil

– Ulangi semua proses sampai semua elemen terurut

3 9 4 1 5 2

List diatas dibagi menjadi dua bagian:

list 1:     |    list 2:

3 9 4       |    1 5 2

Kedua list yang baru disusun sendiri-sendiri menjadi:

list 1:     |    list 2:

3 4 9       |    1 2 5

Setelah itu dubentuk list baru yang merupakan gabungan kedua list tadi:

List baru:

list 1:     |    list 2:

3 4 9       |    2 5

List baru:

1 2

list 1:     |    list 2:

3 4 9       |    5

List baru:

1 2 3

list 1:     |    list 2:

4 9         |    5

List baru:

1 2 3 4

list 1:     |    list 2:

9           |    5

List baru:

1 2 3 4 5

list 1:     |    list 2:

9           |    kosong

List baru:

1 2 3 4 5 9

list 1:     |    list 2:

kosong      |    kosong

Dan akhirnya akan didapat list yang sudah tersusun:

List:

1 2 3 4 5 9

Contoh 2

Contoh : data berikut ini akan diurutkan

1). Divide/membagi data yang tidak terurut menjadi dua bagian

2). Ulangi sampai setiap array hanya memiliki sebuah data

3). Lakukan merge untuk memperoleh data terurut

1).
2).
3).
4).
5).
6).
7).
8).
9).
10).
11).
12).
13).
14).
15).
16).
17).
18).
19).
20).
21).
22).
23).
24).
25).
26).
27).
28).
29).
30).
31).
32).
33).
34).
35).
36).
37).
38).
39).

Teknik Serching

Proses pencarian à menemukan harga/data tertentu didalam sekumpulan harga yang bertipe sama.

Dalam proses pemrograman serching/pencarian biasanya digunakan untuk

- proses update atau penghapusan data à sebelumnya melakukan proses pencarian data.

- Penyisipan data pada sekumpulan data, jika data sudah ada maka proses penyisipan tidak diperkenankan. Jika data tidak ada maka proses penyisipan dilakukan àtujuan digunakan agar tidak terjadi duplikasi data

1. Tehnik Pencarian Tunggal :

· Tehnik Sequential Search / Linier Search

· Tehnik Binary Search

PENCARIAN SEQUENTIAL

· Merupakan algoritma pencarian yang sangat sederhana.

· Proses pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan dan seluruh elemn sudah diperiksa.

13 16 14 21 76 21

Nilai yang dicari: 21

Maka elemen yang diperiksa : 13 16 14 21

Index ketemu : 4

Nilai yang dicari: 13

Maka elemen yang diperiksa : 13

Index ketemu : 1

Nilai yang dicari: 15

Maka elemen yang diperiksa : 13 16 14 21 76 21

Index ketemu : 0

Algoritma dari proses Pencarian diatas adalah:

1. Tentukan i=1, Ketemu = 0.

2. Masukan Nilai X à nilai yang dicari.

3. Jika Nilai[i] <> X maka i=i+1, kembali kelangkah 2.

4. Jika Nilai[i] = X maka Ketemu =i.

5. Jika Ketemu = 0 maka Cetak “nilai X tidak ketemu”

6. Jika tidak (Ketemu <>0)Cetak “nilai X ketemu pada posisi Ketemu”

7. Selesai

Pencarian Binary Search

· Metode pencarian yang diterapkan pada sekumpulan data yang sudah terurut (menaik maupun menurun)

· Metode ini digunakan untuk melakukan pencarian secara cepat dengan data yang sudah terurut.

Konsep Pencarian Binary/Bagi Dua

· Pilih Indek Kiri (Low) dan Indek Kanan (High)

· Langkah 1:

Bagi dua elemen larik pada elemen tengah.

Elemen tengah adalah elemen dengan indek middle=(low+high) div 2.

Elemen tengah (middle), akan membagi array menjadi 2 bagian yaitu:

ð Bagian kiri, dengan index LARIK[Low .. middle-1]

ð Bagian Kanan, dengan index LARIK[middle+1..High]

· Langkah 2:

ð Periksa apakah LARIK[middle] = X , pencarian akan dihentikan sebab X sudah ditemukan

ð Jika LARIK[middle] <> X, maka kita tentukan pencarian akan dilakukan disebelah kiri atau kanan.

§ Jika LARIK[middle] < X, maka pencarian dilakukan dibagian kiri LARIK

§ Jika LARIK[middle] > X, maka pencarian dilakukan di bagian kanan LARIK

· Langkah 3:

Ulangi langkah 1 sampai dengan X ditemukan, atau low > high (menentukan ukuran larik sudah 0).

Ilustrasi Pencarian Bagi Dua.

81	76	21	18	16	13	10	7
1	2	3	4	5	6	7	8
Low							High

1. Misalkan elemen yang dicari adalah X=18.

Langkah 1:

Low = 1 dan High = 8

Elemen tengah Middle = (1+8) div 2 = 9 div 2 = 4

81	76	21	18	16	13	10	7
1	2	3	4	5	6	7	8
Low			Middle				High

Langkah 2:

Larik[4] = X ? (18 = 18) true à X ditemukan, pencarian dihentikan.

2. Misalkan elemen yang dicari adalah X=16.

ITERASI 1

Langkah 1:

Low = 1 dan High = 8

Elemen tengah Middle = (1+8) div 2 = 9 div 2 = 4

81	76	21	18	16	13	10	7
1	2	3	4	5	6	7	8
Low			Middle				High
kiri				kanan

Langkah 2:

Larik[4] = X ? (18 = 16) FALSE, sehingga diputuskan pencarian di kiri atau dikanan.

Jika Larik[4] > 16 ?, (18 > 16) TRUE, lakukan pencarian disebelah kanan dengan Low = middle+1 à 4+1 = 5 dan High = 8, Tetap.

16	13	10	7
5	6	7	8
low			High

ITERASI 2

Langkah 1:

Low = 5 dan High=8

Elemen tengah Middle = (5+8) div 2 = 13 div 2 = 6

16	13	10	7
5	6	7	8
low	middle		High

Langkah 2:

Larik[6] = X ? (13 = 16) FALSE, sehingga diputuskan pencarian di kiri atau dikanan.

Jika Larik[6] > 16 ?, (13 > 16) FALSE, lakukan pencarian disebelah KIRI dengan Low = 5 (TETAP) dan High = middle-1 = 5

Low/high

ITERASI 3

Langkah 1:

Low = 5 dan High=5

Elemen tengah Middle = (5+5) div 2 = 10 div 2 = 5

middle

Langkah 2:

Larik[5] = X ? (16 = 16) TRUE (X ditemukan , pencarian dihentikan)

3. Misalkan elemen yang dicari X=100.

Gambarkan langkah-langkah penyelesaiannya?

Dari ilustrasi diatas dapat dibuat algoritma sebagai berikut:

(dengan data urut menurun/ descending)

1. Masukan Bil yang dicari X

2. tentukan low=1 dan high = N

3. Tentukan nilai tengah : middle = (low + high) div 2

4. Cek, jika LARIK[middle] = X maka Nilai X yang dicari ditemukan, kelangkah 8

5. jika LARIK[middle] > X maka low=middle+1, kelangkah 7

6. jika LARIK[middle] < X maka high=middle-1, kelangkah 7

7. Jika low > high, “bil X tidak ditemukan” dan kelangkah 8, jika tidak kelangkah 3.

8. selesai.

Tugas :

1. buatlah algoritma binary search untuk data yang urut menaik / ascending. Dari algoritma diatas

2. buatlah flowchartnya.

ALGORITMA bentuk lain (ada pada slide) à untuk data urut menaik/ascending

1. Low = 1 , High = N

2. Ketika Low <= High Maka kerjakan langkah No .3,

Jika tidak Maka kerjakan langkah No.7

3. Tentukan index tengah dengan rumus

Middle= ( Low + High ) Div 2

4. Jika X < LARIK[middle] /Nil. Tengah Maka High = Mid –1

5. Jika X > LARIK[middle] /Nil. Tengah Maka Low = Mid +1

6. Jika X = LARIK[middle] /Nil. Tengah Maka Nil. Tengah = Nil. Yg dicari

7. Jika X > High Maka Pencarian GAGAL

2. Tehnik Pencarian Nilai MAXMIN :

ð Tehnik StaritMAXMIN

ð Tehnik D and C

Teknik yangt digunakan untuk mencari nilai maksimum dan minimum dari sekumpulan nilai.

Tehnik Pencarian MAXMIN

Searching dengan Tehnik STRAITMAXMIN

Waktu tempuh yang digunakan untuk menyelesaikan pencarian hinggan mendapatkan solusi yang optimal terbagi atas :

a. Best Case

b. Average Case

c. worst Case

Algoritma dari Proses Pencarian adalah (ada pada slide):

1. Masukan N, tentukan i=1.

2. Tentukan max dan min = A[i]

3. i = 2

4. Jika i<= N maka kelangkah 5, jika tidak kelangkah 8

5. jika A[i] > max maka max=A[i] dan kelangkah 7

6. jika tidak maka (jika A[i] < min maka min = A[i].

7. i = i+1, ulangi langkah 4.

8. cetak max dan min

program straitmaxmin;

var

i,N:integer;

max,min : integer;

A : array[1..10] of integer;

begin

write('masukan N = '); readln(N);

for i:=1 to N do

readln(A[i]);

max := A[1]; min := A[1];

for i:=2 to N do

if A[i] > max then max:=A[i]

else if A[i] < min then min := A[i];

writeln;

writeln('nilai max min= ',max:3, min:3);

end.

masukan N = 5

nilai max min = 6 1

-----------------

masukan N = 6

nilai max min = 9 2

Searching dengan teknik D and C.

Penjelasan ada pada slide.

METODE GREEDY

ð Metode Greedy digunakan untuk memecahkan persoalan optimasi.

ð Persoalan optimasi à adalah persoalan mencari solusi optimum

ð Persoalan optimasi ada 2 àMaksimasi

à Minimasi

Contoh Masalah Optimasi:

Penukaran Uang

Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada.

Berapakah jumlah minimum koin yang diperlukan untuk penukaran uang tersebut.

Persoalan Minimasi.

Contoh 1: tersedia banyak koin 1, 5, 10, 25

32 = 1 + 1 + … + 1 (32 koin)

32 = 5 + 5 + 5 + 5 + 10 + 1 + 1 (7 koin)

32 = 10 + 10 + 10 + 1 + 1 (5 koin)

Minimum: 32 = 25 + 5 + 1 + 1 (4 koin)

Greedy = rakus, tamak

ð Algoritma greedy membentuk solusi langkah per langkah (step by step).

ð Pada setiap langkah terdapat banyak pilihan yang perlu dieksplorasi.

ð Sehingga, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.

(keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya).

ð Pada setiap langkah à membuat pilihan optimum lokal

Dengan harapan bahwa langkah sisanya mengarah kesolusi optimum global.

Metode Greedy digunakan dalam menyelesaikan masalah

ð Optimal Storage on Tapes Problem

ð Knapsack Problem

ð Minimum Spanning Tree Problem

ð Shortest Path Problem

Penjelasan Storage on Tape Problen ada pada SLIDE.
Knapsack Problem

Knapsack dapat diartikan sebagai karung, kantung, atau buntilan.

Karung digunakan untuk memuat sesuatu.

Dan tentunya tidak semua objek dapat ditampung di dalam karung. Karung tersebut hanya dapat menyimpan beberapa objek dengan total ukurannya (weight) lebih kecil atau sama dengan ukuran kapasitas karung.

Setiap objek itupun tidak harus kita masukkan seluruhnya. Tetapi bisa juga sebagian saja.

knapsack 0/1, yaitu suatu objek diambil seluruh bagiannya atau tidak sama sekali.

Setiap objek mempunyai nilai keuntungan atau yang disebut dengan profit.

Tujuan ingin mendapatkan profit yang maksimal. Untuk mendapatkan profit maksimal Belum tentu menggunakan banyak objek yang masuk akan menguntungkan. Bisa saja hal yang sebaliknya yang terjadi.

o Cara terbaik agar menguntungkan : bukan hanya dari hasilnya optimal tetapi juga banyaknya langkah yang dibutuhkan

Knapsack 0/1

Diberikan n buah objek dan sebuah knapsack dengan kapasitas bobot W.

Setiap objek memiliki properti bobot (weigth) wi dan keuntungan(profit) pi.

persoalan adalah memilih memilih objek-objek yang dimasukkan ke dalam knapsack sedemikian sehingga memaksimumkan keuntungan. Total bobot objek yang dimasukkan ke dalam knapsack tidak boleh melebihi kapasitas knapsack.

Solusi persoalan dinyatakan sebagai vektor n-tupel:

X = {x1, x2, … , xn}

xi = 1 jika objek ke-i dimasukkan ke dalam knapsack,

xi = 0 jika objek ke-i tidak dimasukkan.

Persoalan 0/1 Knapsack dapat kita pandang :

sebagai mencari himpunan bagian (subset) dari keseluruhan objek yang muat ke dalam knapsack dan memberikan total keuntungan terbesar.

Penyelesaian dengan Greedy:

1. Greedy by Profit

Pada setiap langkah Knapsack diisi dengan obyek yang mempunyai keuntungan terbesar.

Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang paling menguntungkan terlebih dahulu.

Pertama kali dilakukan adalah menurutkan secara menurun obyek-obyek berdasarkan profitnya . Kemudian obyek-obyek yang dapat ditampung oleh knapsack diambil satu persatu sampai knapsack penuh atau (sudah tidak ada obyek lagi yang bisa dimasukan).

Data awal :

w1 = 6; p1 = 12

w2 = 5; p2 = 15

w3 = 10; p3 = 50

w4 = 5; p4 = 10

Kapasitas knapsack W = 16

2. Greedy by Wight

Pada setiap langkah, knapsack diisi dengan objek yang mempunyai berat paling ringan. Strategi ini mencoba memaksimumkan keuntungan dengan memasukan sebanyak mungkin objek kedalam knapsack.

Pertama kali yang dilakukan adalah mengurutkan secara menaik objek-objek berdasarkan weight-nya. Kemudian obyek-obyek yang dapat ditampung oleh knapsack diambil satu persatu sampai knapsack penuh atau (sudah tidak ada obyek lagi yang bisa dimasukan).

3. Greedy By Density

Pada setiap langkah, knapsack diisi dengan obyek yang mempunyai densitas terbesar (perbandingan nilai dan berat terbesar).

Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang mempunyai keuntungan per unit berat terbesar.

Pertama kali yang dilakukan adalah mencari nilai profit per unit/ density dari tiap-tiap objek. Kemudian obyek-obyek diurutkan berdasarkan densitasnya.

Kemudian obyek-obyek yang dapat ditampung oleh knapsack diambil satu persatu sampai knapsack penuh atau (sudah tidak ada obyek lagi yang bisa dimasukan).

Perbandingan hasil:

Penggunaan 3 strategi diatas tidak menjamin akan memberikan solusi optimal.

CONTOH 2:

Kapasitas M=20, dengan jumlah barang =3

Berat Wi masing-masing barang (W1,W2,W3) à (18,15,,10)

Nilai Profit masing-masing barang (P1,P2,P3) à (25,24,15)

Pilih Barang dengan nilai profit maksimal

P1=25 à x1=1. batas atas nilai

P2=24 à x2=2/15.

P3=15 à x3 =0. batas bawah nilai.

Pilih barang dengan berat minimal

W1 = 18 à x1=0. batas bawah

W2=15 à x2 = 2/3

W3=10 à x3=1. batas atas.

Pilih barang dengan menghitung perbandingan yang terbesar dari profit dibagi Berat (Pi/Wi) diurut secara tidak naik.

P1/w1=25/18 (1.38) à x1=0. karena terkecil x1=0

P2/w2=24/ 15 (1.6)à x2=1. karena terbesar x2=1

P3/w3=15/10 (1.5)à x3=1/2 dicari dengan fungsi pembatas x3=1/2.

Buat Tabel

Solusi	(x1,x2,x3)	Σwixi	Σpixi
Pi max	1,2/15,0	20	28.2
Wi min	0,2/3,1	20	31.0
Pi/Wi max	0,1,1/2	20	31.5

Nilai profit maksimal = 31.5.

PERTEMUAN 13

PENYELESAIAN DENGAN ALGORITMA PEMROGRAMAN GREEDY

PROSEDUR DALAM SLIDE

PROCEDURE GREEDY KNAPSACK (P, W, x, n)

REAL P(1 : n), W(1 : n),x(1 : n),M,isi;

INTEGER i, n;

x(1 : n) ß 0 ; isi ß M ;

FOR i ß 1 TO n DO

IF W(i) > Isi THEN EXIT ENDIF

x(i) ß 1

isi ß isi - W(i)

REPEAT

IF i £ n THEN x(i) ß isi/W(i) ENDIF

END_GREEDY KNAPSACK

Penjelasan program ada pada slide.

Model Graph Dalam metode Greedy

Graph

teori graph terdiri dari titik-titik.

Bila dirangkaikan, titik-titk tersebut mebentuk suatu object yang kita kenal sebagai grafis.

Graph :

ð Terdiri dari node dan

ð Terdiri dari link

ð node disebut vertex

ð link disebut edge

ð informasi penting dlm graph adalah koneksi antar vertex

Graph Berbobot

ð Contoh salah satu representasi visual dari graf adalah peta.

ð representasi dari peta antara lain:

menentukan jalur terpendek dari satu tempat ke tempat lain
menggambarkan 2 kota yang bertetangga dengan warna yang berbeda pada peta
menentukan tata letak jalur transportasi

ð Salah satu konsep graph yang banyak digunakan adalah konsep pohon.

Pohon adalah graf tak-berarah dan tidak berbentuk sirkuit

T = ( V,E ) +

Keterangan :

T : Tree

V : Vertices atau node atau vertex atau simpul, V

merupakan himpunan tidak kosong.

V = {v1,v2,…,vn}

E : Edges atau sisi yang menghubungkan simpul

E = {e1,e2,…,en}

Minimum Spanning Tree

Contoh kasus pada pemeliharaan jalan raya. Dengan Spanning Tree, pemerintah dapat mengalokasikan dana secara optimal dengan mencari jalur pemeliharaan dengan bobot biaya yang minimum.

MST

àlintasan pada graf berbobot dengan jumlah bobot yang paling kecil.

àdigunakan untuk memilih jalur dengan bobot terkrcil yang akan meminimalkan cost.

Algoritma Prim untuk membentuk pohon merentang dari Graph :

1. Ambil sisi dari graf G yang berbobot merentang. ,masukkan kedalam T.

2. Pilih sisi (u,v) yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi (u,v) tidak membentuk sirkuit di T. Tambahkan(u,v)ke dalamT

3. Ulangi langkah 2 sebanyak n 2 kali.

Proses pembentukan pohon merentang (spanning tree).

Pada setiap langkah dipilih sisi graf G yang mempunyai bobot minimum dan terhubung dengan MST yang telah terbentuk

Kriteria2 dr spanning tree, yakni :

1. Setiap ruas pada graph harus terhubung (conected)

2. Setiap ruas pd graph hrs mpy nilai (label graph)

3. Setiap ruas pd graph tdk mpy arah (graph tdk berarah)

Proses.Total minimum cost terbentuknya graph dgn tahapan sbb:

• Dari graph yg tetbentuk, apakah memenuhi kriteria MST.

• Lakukan secara urut dr simpul ruas awal s/d ruas akhir

• Pada setiap simpul ruas perhatikan nilai/cost dr tiap-tiap ruas

• Ambil nilai yg paling kecil (jarak tertpendek setiap ruas).

• Lanjutkan s/d semua simpul ruas tergambar pd spanning tree

• Jumlahkan nilai/cost yg dipilih tadi.

Contoh :

SHORTEST PATH PROBLEM

• Permasalahan= menghitung jalur terpendek dari sebuah graph berarah.

• bagaimana mencari sebuah jalur pada graf yang meminimalkan jumlah bobot sisi pembentuk jalur tersebut.

Ada beberapa macam persoalan lintasan terpendek,

antara lain:

a. Lintasan terpendek antara dua buah simpul tertentu (a pair shortets path).

b. Lintasan terpendek antara semua pasangan simpul (all pairs shortest path).

c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain (single-source shoertes path).

d. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path).

Kriteria utk permasalahan jalur terpendek/SP problem tsb :

Setiap ruas pd graph hrs mpy nilai (label graph)
Setiap ruas pd graph tdk hrs terhubung (unconnected)
Setiap ruas pd graph tsb hrs mempunyai arah (graph berarah).

......................................................................................................................................................................

5. Metode QUICK SORT