Tugas Ke-2 Disusun untuk memenuhi tugas Desain dan Analisis Algoritma
Disusun Oleh: Kelompok 5 K5_L_T2 1. Ibrahim Kusuma
115090600111012
2. M Choirul Rahmadan
115090600111026
3. Abu Bakar
115090601111016
4. Wisnu Wijaya
115090607111018
5. Hammurabi Wisadono
115090607111030
6. Yusuf Aji Wibowo
115090613111004
Program Studi Informatika / Ilmu Komputer Program Teknologi Informasi dan Ilmu Komputer Universitas Brawijaya 2013
A. Algoritma Knapsack Problem a. Definisi Algoritma Knapsack Knapsack artinya karung/kantung. Karung mempunyai kapasitas muat terbatas. Barangbarang dimasukkan ke dalam karung hanya sampai batas kapasitas maksimum karung saja. Knapsack adalah salah satu masalah yang sering muncul dalam kasus optimasi dan kombinatorial yang banyak ditemukan pada literatur-literatur lama dan hingga kini permasalahan ini masih banyak ditemukan dalam kehidupan sehari-hari. Dalam dunia nyata permasalahan Knapsack ini sering sekali digunakan terutama pada bidang (jasa) pengangkutan barang (seperti pengangkutan peti kemas dalam sebuah kapal). Dalam usaha tersebut, diinginkan suatu keuntungan yang maksimal untuk mengangkut barang yang ada dengan tidak melebihi batas kapasitas yang ada. Berdasarkan persoalan tersebut, diharapkan ada suatu solusi yang secara otomatis dalam mengatasi persoalan itu. Problem Knapsack adalah permasalahan optimasi kombinatorial, dimana kita harus mencari solusi terbaik dari banyak kemungkinan yang dihasilkan. Knapsack Problem: Diberikan bobot knapsack adalah M. Diketahui n buah objek yang masing-masing bobotnya adalah w1, w2, …, wn. Tentukan nilai bi sedemikian sehingga M = b1w1 + b2w2 + … + bnwn yang dalam hal ini, bi bernilai 0 atau 1. Jika bi = 1, berarti objek i dimasukkan ke dalam knapsack, sebaliknya jika bi = 0, objek i tidak dimasukkan. b. Contoh Program import java.util.Scanner;
/** * ***********************************************************************
* Compilation: javac Knapsack.java Execution: java Knapsack N W * * Generates an instance of the 0/1 knapsack problem with N items and maximum * weight W and solves it in time and space proportional to N * W using dynamic * programming. * * For testing, the inputs are generated at random with weights between 0 and W, * and profits between 0 and 1000. * * % java Knapsack 6 2000 item profit weight take 1 874 580 true 2 620 1616 * false 3 345 1906 false 4 369 1942 false 5 360 50 true 6 470 294 true * ************************************************************************ */ public class Knapsack {
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); //
int N = Integer.parseInt(args[0]);
// number of items
//
int W = Integer.parseInt(args[1]);
// maximum weight of
knapsack System.out.println("Algoritma Knapsack Problem"); System.out.print("Masukan jumlah item : ");
int N = scanner.nextInt(); System.out.print("Masukkan berat maksimum : "); int W = scanner.nextInt(); int[] profit = new int[N + 1]; int[] weight = new int[N + 1];
// generate random instance, items 1..N for (int n = 1; n <= N; n++) { profit[n] = (int) (Math.random() * 100); weight[n] = (int) (Math.random() * W); }
// opt[n][w] = max profit of packing items 1..n with weight limit w // sol[n][w] = does opt solution to pack items 1..n with weight limit w include item n? int[][] opt = new int[N + 1][W + 1]; boolean[][] sol = new boolean[N + 1][W + 1];
for (int n = 1; n <= N; n++) { for (int w = 1; w <= W; w++) {
// don't take item n int option1 = opt[n - 1][w];
// take item n int option2 = Integer.MIN_VALUE; if (weight[n] <= w) { option2 = profit[n] + opt[n - 1][w - weight[n]]; }
// select better of two options opt[n][w] = Math.max(option1, option2); sol[n][w] = (option2 > option1); } }
// determine which items to take boolean[] take = new boolean[N + 1]; for (int n = N, w = W; n > 0; n--) { if (sol[n][w]) { take[n] = true; w = w - weight[n]; } else { take[n] = false; } }
// print results System.out.println("\nHasil dari set random :"); System.out.println("item" + "\t" + "profit" + "\t" + "berat" +
"\t" + "ambil"); for (int n = 1; n <= N; n++) { System.out.println(n + "\t" + profit[n] + "\t" + weight[n] + "\t" + take[n]); } int totalProfit = 0, totalBerat = 0; System.out.print("\nJadi item yang diambil adalah item "); for (int n = 1; n < N; n++) { if (take[n]) { System.out.print(" "+n); totalProfit+=profit[n]; totalBerat+=weight[n]; } } System.out.println("\nDengan total profit "+totalProfit+" dan total berat "+totalBerat); } }
Screenshoot
B. Algoritma Kompresi Data Menggunakan Huffman Code a. Definisi Algoritma Huffman Algoritma Huffman, yang dibuat oleh seorang mahasiswa MIT bernama David Huffman pada tahun 1952, merupakan salah satu metode paling lama dan paling terkenal dalam kompresi teks [2]. Algoritma Huffman menggunakan prinsip pengkodean yang mirip dengan kode Morse, yaitu tiap karakter (simbol) dikodekan hanya dengan rangkaian beberapa bit, dimana karakter yang sering muncul dikodekan dengan rangkaian bit yang pendek dan karakter yang jarang muncul dikodekan.dengan rangkaian bit yang lebih panjang. Berdasarkan tipe peta kode yang digunakan untuk mengubah pesan awal (isi data yang diinputkan) menjadi sekumpulan codeword, algoritma Huffman termasuk kedalam kelas algoritma yang menggunakan metode statik . Metoda statik adalah metoda yang selalu menggunakan peta kode yang sama, metoda ini membutuhkan dua fase (two-pass): fase pertama untuk menghitung probabilitas kemunculan tiap simbol dan menentukan peta kodenya, dan fase kedua untuk mengubah pesan menjadi kumpulan kode yang akan di taransmisikan.
Sedangkan berdasarkan teknik pengkodean simbol yang digunakan, algoritma Huffman menggunakan metode symbolwise. Metoda symbolwise adalah metode yang menghitung peluang kemunculan dari setiap simbol dalam satu waktu, dimana simbol yang lebih sering muncul diberi kode lebih pendek dibandingkan simbol yang jarang muncul. b. Pembentukan Pohon Huffman Kode Huffman pada dasarnya merupakan kode prefiks (prefix code). Kode prefiks adalah himpunan yang berisi sekumpulan kode biner, dimana pada kode prefik ini tidak ada kode biner yang menjadi awal bagi kode biner yang lain. Kode prefiks biasanya direpresentasikan sebagai pohon biner yang diberikan nilai atau label. Untuk cabang kiri pada pohon biner diberi label 0, sedangkan pada cabang kanan pada pohon biner diberi label 1. Rangkaian bit yang terbentuk pada setiap lintasan dari akar ke daun merupakan kode prefiks untuk karakter yang berpadanan. Pohon biner ini biasa disebut pohon Huffman. Langkah-langkah pembentukan pohon Huffman adalah sebagai berikut [3] : 1. Baca semua karakter di dalam teks untuk menghitung frekuensi kemunculan setiap karakter. Setiap karakter penyusun teks dinyatakan sebagai pohon bersimpul tunggal. Setiap simpul di-assign dengan frekuensi kemunculan karakter tersebut. 2. Terapkan strategi algoritma greedy sebagai berikut : gabungkan dua buah pohon yang mempunyai frekuensi terkecil pada sebuah akar. Setelah digabungkan akar tersebut akan mempunyai frekuensi yang merupakan jumlah dari frekuensi dua buah pohon-pohon penyusunnya. 3. Ulangi langkah 2 sampai hanya tersisa satu buah pohon Huffman. Agar pemilihan dua pohon yang akan digabungkan berlangsung cepat, maka semua yang ada selalu terurut menaik berdasarkan frekuensi. Sebagai contoh, dalam kode ASCII string 7 huruf “ABACCDA” membutuhkan representasi 7 × 8 bit = 56 bit (7 byte), dengan rincian sebagai berikut: A = 01000001 B = 01000010
A = 01000001 C = 01000011 C = 01000011 D = 01000100 A = 01000001 Pada string di atas, frekuensi kemunculan A = 3, B = 1, C = 2, dan D = 1,
Gambar 1. Pohon H uffman untuk Karakter “ABACCDA”
c. Proses Encoding Encoding adalah cara menyusun string biner dari teks yang ada. Proses encoding untuk satu karakter dimulai dengan membuat pohon Huffman terlebih dahulu. Setelah itu, kode untuk satu karakter dibuat dengan menyusun nama string biner yang dibaca dari akar sampai ke daun pohon Huffman.
Langkah-langkah untuk men-encoding suatu string biner adalah sebagai berikut 1. Tentukan karakter yang akan di-encoding 2. Mulai dari akar, baca setiap bit yang ada pada cabang yang bersesuaian sampai ketemu sdaun dimana karakter itu berada 3. Ulangi langkah 2 sampai seluruh karakter diencoding Sebagai contoh kita dapat melihat tabel dibawah ini, yang merupakan hasil encoding untuk pohon Huffman pada gambar 1 Karakter String Biner Huffman A
0
B
110
C
10
D
111
Tabel 1. Kode Huffman untuk Karakter “ABCD”
d. Proses Decoding Decoding merupakan kebalikan dari encoding. Decoding berarti menyusun kembali data dari string biner menjadi sebuah karakter kembali. Decoding dapat dilakukan dengan dua cara, yang pertama dengan menggunakan pohon Huffman dan yang kedua dengan menggunakan tabel kode Huffman. Langkah-langkah men -decoding suatu string biner dengan menggunakan pohon Huffman adalah sebagai berikut : 1. Baca sebuah bit dari string biner. 2. Mulai dari akar 3. Untuk setiap bit pada langkah 1, lakukan traversal pada cabang yang bersesuaian. 4. Ulangi langkah 1, 2 dan 3 sampai bertemu daun. Kodekan rangkaian bit yang telah dibaca dengan karakter di daun. 5. Ulangi dari langkah 1 sampai semua bit di dalam string habis. Sebagai contoh kita akan men-decoding string biner yang bernilai ”111”
Gambar 2. Proses Decoding dengan Menggunakan Pohon Huffman
setelah kita telusuri dari akar, maka kita akan menemukan bahwa string yang mempunyai kode Huffman “111” adalah karakter D. Cara yang kedua adalah dengan menggunakan tabel kode Huffman. Sebagai contoh kita akan menggunakan kode Huffman pada Tabel 1 untuk merepresentasikan string “ABACCDA”. Dengan menggunakan Tabel 1 string tersebut akan direpresentasikan menjadi rangkaian bit : 0 110 0 10 10 1110. Jadi, jumlah bit yang dibutuhkan hanya 13 bit. Dari Tabel 1 tampak bahwa kode untuk sebuah simbol/karakter tidak boleh menjadi awalan dari kode simbol yang lain guna menghindari keraguan (ambiguitas) dalam proses dekompresi atau decoding. Karena tiap kode Huffman yang dihasilkan unik, maka proses decoding dapat dilakukan dengan mudah. Contoh: saat membaca kode bit pertama dalam rangkaian bit “011001010110”, yaitu bit “0”, dapat langsung disimpulkan bahwa kode bit “0” merupakan pemetaan dari simbol “A”. Kemudian baca kode bit selanjutnya, yaitu bit “1”. Tidak ada kode Huffman “1”, lalu baca kode bit selanjutnya, sehingga menjadi “11”. Tidak ada juga kode Huffman “11”, lalu baca lagi kode bit berikutnya, sehingga menjadi “110”. Rangkaian kode bit “110” adalah pemetaan dari simbol “B”.
e. Kompleksitas Algoritma Huffman Algoritma Huffman mempunyai kompleksitas waktu O(n log n), karena dalam melakukan sekali proses itersi pada saat penggabungan dua buah pohon yang mempunyai frekuensi terkecil pada sebuah akar membutuhkan waktu O(log n), dan proses itu dilakukan berkalikali sampai hanya tersisa satu buah pohon Huffman itu berarti dilakukan sebanyak n kali[4].
f. Contoh Program /* * Huffman Algorithm for the DEI's Programming Contest, 2004 * (c) Paulo Marques, 2004. *
[email protected] * * Note: this program only process text characters: *
('a'-'z' / 'A'-'Z'). Everything else is ignored.
*/
import java.util.*;
class Node implements Comparable { private int
value;
private char
content;
private Node
left;
private Node
right;
public Node(char content, int value) {
}
this.content
= content;
this.value
= value;
public Node(Node left, Node right) { // Assumes that the left three is always the one that is lowest this.content
=
(left.content
<
right.content)
left.content : right.content; this.value this.left this.right
= left.value + right.value; = left; = right;
}
@Override public int compareTo(Object arg) { Node other = (Node) arg;
// Content value has priority and then the lowest letter if (this.value == other.value) return this.content-other.content; else return this.value-other.value; }
////////////////
?
private void printNode(String path) { if ((left==null) && (right==null)) System.out.println(content + " " + path);
if (left != null) left.printNode(path + '0'); if (right != null) right.printNode(path + '1'); }
public static void printTree(Node tree) { tree.printNode(""); } }
public class Huffman { public static void main(String[] args) { Scanner scanner = new Scanner(System.in);
System.out.println("Algoritma Huffman Code\n");
Kompresi
Data
Menggunakan
System.out.print("Masukkan teks asal : "); String teks = scanner.nextLine(); System.out.println("\nHasil : "); processFile(teks); }
private static void processFile(String fileContents) { int[] frequency = new int['Z'-'A'+1];
//
Frequency table of each letter TreeSet
trees
= new TreeSet();
// List
containing all trees -- ORDERED!
// Build the frequency table of each letter for (int i=0; i
ch
Character.toUpperCase(fileContents.charAt(i)); if ((ch >= 'A') && (ch <= 'Z')) ++frequency[ch - 'A']; }
// Build up the initial trees for (int i=0; i<'Z'-'A'+1; i++) { if (frequency[i] > 0)
=
{ Node
n
=
new
Node((char)('A'+i),
frequency[i]); trees.add(n); } }
// Huffman algoritm while (trees.size() > 1) { Node tree1 = (Node) trees.first(); trees.remove(tree1); Node tree2 = (Node) trees.first(); trees.remove(tree2);
Node merged = new Node(tree1, tree2); trees.add(merged); }
// Print the resulting tree if (trees.size() > 0) { Node theTree = (Node) trees.first(); Node.printTree(theTree); } else
System.out.println("The file didn't contain useful characters."); } }
Screenshoot
C. Algoritma Minimum Spanning Tree a. Definisi Algoritma Minimum Spanning Tree Definisi dari Spanning tree Untuk suatu jaringan dengan n node, spanning tree adalah sekumpulan dari n-1 arc yang menghubungkan semua node dalam jaringan dan tidak mengandung loop sedangkan definisi dari Minimum Spanning Tree sendiri adalah spanning tree dengan panjang minimum dalam suatu jaringan. Pohon Merentang Minimum (Minimum Spanning Tree) Jika G pada gambar 2.10 merupakan graf berbobot, maka bobot pohon merentang T1 atau T2 didefinisikan sebagai jumlah bobot semua sisi di T1 atau T2. Diantara pohon merentang yang ada pada G, yang paling penting adalah pohon merentang dengan jumlah bobot sisi e minimum. Pohon
merentang dengan jumlah bobot sisi e minimum ini disebut dengan pohon merentang minimum atau Minimum Spanning Tree (MST). Contoh aplikasi MST yang digunakan dalam penulisan skripsi ini adalah masalah pemasangan jaringan kabel listrik menggunakan graf. MST digunakan untuk memilih jalur dengan jumlah bobot terkecil yang akan meminimalkan biaya pemasangan kabel listrik
Gambar 2.10. G adalah Graf Berbobot, T1 dan T2 adalah Pohon Merentang Berbobot dari Graf G.
Dari graf berbobot G, kita harus menentukan pohon merentang mana yang paling minimum. Apakah T1 atau T2, hal tersebut yang akan dicari dengan membangun pohon merentang yang mempunyai jumlah jalur terpendek, dengan kata lain harus dicari pohon merentang minimum. Cara yang paling sederhana adalah dengan mendaftarkan semua pohon merentang berbobot yang mungkin dibuat (dalam hal ini T1 dan T2) dan menghitung total bobot tiap-tiap pohon merentang. Selanjutnya dipilih pohon merentang dengan total bobot sisi e yang paling kecil. Metode ini tidak efisien, terutama pada graf cukup besar karena terdapat banyak sekali pohon merentang yang dapat dibuat. Algoritma Prim Pada tahun 1956 seorang computer scientist Robert C Prim berhasil menyusun algoritma untuk membuat pohon merentang minimum secara efisien. Algoritma Prim membentuk MST langkah per langkah. Pada setiap langkah dipilih sisi e dari graf G yang mempunyai bobot minimum dan bersisian dengan simpul-simpul di dalam T tetapi e tidak membentuk sirkuit didalam T. Ada 3 (tiga) langkah yang dilakukan pada algoritma Prim, yaitu : 1. Pilih sisi graf G yang berbobot paling minimum dan masukkan ke dalam T 2. Pilih sisi e yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi e
tidak membentuk sirkuit di T, lalu masukkan e ke dalam T. 3. Ulangi langkah ke-dua sebanyak n-2 kali. Jumlah langkah seluruhnya didalam algoritma Prim adalah 1 + ( n – 2 ) = n - 1 yaitu sebanyak jumlah sisi didalam pohon merentang dengan n buah simpul.
b. Contoh Program import java.io.*; import java.util.Scanner;
class Prim {
public static Scanner sc = new Scanner(System.in); static int[][] G; static int[][] t; static int[] near; static int n; static int mincost = 0; static int k, l;
static void prims() { MinKL(); mincost = G[k][l]; t[1][1] = l; t[1][2] = k; for (int i = 1; i <= n; i++) {
near[i] = (G[i][l] < G[i][k]) ? l : k; } near[k] = near[l] = 0;
for (int i = 2; i < n; i++) { int j = Min(); t[i][1] = j; t[i][2] = near[j]; mincost = mincost + G[j][near[j]]; near[j] = 0; for (int k = 1; k <= n; k++) { if ((near[k] != 0) && G[k][ near[k]] > G[k][j]) { near[k] = j; } } } }
static int Min() { int j = 1; for (int i = 1; i <= n; i++) { if (near[i] != 0) { j = i; break; }
}
for (int i = 1; i <= n; i++) { if (near[i] != 0) { if (G[j][near[j]] > G[i][near[i]]) { j = i; } } } return j; }
static void MinKL() { int k1 = 1, l1 = 2; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if ((i != j) && (i < j)) { if ((G[i][j] < G[k1][l1]) && G[i][j] != 0) { k1 = i; l1 = j; } } } } if (G[k1][l1] != 0) {
k = k1; l = l1; } }
public static void main(String[] args) throws IOException { System.out.println("Algoritma Minimum Spanning Tree Prim");
System.out.print("\nMasukkan jumlah verteks: "); n = Integer.parseInt(sc.nextLine());
G = new int[n + 1][n + 1]; t = new int[n + 1][3];
near = new int[n + 1];
System.out.print("\nMasukkan bobot lintasan :\n"); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if ((i != j) && (i < j)) { System.out.print(i + " and " + j + ": "); G[j][i] = G[i][j] = Integer.parseInt(sc.nextLine()); if (G[i][j] == 0) { G[j][i] = G[i][j] = 7001; }
} if (i == j) { G[i][j] = 7001; } } }
prims(); System.out.println("\nHasil :");
for (int i = 1; i <= n; i++) { if ((t[i][1] != 0) && (t[i][2] != 0)) { System.out.println(t[i][1] + "-" + t[i][2]); } } System.out.println("\nMinimum bobot : " + mincost); } }
Screenshoot
DAFTAR PUSTAKA Rinaldi Munir, 2004, Diktat Kuliah IF5054 Kriptografi, Penerbit ITB http://nurmaghany.blogspot.com/2012/01/knapsack-algoritma.html Diakses pada tanggal 12 April 2013 http://yohandamandala.blogspot.com/2009/11/algortima-huffman-code.html Diakses pada tanggal 12 April 2013 http://pmarques.dei.uc.pt/programs/huffman/Huffman.java.html Diakses pada tanggal 15 April 2013
