laporan praktikum struktur data dan algoritma

LAPORAN PRAKTIKUM

STRUKTUR DATA DAN ALGORITMA

BINARY HEAP

DISUSUN OLEH:

FEMBI REKRISNA GRANDEA PUTRA

M0513019

ASISTEN DOSEN:

1. DIAN SUPRABA (M0512012)

2. DWI PUTRI PERTIWI (M0512015)

3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)

4. RIZAL KUSUMAJATI NUGROHO (M0512050)

JURUSAN INFORMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SEBELAS MARET

SURAKARTA

KAMIS, 25 SEPTEMBER 2014

SOAL

1. Print Screen

2. Penjelasan Program

public class BinaryHeap

Merupakan pembuka sebuah kelas yang digunakan untuk membuat suatu

objek.

{}

Pembuka dan penutup suatu class/method.

private int size;

Pendeklarasian variabel size dengan tipe data integer.

public BinaryHeap()


objek.

public BinaryHeap (Comparable[] array)


objek dengan menambahkan array untuk pemilihan pada menu saat

program dijalankan.

public boolean isEmpty()

Keadaan saat heap kosong.

public boolean isFull()

Keadaan saat heap penuh.

public void buildHeap()

Pembuatan heap baru.

for(int x = size/2; x > 0; x--) {

perculateDown(x); }

Untuk x=size/2,maka x>0 dan nilai x dikurangi satu.

private void perculateDown(int x) {Comparable temp

= heap[x];int child;

Pembuatan anak/cabang pada heap.

for(; 2*x <= size; x = child) {child = 2*x;

Untuk 2*x <=size,maka x =child dan child = 2*x.

public Comparable deleteMin()

Pembuatan fungsi deleteMin pada program.

if(size == 0);Comparable min = heap[1];heap[1] =

heap[size--] perculateDown(1);

Kondisi saat heap sebelum dihapus.

public void insert(Comparable y)

Pembuatan fungsi insert pada program.

private void doubleSize()

Pendeklarasian variabel Size dengan tipe data double.

Comparable[] old = heap;

Membandingkan heap lama dengan heap yang baru.

heap = new Comparable[heap.length*2];

Proses output heap setelah diproses oleh program.

public void heapSort()

Pembuatan fungsi pengurutan/sort pada program.

int arr[] = new int[500];

Pendeklarasian array dengan tipe data integer serta penetapan batas

karakter input sebanyak 500.

int swap, p, q, r;

Pendeklarasian variabel swap,p,q,r dengan tipe data integer.

for( p = 0; p < size; p++)

Untuk p=0,p<size,maka nilai p ditambah 1.

for (q = 0; q < size-1; q++)

Untuk q=0,q<size-1,maka nilai q ditambah 1.

for (r = 0; r < size-q-1; r++)

Untuk r=0,r < size-q-1,maka nilai r ditambah 1.

for(p = 0; p < size; p++) { heap[p+1] = arr[p+1];

}

Untuk p = 0,p<size,maka nilai p ditambah 1.

for(int s = 0; s < size; s++) {

System.out.print(heap[s+1]+ " "); }

Untuk s = 0,s<size,maka nilai s ditambah 1.

public void printHeap()

Pembuatan fungsi pencetakan heap kepada pengguna pada program.

System.out.println("\nHeap : ");

Program akan menampilkan heap yang telah diproses oleh program.

for (int i = 0; i < size; i++)

Untuk I = 0,i<size,maka nilai I ditambah 1.

public static void main(String[] args)

Merupakan pembuka suatu method.Method main ini akan dikompilasi yang

paling pertama. Method di atas berparameter string[] args,dengan args

sebagai nama dari objek array dan string.

Scanner input = new Scanner(System.in);

Program akan melakukan scan terhadap setiap input yang akan dilakukan

oleh pengguna.

System.out.println("\n--Binary Heap--");

Program akan mencetak "--Binary Heap--" ke layar.

BinaryHeap jalan = new BinaryHeap();

Setelah diberi input,maka program otomatis akan menampilkan menu

utama lagi.

System.out.println("\nPilihan Menu Binary Heap");

System.out.println("1. Insert");

System.out.println("2. Delete-

Min");System.out.println("3. Heap

Sort");System.out.println("4. Print

Heap");System.out.println("5. Check Empty");

System.out.println("6. Exit");

System.out.print("Silahkan Pilih Menu = ");

Program akan mencetak pilihan menu binary heap dengan pilihan menu

Insert,Delete-min,Heap Sort,Print Heap,Check Empty,Exit.

case 1:

{System.out.println("\n");System.out.println("--

Insert--");System.out.print("Masukkan Element =

");jalan.insert(input.nextInt());System.out.printl

n("Elemen Berhasil Dimasukkan");break;

Pada menu pertama program akan menampilkan pilihan menu insert,yaitu

menu yang berfungsi untuk memasukkan angka yang akan diurutkan

dengan menggunakan algoritma binary heap.

case 2: {

System.out.println("\n");System.out.println("--

Delete-Min --"); jalan.deleteMin();

System.out.println("Elemen terkecil Berhasil

dihapus"); break;

Pada menu kedua program akan menampilkan pilihan menu Delete-

Min,yang berfungsi untuk menghapus input yang dilakukan pengguna

sebelumnya.

case 3: { System.out.println("\n");

System.out.println("--Heap Sort--");

jalan.heapSort(); System.out.println("\n"); break;

Pada menu ketiga program akan menampilkan pilihan menu Heap Sort

yang berfungsi untuk mengurutkan input yang dimasukkan oleh pengguna

yang sebelumnya telah diproses dengan menggunakan algoritma binary

heap.

case 4: {

System.out.println("\n");System.out.println("--

Heap--"); jalan.printHeap(); break;

Pada menu keempat program akan menampilkan menu Print Heap yang

berfungsi untuk mencetak heap yang telah diproses oleh program dengan

mengunakan algoritma binary heap.

case 5:

{System.out.println("\n");System.out.println("Stat

us Empty = " + jalan.isEmpty());break;

Menu ini digunakan untuk menghapus semua input yang dilakukan oleh

pengguna.

case 6: { System.err.println("Program Telah

Berhenti"); System.exit(0);

Menu ini digunakan untuk keluar dari program.

Program binary heap ini digunakan untuk mengolah input data berupa

angka yang diolah menjadi heap dengan menggunakan algoritma binary heap.

Program ini selain memiliki kemampuan mengolah angka menjadi heap juga dapat

melakukan sorting binary heap.

Mula-mula dibentuk kelas BinaryHeap sebagai awal dari pembuatan

program.Lalu untuk batas karakter inputnya dibuat melalui source code private

static final int CAPACITY = 500;.

Pembuatan heap baru dilakukan oleh program melalui

public BinaryHeap() {

size = 0;

heap = new Comparable [CAPACITY];

}

Untuk membandingkan antara input angka yang satu dengan yang

lain,program ini menggunakan

public BinaryHeap (Comparable[] array) {

size = array.length;

heap = new Comparable[array.length+1];

}

Untuk menyatakan keadaan bahwa heap dalam keadaan kosong maka

program menggunakan

public boolean isEmpty() {

return size == 0;

}

Untuk menyatakan keadaan bahwa heap dalam keadaan penuh maka

program menggunakan

public boolean isFull() {

return size == heap.length;

}

Untuk membangun heap baru maka program menggunakan

public void buildHeap() {

for(int x = size/2; x > 0; x--) {

perculateDown(x);

}

}

Untuk menyatakan fungsi deletemin maka program ini menggunakan

public Comparable deleteMin() {

if(size == 0);

Comparable min = heap[1];

heap[1] = heap[size--];

perculateDown(1);

return min;

}

Untuk melakukan sorting pada heap dilakukan melalui

public void heapSort() {

int arr[] = new int[500];

int swap, p, q, r;

for( p = 0; p < size; p++) {

arr[p+1] = (int) heap[p+1];

}

for (q = 0; q < size-1; q++) {

for (r = 0; r < size-q-1; r++) {

if(arr[r+1] > arr[r+2]) {

swap = arr[r+1];

arr[r+1] = arr[r+2];

arr[r+2] = swap;

}

}

}

for(p = 0; p < size; p++) {

heap[p+1] = arr[p+1];

}

for(int s = 0; s < size; s++) {

System.out.print(heap[s+1]+ " ");

}

}

Untuk mencetak heap yang telah diproses menggunakan

public void printHeap() {

System.out.println("\nHeap : ");

for (int i = 0; i < size; i++)

System.out.println(heap[i+1]+ " ");

System.out.println();

}

Setelah semua source code diproses, maka hasil run program adalah

Mula-mula dilakukan pemilihan menu no.1 (insert). Angka yang

dimasukkan adalah 20, 37, 25, 63, 61, 92, 17, 21, 12, 55, 47, 45, 64, 83, 73. Setelah

di-input-kan semua data-datanya, maka yang harus dilakukan setelahnya adalah

melakukan heap sort. Untuk melakukan heap sort, dilakukan pemilihan menu no.3.

Setelah dilakukan pemilihan menu heap sort, maka program akan menampilkan

Output yang dikeluarkan adalah 12, 17, 20, 21, 25, 37, 45, 47, 55, 61, 63,

64, 73, 83, 92. Setelah menggunakan program, jika ingin keluar dari program,

maka yang harus dilakukan adalah memilih menu no.6 (exit). Setelah dipilih menu

exit, maka program akan berhenti bekerja.

LAPORAN PRAKTIKUM


SPLAY TREE

DISUSUN OLEH:


M0513019

ASISTEN DOSEN:





JURUSAN INFORMATIKA



SURAKARTA

KAMIS, 9 OKTOBER 2014

SOAL

1. Print Screen

2. Analisis

Program ini berguna untuk mengimplementasikan splay tree pada Java.

Program ini terdiri dari beberapa kelas, yaitu SplayNode, SplayTree, dan

Test_SplayTree. Di kelas SplayNode, terdapat konstruktor SplayNode dengan

objek left, right, dan parent dan variabel elemen bertipe integer.

Di kelas SplayTree, terdapat metode-metode yang dirujuk oleh menu pada

program ini. Metode SplayTree mengubah nilai variabel root menjadi null. Metode

isEmpty bertipe boolean, akan menentukan apakah splay tree berisi data atau null.

Metode clear berguna untuk menghapus seluruh data. Metode insert berguna untuk

menyisipkan data. Metode remove bertipe boolean berguna untuk mengecek

ketersediaan data yang akan dihapus. Metode remove bertipe void berguna untuk

menghapus data. Metode countNodes berguna untuk menghitung jumlah node

yang ada. Metode search berguna untuk mencari ketersediaan node di dalam splay

tree dengan mengembalikan kepada metode findNode. Metode findNode berguna

untuk menemukan node di dalam splay tree. Metode inorder berguna untuk

menampilkan urutan node dalam inorder. Metode preorder berguna untuk

menampilkan urutan node dalam preorder. Metode postorder berguna untuk

menampilkan urutan node dalam postorder.

Di dalam kelas Test_SplayTree berisi perintah untuk memindai masukan

dari pengguna dan mencetak tulisan ke layar. Menu 1 untuk memasukkan data dan

memanggil metode insert. Menu 2 untuk menghapus data, dengan memanggil

metode isEmpty terlebih dahulu, jika node masih null, maka menampilkan tulisan

“Tree Kosong”. Jika data sudah terisi, maka pengguna dapat memasukkan data

yang akan dihapus, kemudian program memanggil metode search untuk

mencarinya dan memanggil metode remove untuk menghapusnya. Jika data

berhasil dihapus oleh metode remove, maka muncul pesan bahwa data telah

dihapus. Jika metode search tidak berhasil menemukan data yang akan dihapus,

maka muncul pesan bahwa data tidak ditemukan. Menu 3 berguna untuk mencari

data dengan memanggil metode search. Menu 4 berguna untuk menghitung jumlah

node yang ada dalam splay tree dengan memanggil fungsi countNodes. Menu 5

berguna untuk mengecek status kekosongan pada splay tree dengan memanggil

metode isEmpty. Menu 6 untuk menghapus seluruh data dengan memanggil

metode clear. Menu 7 untuk keluar dari program. Jika salah memilih menu atau

angka yang dipilih di luar angka 1—7, maka akan muncul pesan bahwa masukan

salah dan pengguna boleh mencoba lagi. Di setiap kali selesai memilih menu dan

selesai melakukan perintah, maka program otomatis mencetak urutan node dalam

postorder, preorder, dan inorder dengan memanggil metode postorder, preorder,

dan inorder.

LAPORAN PRAKTIKUM


TRIES

DISUSUN OLEH:


M0513019

ASISTEN DOSEN:





JURUSAN INFORMATIKA



SURAKARTA


SOAL

1. Print Screen

2. Analisis

Program ini berguna untuk memasukkan masukan berupa string dari

pengguna dan menghitung jumlah huruf pada masing-masing kata. Kemudian

pengguna dapat mencari kata apa yang terdapat dalam string tadi, program akan

mencarinya dan menemukannya di indeks tertentu.

Program ini terdiri dari dua kelas, yaitu PrefixTree dan TrieNode. Di kelas

PrefixTree, terdapat metode createTree yang berguna untuk membuat tree dengan

mengembalikan nilai ke TrieNode baru. Metode insertWord berguna untuk

menyisipkan kata. Metode find berguna untuk menemukan kata yang ingin dicari

pengguna di dalam kalimat yang dimasukkan sebelumnya. Metode printTree

berguna untuk mencetak jumlah huruf pada setiap kata yang dimasukkan

pengguna.

Di dalam metode main, terdapat perintah untuk memindai masukan dari

pengguna dan mencetak tulisan ke layar. Pada awalnya, program memanggil

metode createTree untuk membuat tree. Setelah itu, pengguna dapat memasukkan

kalimat ke dalam program. Program akan memanggil metode insertWord dan

menghitung jumlah huruf pada setiap kata yang dimasukkan. Setelah itu, program

meminta masukan dari pengguna terhadap kata apa yang ingin dicari oleh

pengguna dalam kalimat sebelumnya dengan memanggil fungsi searchWord. Jika

kata yang dicari pengguna terdapat dalam kalimat tersebut, maka program akan

menampilkannya dan menghitung di indeks berapa kata tersebut diawali. Jika kata

yang dicari pengguna tidak ditemukan program dalam kalimat tersebut, maka

program akan menampilkan pesan bahwa kata tidak dapat ditemukan.

Huruf Indeks ke-

m 1

a 2

h 3

a 4

s 5

i 6

s 7

w 8

a 9

10

Kelas TrieNode berguna untuk mendeklarasikan

beberapa variabel yang berguna untuk menjalankan

program. Contoh penggunaannya, pengguna memasukkan

string berupa “mahasiswa mipa merdeka”, maka program

akan menghitung jumlah huruf dari setiap kata, yaitu 9

huruf untuk “mahasiswa”, 4 huruf untuk “mipa”, dan 7

huruf untuk “merdeka”. Setelah itu program meminta

pengguna untuk memasukkan kata yang ingin dicari kalimat

tersebut. Jika pengguna ingin mencari kata “mipa”, maka

program akan mencarinya dalam kalimat tadi dan

menemukan bahwa huruf “m” dari kata “mipa” terdapat di

indeks ke-11, dengan catatan bahwa karakter spasi juga

dihitung sebagai indeks tersendiri.

Jika pengguna mencoba lagi memasukkan kalimat yang sama dan mencoba

mencari kata yang tidak ada dalam kalimat tersebut, misalnya kata “siswa”, maka

program akan menampilkan tulisan “The word was NOT found”, walaupun huruf-

huruf tersebut terdapat dalam kata mahasiswa secara berurutan, namun program

tidak membacanya sebagai satu kata yang utuh, sehingga tidak dianggap sebagai

salah satu kata yang terdapat dalam kalimat tersebut.

m 11

i 12

p 13

a 14

15

m 16

e 17

r 18

d 19

e 20

k 21

a 22

LAPORAN PRAKTIKUM


ALGORITMA GREEDY

DISUSUN OLEH:


M0513019

ASISTEN DOSEN:





JURUSAN INFORMATIKA



SURAKARTA


1. Integer Knapsack

a. Print Screen

b. Analisis

Program ini berguna untuk mengimplementasikan algoritma Greedy pada

Java, yaitu memasukkan objek satu persatu. Setelah objek dimasukkan, tidak dapat

dikeluarkan lagi. Pada awalnya, program mendeklarasikan beberapa variabel.

Kemudian program menerima masukan dari pengguna berupa kapasitas

maksimum, jumlah barang, Wi (berat) dari masing-masing barang, dan Pi

(keuntungan) dari masing-masing barang.

Misalnya pengguna memasukkan kapasitas maksimum bernilai 16 dan

jumlah barang bernilai 4. Maka pengguna akan diminta memasukkan berat dan

keuntungan dari masing-masing barang sebanyak 4 kali.

Indeks ke- Wi Pi PWi = Pi / Wi

1 8 4 0.5

2 5 2 0.4

3 4 8 2.0

4 10 2 0.2

Pertama, program akan menentukan Greedy by Profit dengan mengurutkan

keuntungan (Pi) dari yang tertinggi ke yang terendah. Sehingga, program akan

mendapatkan barang indeks ke-3 dan 1 dengan total keuntungannya adalah 12 dan

total bobotnya adalah 12. Indeks ke-2 dan 4 sebagai urutan keuntungan selanjutnya

tidak dapat dimasukkan lagi. Karena jika salah satu dari keduanya dimasukkan,

maka total bobotnya (17) akan melebihi kapasitas maksimum yang ditentukan (16).

Kedua, program akan menentukan Greedy by Weight dengan mengurutkan

berat (Wi) dari yang terkecil ke yang terbesar. Sehingga, program akan

mendapatkan barang indeks ke-3 dan 2 dengan total bobotnya adalah 9 dan total

keuntungannya adalah 10. Indeks ke-1 sebagai urutan bobot selanjutnya tidak

dapat dimasukkan lagi. Karena jika dimasukkan, maka total bobotnya (17) akan

melebihi kapasitas maksimum yang ditentukan (16).

Terakhir, program akan menentukan Greedy by Density dengan

mengurutkan kepadatan dari yang terbesar ke yang terkecil. Sehingga, program

akan mendapatkan barang indeks ke-3 dan 1 dengan total bobotnya adalah 12 dan

total keuntungannya adalah 12. Indeks ke-2 sebagai urutan kepadatan selanjutnya

tidak dapat dimasukkan lagi. Karena jika dimasukkan, maka total bobotnya (17)

akan melebihi kapasitas maksimum yang ditentukan (16).

2. Pemilihan Aktivitas

a. Print Screen

b. Analisis

Program ini digunakan untuk mengimplementasikan algoritma pada Java,

yaitu berkaitan dengan masalah pemilihan aktivitas. Pada kasus ini, kita dapat

memilih aktivitas mana yang dapat dilakukan dengan mengetahui Si (waktu mulai)

dan Fi (waktu berakhirnya) aktivitas tersebut.

Misalnya, pengguna memasukkan total aktivitas sebanyak 3 dengan

masing-masing waktu mulai dan berakhirnya adalah 11 dan 15, 13 dan 21, serta 10

dan 12. Jika pengguna memasukkan nilai Fi yang lebih kecil daripada nilai Si,

maka program akan menampilkan pesan kesalahan dan meminta pengguna untuk

memasukkan kembali nilai yang benar.

Indeks ke- Si Fi

1 11 15

2 13 21

3 10 12

Selanjutnya, program akan mengurutkan aktivitas dari nilai Si yang terkecil

ke yang terbesar.

Indeks ke- Si Fi

1 10 12

2 11 15

3 13 21

Kemudian, program akan menentukan aktivitas mana yang dapat dilakukan

pengguna dengan tidak memilih aktivitas yang waktunya bertabrakan, sehingga

program memilih aktivitas dengan indeks ke-1 dan 3 dengan jumlah aktivitas 2.

3. Penukaran Uang

a. Print Screen

b. Analisis

Program ini digunakan untuk mengimplementasikan algoritma Greedy pada

Java, yaitu berkaitan dengan masalah penukaran uang, dengan memilih koin

dengan nilai terbesar dari himpunan koin yang tersisa.

Misalnya, pengguna akan memiliki 5 jenis koin dengan nominal yang

berbeda-beda (50, 100, 200, 500, dan 1000). Maka, program akan mengurutkan

nilai koin-koin tersebut dari yang terbesar ke yang terkecil. Setelah itu,

pengguna ingin mendapatkan uang sejumlah 4950 dari koin-koin tersebut,

kemudian program akan menjumlahkan koin-koin tersebut dengan fungsi

while. Sehingga jika nilai uang melebihi nilai total, maka perintah tersebut

akan berhenti dijalankan. Selanjutnya, program akan menampilkan urutan koin

yang dipakai untuk mendapatkan sejumlah uang tersebut dan menampilkan

jumlah minimal koin yang dibutuhkan.

4. Penjadwalan

a. Print Screen

b. Analisis


Java, yaitu berkaitan dengan masalah penjadwalan. Pada kasus ini, program

menggunakan konsep algoritma Greedy untuk meminimalisasi waktu dalam

sistem penjadwalan. Pengguna akan memilih pelanggan yang membutuhkan

waktu pelayanan terkecil di antara pelanggan lain yang belum dilayani.

Program ini akan mengeksekusi kelas Penjadwalan dan memanggil metode

utama yang bernama main. Selanjutnya, program akan mendeklarasikan

variabel-variabel yang digunakan dalam program ini. Selanjutnya, pengguna

memasukkan banyak proses, yaitu 3 yang masuk ke variabel n. Lalu, pengguna

memasukkan nilai variabel t dengan operasi perulangan.

Selanjutnya akan dilakukan proses pengurutan variabel t dari nilai terkecil

ke nilai terbesar dari nilai t. Selanjutnya akan dilakukan proses menentukan

penjadwalan. Dengan menginisialisasikan nilai jml = 0 dan tot = 0, maka

program melakukan proses perulangan. Setelah kondisi tidak memenuhi, maka

proses looping berhenti, dan program akan menampilkan nilai kemungkinan

total aktivitas minimum atau nilai akhir dari variabel tot yaitu 29.

5. Fractional Knapsack

a. Print Screen

b. Analisis


Java yang berkaitan dengan masalah fractional knapsack. Program

menggunakan konsep algoritma Greedy dengan memasukkan objek satu

persatu ke dalam knapsack. Setelah objek dimasukkan, objek tersebut tidak

bisa dikeluarkan lagi.

Program ini akan mengeksekusi kelas Fractional_knapsack dan memanggil

metode utama yang bernama main. Selanjutnya akan melakukan pembuatan

objek baru bernama fk di dalam kelas Fractional_knapsack. Kemudian

memanggil metode fill melalui objek fk.

Selanjutnya pengguna memasukkan jumlah barang, yaitu 3 yang masuk ke

variabel nItems. Lalu pengguna memasukkan berat dan keuntungan dari

masing-masing barang. Selanjutnya pengguna memasukkan kapasitas

maksimum, yaitu 20 yang masuk ke variabel W. Lalu program melakukan

proses untuk mencari solusi optimal.

Selanjutnya, program menentukan Greedy by profit dengan mencari nilai

keuntungan terbesar yaitu 25 dengan bobot 18. Karena masih memenuhi, lalu

mencari nilai keuntungan yang terbesar selanjutnya yaitu 24 dengan bobot 15.

Jika bobotnya dijumlahkan (18 + 15 = 33), maka kondisinya tidak memenuhi,

sehingga diambil sebagian saja, yaitu 24 x (20 - 18) / 15 = 24 x 2 / 15 = 3,2.

Maka menghasilkan keuntungan sebesar 25 + 3,2 = 28,2 dan bobot senilai 18 +

(2 / 15 x 15) = 18 + 2 = 20.

Kemudian, program menentukan Greedy by weight dengan mencari nilai

bobot yang terkecil, yaitu 10 dengan keuntungan 15. Karena masih memenuhi,

lalu mencari nilai bobot yang terkecil selanjutnya, yaitu 15 dengan keuntungan

24. Jika menjumlahkan bobotnya (10 + 15 = 25), maka kondisinya tidak

memenuhi, sehingga diambil sebagian saja, yaitu 15 x (20 - 10) / 15 = 15 x 2 /

3 = 10. Maka menghasilkan bobot bernilai 10 + 10 = 20 dan keuntungan

bernilai 15 + (2 / 3 x 24) = 15 + 16 = 31.

Lalu, program menentukan Greedy by density dengan mencari nilai

kepadatan yang terbesar, yaitu 1,6 dengan bobot 15. Karena masih memenuhi,

lalu mencari nilai kepadatan yang terbesar selanjutnya, yaitu 1,5 dengan bobot

10. Jika menjumlahkan bobotnya (15 + 10 = 25), maka kondisinya tidak

memenuhi, sehingga diambil sebagian saja, yaitu 10 x (20 - 15) / 10 = 10 x 1 /

2 = 5. Maka menghasilkan bobot senilai 15 + 5 = 20 dan keuntungan sebesar

24 + (1 / 2 x 15) = 24 + 7,5 = 31,5.

Dengan membandingkan hasil tersebut satu persatu, sehingga total hasil

optimal terletak pada nilai 31,5 dan total bobot optimal terletak pada nilai 20,

dengan solusi optimal pada barang ke-2 dan barang ke-3.

LAPORAN PRAKTIKUM


HUFFMAN CODE

DISUSUN OLEH:


M0513019

ASISTEN DOSEN:





JURUSAN INFORMATIKA



SURAKARTA

KAMIS, 20 NOVEMBER 2014

1. Integer Knapsack

a. Print Screen

b. Analisis

Program ini merupakan program sederhana yang berfungsi untuk

mengimplementasikan Huffman Code pada Java. Dalam pembuatannya, program

ini terbagi menjadi beberapa kelas yang terdapat dalam paket bernama Huffman.

Program ini juga mengimpor beberapa kelas dari koleksi perpustakaan Java, seperti

PriorityQueue dan Scanner. Program ini memiliki empat kelas dengan tipe,

metode, dan fungsi yang berbeda.

Kelas HuffmanTree bertipe abstrak mengimplementasikan antar muka

Comparable dengan tipe generik HuffmanTree. Kelas ini berfungsi memberikan

frekuensi dari kelas ini sendiri dengan mendeklarasikan variabel frequency bertipe

integer dan memproses metode HuffmanTree dengan parameter freq bertipe

integer. Parameter freq dinyatakan sebagai variabel frequency yang berarti nilai

freq sama dengan frequency.

Kelas HuffmanLeaf merupakan subkelas dari HuffmanTree dan memiliki

dua parameter, yaitu integer freq dan karakter val. Kelas ini beroperasi dengan

mengakses variabel freq pada superkelasnya dan memberikan nilai val kepada

value.

Kelas HuffmanNode merupakan subkelas dari HuffmanTree yang

mendeklarasikan variabel left dan right yang merupakan subpohon dari

HuffmanTree. Metode HuffmanNode dengan parameter Huffman Tree l dan

HuffmanTree r akan mengakses variabel l.frequency dan r.frequency dari

superkelasnya dan memberikan nilai l kepada left dan r kepada right.

Kelas HuffmanCode merupakan kelas publik yang dapat diakses oleh

metode dan kelas apapun dalam proyek ini. Kelas ini memiliki empat metode

dengan fungsi yang berbeda. Kelas ini mendeklarasikan variabel array string statis

bernama huruf dan kode dengan masing-masing variabel tersebut bernilai indeks

array 256. Kelas ini juga mendeklarasikan variabel integer statis bernama k

bernilai awal 0.

Di dalam kelas HuffmanCode terdapat metode buildTree yang membangun

sebuah tree dari HuffmanTree. Metode ini membuat objek baru bernama trees

dengan tipe PriorityQueue. Kemudian melakukan proses looping berdasarkan nilai

variabel charFreqs.length. Jika nilai charFreqs[i] bernilai lebih dari nol, maka

proses selanjutnya adalah mengakses metode offer pada objek trees dengan

membuat HuffmanLeaf baru berparameter charFreqs[i] dan char i. Program akan

melakukan assert terhadap trees.size dengan nilai lebih dari nol dan melakukan

looping sampai hanya tersisa satu tree. Metode ini akan mengembalikan nilai

trees.poll pada objek yang mengaksesnya.

Metode printCodes dalam kelas HuffmanCode dengan parameter

HuffmanTree tree dan StringBuffer prefix berfungsi untuk melakukan proses

dekode. Proses dilakukan dengan memberikan nilai tree tidak sama dengan null.

Jika nilai tree instanceof HuffmanLeaf sama dengan HuffmanLeaf tree, maka

program akan memberikan keluaran berupa nilai yang terdapat pada leaf.value,

leaf.frequency, dan prefix. Program akan memberikan nilai tambah kepada

variabel cetak dari nilai pada variabel leaf.value. Variabel huruf[k] diberi nilai

sama dengan variabel cetak dan variabel kode[k] diberikan nilai yang sama dengan

prefix.toString. Akan tetapi, jika nilai node pada HuffmanNode bernilai sama

dengan tree pada HuffmanNode, maka program akan memberikan nilai 0 pada

prefix.append dan mengakses prefix.deleteCharAt(prefix.length() - 1).

Metode yang lainnya adalah printAll yang berfungsi untuk mencetak hasil

dekode dari HuffmanTree. Metode ini membuat objek HashMap dengan parameter

generik String, String dengan nama compressed, mendeklarasikan nilai kosong dari

variabel string d, dan memberikan nilai compressed.put(huruf[i], kode[i]). Jika

nilai variabel y kurang dari h.length(), maka program akan menambahkan nilai

h.charAt(y) kepada variabel d dan menampilkan keluaran berupa hasil

pengaksesan compressed.get(d). Selanjutnya, program memberikan nilai kosong

pada variabel d.

Metode main yang merupakan metode terakhir dan utama berfungsi untuk

menjalankan program. Metode ini meminta pengguna untuk memasukkan string

yang akan didekode dan menyimpannya dalam variabel menggunakan perintah

Scanner. Metode ini juga mendeklarasikan nilai dari variabel array integer

charFreqs dengan indeks 256. Dengan menggunakan looping for (char c :

test.toCharArray), program membaca masing-masing karakter string yang

dimasukkan oleh pengguna dan merekam, menghitung, serta menyimpan

frekuensinya. Program akan membuat tree dari masing-masing karakter tersebut

dengan mengakses HuffmanTree, menampilkan hasil dari metode printCodes, dan

mencetak semua hasilnya, serta membuat dekode berdasarkan konsep tree yang

telah dibuat..

LAPORAN PRAKTIKUM


DISJOINT SET

DISUSUN OLEH:


M0513019

ASISTEN DOSEN:





JURUSAN INFORMATIKA



SURAKARTA

KAMIS, 4 DESEMBER 2014

1. UnionFind

a. Print Screen

b. Analisis

Program ini memiliki beberapa metode yang berguna untuk

mengimplementasikan disjoint set pada Java.

Metode String toString bersifat publik dan berguna untuk mengembalikan

nilai UnionFind yang nantinya akan digunakan pada metode utama.

Metode UnionFind bersifat publik, berparameter max yang bertipe integer,

dan berguna untuk membuat indeks max dari variabel _parent dan _rank dan

menyatakan nilai variabel i dengan fungsi perulangan terhadap variabel _parent

indeks ke-i.

Metode union bersifat publik, bertipe void, berparameter i dan j yang

bertipe integer, dan berguna untuk menggabungkan komponen yang ada di dalam

himpunan disjoint set.

Metode find bersifat publik, bertipe integer, berparameter i yang bertipe

integer, dan berguna untuk menemukan komponen yang ada di dalam himpunan

disjoint set dengan menyatakan bahwa nilai variabel p sama dengan variabel

_parent indeks ke-i, kemudian mengembalikan nilai i jika nilai variabel i sama

dengan p dan mengembalikan nilai variabel _parent indeks ke-i sama dengan

metode find berparameter p jika tidak sama.

Metode utama berguna untuk mencetak keluaran pada program. Pertama,

program membuat objek uf dari kelas UnionFind berparameter 5 dan mencetaknya

ke layar. Parent disimbolkan dengan huruf a, anggota disimbolkan dengan huruf p,

dan rank disimbolkan dengan huruf r.

a 0 1 2 3 4

p -1 -1 -1 -1 -1

r 0 0 0 0 0

Selanjutnya, program memanggil metode union melalui objek uf dengan

parameter 1 dan 2. Proses ini akan menggabungkan komponen ke-1 dan 2. Karena

rank ke-1 dan 2 memiliki nilai yang sama (0), maka program akan mengubah nilai

anggota ke-2 menjadi nilai komponen ke-1 (1) dan menambahkan 1 ke nilai rank

ke-1.

a 0 1 2 3 4

p -1 -1 1 -1 -1

r 0 1 0 0 0

Setelah itu, program memanggil metode union melalui objek uf dengan



anggota ke-4 menjadi nilai dari komponen ke-3 (3) dan menambahkan 1 ke nilai

rank ke-3.

a 0 1 2 3 4

p -1 -1 1 -1 3

r 0 1 0 1 0

Kemudian, program memanggil metode union melalui objek uf dengan


nilai rank ke-1 lebih besar daripada nilai rank ke-0 (1>0), maka program akan

mengubah nilai anggota ke-0 menjadi nilai dari komponen ke-1 (1).

a 0 1 2 3 4

p 1 -1 1 -1 3

r 0 1 0 1 0





rank ke-1.

a 0 1 2 3 4

p 1 -1 1 1 3

r 0 2 0 1 0

Terakhir, program memanggil metode find melalui objek uf dengan

parameter 4. Karena parent ke-4 bernilai sama dengan parameter (4), maka

program akan mengembalikan nilai kepada parameter (4) dan tidak terjadi

perubahan komponen.

a 0 1 2 3 4

p 1 -1 1 1 3

r 0 2 0 1 0

2. UnionFind2

a. Print Screen

b. Analisis

Program ini memiliki beberapa metode yang digunakan untuk

mengimplementasikan disjoint set pada Java.

Metode String toString bersifat publik dan berguna untuk mengembalikan

nilai UnionFind yang nantinya akan digunakan pada metode utama.

Metode UnionFind2 bersifat publik, berparameter max yang bertipe

integer, dan berguna untuk membuat indeks max dari variabel _parent dan _rank

dan menyatakan nilai variabel i dengan fungsi perulangan terhadap variabel

_parent indeks ke-i.

Metode union bersifat publik, bertipe void, berparameter i dan j yang

bertipe integer, dan berguna untuk menggabungkan komponen yang ada di dalam

himpunan disjoint set.

Metode find bersifat publik, bertipe integer, berparameter i yang bertipe

integer, dan berguna untuk menemukan komponen yang ada di dalam himpunan

disjoint set dengan mengembalikan nilai i jika nilai variabel i sama dengan _parent

indeks ke-i. Jika nilainya tidak sama, program akan membuat variabel integer baru

bernama result yang bernilai sama dengan metode find berparameter variabel

_parent indeks ke-i, menyatakan bahwa nilai variabel _parent indeks ke-i sama

dengan variabel result, dan mengembalikan nilai kepada result.

Metode utama berguna untuk mencetak keluaran pada program. Pertama,

program membuat objek uf dari kelas UnionFind berparameter 5 dan mencetaknya

ke layar. Parent disimbolkan dengan huruf p, anggota disimbolkan dengan huruf a,

dan rank disimbolkan dengan huruf r.

p 0 1 2 3 4

a -1 -1 -1 -1 -1

r 0 0 0 0 0




anggota ke-2 menjadi nilai komponen ke-1 (1) dan menambahkan 1 ke nilai rank

ke-1.

p 0 1 2 3 4

a -1 -1 1 -1 -1

r 0 1 0 0 0

Setelah itu, program memanggil metode union melalui objek uf dengan




rank ke-3.

p 0 1 2 3 4

a -1 -1 1 -1 3

r 0 1 0 1 0

Kemudian, program memanggil metode union melalui objek uf dengan


nilai rank ke-1 lebih besar daripada nilai rank ke-0 (1>0), maka program akan

mengubah nilai anggota ke-0 menjadi nilai dari komponen ke-1 (1).

p 0 1 2 3 4

a 1 -1 1 -1 3

r 0 1 0 1 0





rank ke-1.

p 0 1 2 3 4

a 1 -1 1 1 3

r 0 2 0 1 0

Terakhir, program memanggil metode find melalui objek uf dengan

parameter 4. Karena parent ke-4 bernilai sama dengan parameter (4), maka

program akan mengembalikan nilai kepada parameter (4) dan tidak terjadi

perubahan komponen.

p 0 1 2 3 4

a 1 -1 1 1 3

r 0 2 0 1 0

LAPORAN PRAKTIKUM


DIVIDE AND CONQUER

DISUSUN OLEH:


M0513019

ASISTEN DOSEN:





JURUSAN INFORMATIKA



SURAKARTA


1. Tes1

a. Print Screen

Tes1

MergeSort

BubbleSort

Output

b. Analisis

Program di dalam paket Tes1 yang memiliki beberapa kelas, yaitu Tes1,

MergeSort, dan BubbleSort ini berguna untuk mengurutkan data acak yang

awalnya tidak berurutan dengan algoritma pengurutan MergeSort dan BubbleSort.

Kelas Tes1 yang bersifat publik memiliki satu metode yang merupakan

metode utama. Metode ini menggunakan fungsi Random untuk membuat variabel

data bertipe integer yang memiliki array sebanyak variabel limit. Variabel limit

dideklarasikan bertipe integer dan bernilai 200.

Program akan mencetak 200 variabel data yang tersusun dalam array

menggunakan fungsi perulangan for. Dengan nilai awal variabel i = 0 dan selama

nilainya masih lebih kecil daripada limit (200), program akan mendeklarasikan

variabel data indeks ke-i menggunakan metode rnd.nextInt(limit) dan

menambahkan satu nilai kepada variabel i setiap selesai perulangan.

Program akan mendeklarasikan objek m, variabel mrg, dan memanggil

metode mergeSort dari kelas MergeSort. Dalam kelas ini, program akan

melakukan pengurutan data acak tersebut menggunakan algoritma MergeSort yang

menggunakan prinsip divide and conquer.

Contoh pengurutan data array acak {38, 27, 43, 3, 9, 82, 10} menggunakan

MergeSort adalah sebagai berikut:

Array tersebut dibagi menjadi dua bagian, jika jumlahnya ganjil, maka

bagian pertama memiliki array lebih banyak daripada bagian kedua {38, 27,

43, 3} dan {9, 82, 10}.

Masing-masing bagian tersebut dibagi lagi menjadi dua bagian, jika

jumlahnya ganjil, maka bagian pertama memiliki array lebih banyak

daripada bagian kedua {38, 27}, {43, 3}, {9, 82}, dan {10}.

Masing-masing bagian tersebut yang memiliki lebih dari satu array dibagi

lagi menjadi dua bagian {38}, {27}, {43}, {3}, {9}, {82}, dan {10}.

Setiap dua bagian array tersebut kemudian digabungkan dan diurutkan

sehingga menjadi {27, 38}, {3, 43}, {9, 82}, dan {10}.

Setiap dua bagian array tersebut kemudian digabungkan dan diurutkan lagi

sehingga menjadi {3, 27, 38, 43} dan {9, 10, 82}.

Semua array tersebut kemudian digabungkan dan diurutkan sehingga

menjadi {3, 9, 10, 27, 38, 43, 82}.

Program akan menampilkan hasil pengurutannya menggunakan fungsi

perulangan for. Dengan nilai awal variabel i = 0 dan selama nilainya lebih kecil

daripada mrg.length, maka akan mencetak variabel mrg indeks ke-i dan

menambah satu nilai kepada variabel i. Program juga akan menampilkan waktu

pemrosesannya menggunakan fungsi System.nanoTime().

Program akan mendeklarasikan objek b, variabel p, dan memanggil metode

bubbleSort dari kelas BubbleSort. Dalam kelas ini, program akan melakukan

pengurutan data acak tersebut menggunakan algoritma BubbleSort.

Contoh pengurutan data array acak (5 1 4 2 8) menggunakan BubbleSort

adalah sebagai berikut:

( 5 1 4 2 8 ) menjadi ( 1 5 4 2 8 ), membandingkan dua elemen pertama (5

dan 1) dan menukarnya karena 5 > 1.

( 1 5 4 2 8 ) menjadi ( 1 4 5 2 8 ), membandingkan elemen 5 dan 4 dan

menukarnya karena 5 > 4.

( 1 4 5 2 8 ) menjadi ( 1 4 2 5 8 ), membandingkan elemen ketiga 5 dan 2

dan menukarnya karena 5 > 2.

( 1 4 2 5 8 ) menjadi ( 1 4 2 5 8 ), membandingkan dua elemen terakhir (5

dan 8) dan tidak menukarnya karena telah berurutan (8 > 5).

( 1 4 2 5 8 ) menjadi ( 1 2 4 5 8 ), membandingkan elemen 4 dan 2 dan

menukarnya karena 4 > 2.



daripada p.length, maka akan mencetak variabel p indeks ke-i dan menambah

satu nilai kepada variabel i. Program juga akan menampilkan waktu

pemrosesannya menggunakan fungsi System.nanoTime().

2. Tes2

a. Print Screen

Tes2

BSBF

Output

b. Analisis

Program di dalam paket Tes2 yang memiliki beberapa kelas, yaitu Tes2,

QSDC, dan BSBF ini berguna untuk mengurutkan data acak yang awalnya tidak

berurutan dengan algoritma pengurutan MergeSort dan BubbleSort.

Kelas Tes1 yang bersifat publik memiliki satu metode yang merupakan

metode utama. Metode ini menggunakan fungsi Random untuk membuat variabel

data bertipe integer yang memiliki array sebanyak variabel limit. Variabel limit

dideklarasikan bertipe integer dan bernilai 200.

Program akan mencetak 200 variabel data yang tersusun dalam array

menggunakan fungsi perulangan for. Dengan nilai awal variabel i = 0 dan selama

nilainya masih lebih kecil daripada limit (200), program akan mendeklarasikan

variabel data indeks ke-i menggunakan metode rnd.nextInt(limit) dan

menambahkan satu nilai kepada variabel i setiap selesai perulangan.

Program akan mendeklarasikan objek qsdc, variabel q, dan memanggil

metode sort dari kelas QSDC. Dalam kelas ini, program akan melakukan

pengurutan data acak tersebut menggunakan algoritma quicksort yang

menggunakan prinsip divide and conquer.

Contoh pengurutan data array acak (3, 7, 8, 5, 2, 1, 9, 4) menggunakan

algoritma quicksort adalah sebagai berikut:

Mengambil sebuah elemen, yang disebut dengan pivot, misalnya 4.

Mengurutkan list sehingga elemen dengan nilai yang lebih kecil daripada 4

berada sebelum 4, sedangkan seluruh elemen yang memiliki nilai yang

lebih besar daripada 4 berada setelahnya.

Membagi list menjadi dua buah sublist yang lebih kecil: elemen kecil dan

elemen besar.

Setelah pemisahan, 4 berada pada posisi akhirnya. Operasi ini disebut

partisi.

Sublist kemudian disortir secara rekursif dari elemen yang lebih kecil dan

sublist dari elemen yang lebih besar.



daripada q, maka akan mencetak variabel q indeks ke-i dan menambah satu nilai

kepada variabel i. Program juga akan menampilkan waktu eksekusinya

menggunakan fungsi System.nanoTime(). Dalam percobaan kali ini,

didapatkan waktu eksekusi sebesar 254.520 nanosekon.

Program akan mendeklarasikan objek bsbf, variabel p, dan memanggil

metode sort dari kelas BubbleSort. Dalam kelas ini, program akan melakukan

pengurutan data acak tersebut menggunakan algoritma bubble sort yang

menggunakan prinsip brute force.



daripada p.length, maka akan mencetak variabel p indeks ke-i dan menambah satu

nilai kepada variabel i. Program juga akan menampilkan waktu eksekusinya

menggunakan fungsi System.nanoTime(). Dalam percobaan kali ini, didapatkan

waktu eksekusi sebesar 21.201.145 nanosekon.

Dari kedua algoritma di atas, dapat disimpulkan bahwa waktu eksekusi

yang dilakukan oleh algoritma quicksort dengan prinsip divide and conquer

(QSDC) jauh lebih cepat daripada algoritma bubble sort dengan prinsip brute force

(BSBF). Hal ini dikarenakan algoritma QSDC memiliki proses yang lebih simpel

dibandingkan dengan algoritma BSBF.

0 5000000 10000000 15000000 20000000 25000000

Waktu Eksekusi (nanosekon)

Diagram Waktu Eksekusi Program

Quicksort (Divide and Conquer) Bubble Sort (Brute-force)

LAPORAN PRAKTIKUM


PATTERN MATCHING

DISUSUN OLEH:


M0513019

ASISTEN DOSEN:





JURUSAN INFORMATIKA



SURAKARTA


1. Brute

a. Print Screen

Output

b. Analisis

Kelas Brute bersifat publik terletak di dalam paket PatternMatching

berguna untuk mengimplementasikan algoritma Brute-Force di Java. Kelas ini

memiliki metode search1 dan main. Metode search1 memiliki parameter pat dan

txt bertipe string. Metode ini berguna untuk menemukan pattern (pola) yang

diinginkan dari sebuah teks.

Metode ini mendeklarasikan variabel M bertipe integer sebagai panjang

pola dan variabel N bertipe integer sebagai panjang teks. Secara sistematis,

langkah-langkah yang dilakukan algoritma ini dalam metode search1 pada saat

mencocokkan pola adalah:

1. Mulai mencocokkan pola pada awal teks dengan fungsi perulangan for,

mendeklarasikan nilai awal variabel i = 0 bertipe integer, nilai akhir

variabel i ≤ N – M, dan penambahan satu nilai pada variabel i.

2. Mendeklarasikan variabel j bertipe integer, dari kiri ke kanan, algoritma ini

akan mencocokkan karakter perkarakter pola dengan karakter di teks yang

bersesuaian dengan fungsi perulangan for, nilai awal variabel j = 0, nilai

akhir variabel j < M, dan penambahan satu nilai pada variabel j, sampai

salah satu kondisi berikut dipenuhi:

1. Karakter di pola dan di teks yang dibandingkan tidak cocok

(mismatch). Jika (txt.charAt(i + j) ≠ pat.charAt(j)), memanggil

fungsi break.

2. Semua karakter di pola cocok. Kemudian algoritma akan

memberitahukan penemuan di posisi ini. Jika nilai variabel j = M,

mengembalikan nilai ke variabel i sebagai indeks lokasi penemuan

pola pada teks.

3. Algoritma kemudian terus menggeser pola sebesar satu ke kanan, dan

mengulangi langkah ke-2 sampai pola berada di ujung teks.

Berikut adalah Algoritma Brute-Force yang sedang bekerja mencari string:

Usaha Ke-1

Teks a b a c a d a b ...

Pola a b a c a d

0 1 2 3 4 5

Pola ditemukan pada indeks ke-0 teks.

Metode utama bernama main mendeklarasikan isi variabel pat bertipe string

berupa pola “abacad” dan isi variabel txt bertipe string berupa teks

“abacadabrabracabracadabrabrabracad”. Metode ini akan memanggil variabel

offset1a bertipe integer untuk mencari variabel pat pada txt dan mencetak variabel

teks dan pola. Untuk menambahkan spasi, digunakan fungsi perulangan for dengan

mendeklarasikan nilai awal variabel i = 0 bertipe integer, nilai akhir variabel i <

offset1a, dan menambah satu nilai pada variabel i.

Untuk hasil akhirnya, jika nilai variabel offset1a = panjang teks, mencetak

tulisan “Tidak ditemukan”. Jika nilainya tidak sama, mencetak tulisan “Pattern

ditemukan pada index ke” diikuti indeks lokasi penemuan pola dalam teks, yaitu

variabel offset1a.

2. KMP

a. Print Screen

Output

b. Analisis

Kelas KMP dalam paket PatternMatching berguna untuk

mengimplementasikan algoritma Knuth-Morris-Pratt dalam Java. Kelas ini

memiliki metode kmpmatch yang memiliki parameter text (teks) dan pattern (pola)

bertipe string.

Secara sistematis, langkah-langkah yang dilakukan dalam metode ini pada

saat mencocokkan pola adalah:

1. Mulai mencocokkan pola pada awal teks.

2. Dari kiri ke kanan, algoritma ini akan mencocokkan karakter perkarakter

pola dengan karakter di teks yang bersesuaian, sampai salah satu kondisi

berikut dipenuhi:

1. Karakter di pola dan di teks yang dibandingkan tidak cocok

(mismatch).

2. Semua karakter di pola cocok. Kemudian algoritma akan

memberitahukan penemuan di posisi ini.

3. Algoritma kemudian menggeser pola berdasarkan tabel next, lalu

mengulangi langkah 2 sampai pattern berada di ujung teks.

Metode utama main berfungsi untuk menampilkan output. Metode ini

mendeklarasikan variabel text bertipe string berupa teks “abracadabra” dan

variabel pat bertipe string berupa teks “raca”, menampilkan output berupa teks dan

pattern dengan mendeklarasikan variabel integer posn dan memanggil metode

kmpmatch berparameter text dan pat, dan mencetak karakter kosong dengan fungsi

perulangan for. Metode ini akan mencetak tulisan “Tidak ditemukan” jika nilai

variabel posn = -1 dan tulisan “Pattern ditemukan pada index ke” diikuti dengan

indeks lokasi penemuan pola pada teks jika nilai variabel posn ≠ -1.

Jika kita melihat algoritma Brute-Force lebih mendalam, kita mengetahui

bahwa dengan mengingat beberapa perbandingan yang dilakukan sebelumnya kita

dapat meningkatkan besar pergeseran yang dilakukan. Hal ini akan menghemat

perbandingan, yang selanjutnya akan meningkatkan kecepatan pencarian.

Perhitungan penggeseran pada algoritma KMP adalah sebagai berikut, bila

terjadi ketidakcocokkan pada saat pattern sejajar dengan teks[i..i+n-1], kita bisa

menganggap ketidakcocokan pertama terjadi di antara teks[i+j] dan pattern[j],

dengan 0 < j < n. Berarti, teks[i..i+j-1] = pattern[0..j-1] dan a=teks[i+j] tidak sama

dengan b=pattern[j]. Ketika kita menggeser, sangat beralasan bila ada sebuah

awalan v dari pattern akan sama dengan sebagian akhiran u dari sebagian teks.

Sehingga kita bisa menggeser pattern agar awalan v tersebut sejajar dengan akhiran

dari u.

Dengan kata lain, pencocokkan string akan berjalan secara efisien bila kita

mempunyai tabel yang menentukan berapa panjang kita seharusnya menggeser

seandainya terdeteksi ketidakcocokkan di karakter ke-j dari pattern. Tabel itu harus

memuat next[j] yang merupakan posisi karakter pattern[j] setelah digeser, sehingga

kita bisa menggeser pattern sebesar j-next[j] relatif terhadap teks.

Jadi, dapat disimpulkan bahwa algoritma Knuth-Morris-Pratt relatif lebih

baik daripada algoritma Brute-Force.

laporan praktikum struktur data dan algoritma

Education