Penerapan Algoritma Knuth-Morris-Pratt Pada Game Puzzle Untuk Mencari Kecocokan Pola Warna

Mulyana, Falih (2014) Penerapan Algoritma Knuth-Morris-Pratt Pada Game Puzzle Untuk Mencari Kecocokan Pola Warna. Diploma thesis, Universitas Komputer Indonesia.

Full text not available from this repository.
Official URL: http://elib.unikom.ac.id/gdl.php?mod=browse&op=rea...

Abstract

Algoritma pencarian adalah suatu metode yang digunakan untuk menyelesaikan masalah pencarian khususnya pada implementasi di bidang teknologi informasi. Salah satu algoritma yang dikenal cukup efisien dalam melakukan pencarian adalah algoritma Knuth-Morris-Pratt. Algoritma ini bekerja dengan mencari perulangan pola pada sebuah sususan array yang dicari yang selanjutnya digunakan sebagai acuan untuk melakukan pencarian lebih singkat. Pada jurnal yang berjudul ��Aplikasi Algoritma Pencarian String Knuth-Morris-Pratt dalam Permainan Word Search��, telah dibuktikan bahwa algoritma pencarian Knuth-Morris-Pratt ini dapat diimplementasikan pada sebuah permainan puzzle. Namun, hasil performansi dan hasil implementasinya tidak terdokumentasi dan tidak pula diperbandingkan dengan metode pencarian lain, sehingga dari penelitian itu belum dapat disimpulkan apakah algoritma KMP ini secara relatif lebih baik dibandingkan dengan suatu algoritma pencarian lain untuk implementasinya dalam suatu permainan puzzle.Dari permasalahan yang telah disebutkan, maka algoritma KMP ini akan dibandingkan performansinya dengan metode pencarian Brute Force dengan mengimplementasikan kedua algoritma tersebut ke dalam sebuah permainan teka-teki warna. Parameter hasil pencarian yang akan diukur adalah banyaknya memori yang digunakan, banyaknya perulangan yang dilakukan dan batas maksimal masing-masing algoritma melakukan perulangan dengan menggunakan standar big-O.Dari hasil penelitian menunjukkan bahwa algoritma pencarian Knuth-Morris-Pratt relatif lebih cepat karena melakukan perulangan lebih sedikit dan lebih terskala dalam hal kompleksitas waktu yang artinya maksimal perulangan relatif lebih kecil dibandingkan dengan algoritma pencarian Brute Force. Namun algoritma Knuth-Morris-Pratt membutuhkan space memori lebih besar dibandingkan dengan algoritma Brute Force karena algoritma KMP menyimpan tambahan informasi berupa overlap, yaitu informasi tentang pola-pola yang berulang.

Item Type: Thesis (Diploma)
Uncontrolled Keywords: algoritma pencarian, brute force, Knuth-Morris-Pratt, perbandingan algoritma
Subjects: S1-Final Project > Fakultas Teknik Dan Ilmu Komputer > Teknik Informatika > 2014
Divisions: Universitas Komputer Indonesia > Fakultas Teknik dan Ilmu Komputer
Universitas Komputer Indonesia > Fakultas Teknik dan Ilmu Komputer > Teknik Informatika (S1)
Depositing User: Admin Repository
Date Deposited: 16 Nov 2016 08:10
Last Modified: 16 Nov 2016 08:10
URI: http://repository.unikom.ac.id/id/eprint/29142

Actions (login required)

View Item View Item