際際滷 Presentation Final Project (S1)
Download as PPTX, PDF
2 likes1,204 views
Dokumen tersebut membahas perbandingan antara algoritma Knuth-Morris-Pratt dan algoritma Boyer-Moore dalam mencari kata yang tersembunyi pada permainan word search puzzle. Algoritma Boyer-Moore dinilai lebih efisien dibandingkan algoritma Knuth-Morris-Pratt karena memiliki kompleksitas waktu O(N/M) dibandingkan O(M+N).
![PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE
(11)
1)
BmBc & BmGs
Index 0 1 2 3 4 5 6 7
Karakter F L A M I N G O
Nilai OH 7 6 5 4 3 2 1 0
Nilai MH 8 8 8 8 8 8 8 1
Teks : Y H X B F L A M I N G O H Z V
Pattern : F L A M I N G O
BmGs [7] = BmBc[M] -7 + 7 atau Max (1 = 4 - 7 + 7 ) = 4
2)
Teks : Y H X B F L A M I N G O H Z V
Pattern : F L A M I N G O
Tahap pencarian dengan algoritma Boyer-Moore diatas pencarian selesai setelah
melakukan sebanyak 1 iterasi.
* *](https://image.slidesharecdn.com/1-141015142012-conversion-gate01/85/際際滷-Presentation-Final-Project-S1-50-320.jpg)
際際滷 Presentation Final Project (S1)
- 1. ANALISIS PERBANDINGAN ALGORITMA KNUTH-MORRIS-PRATT DENGAN ALGORITMA BOYER-MOORE PADA PERMAINAN WORD SEARCH PUZZLE OLEH : ASEP ROJALI (10109411)
- 3. PERMAINAN WORD SEARCH PUZZLE
- 4. Sistem dapat menemukan semua kata yang tersembunyi * di dalam puzzle yang tersusun secara random Penelitian sebelumnya Algoritma Knuth-Morris-Pratt (word search puzzle) Perbandingan Algoritma Knuth-Morris-Pratt dan Algoritma Boyer-Moore
- 6. Implementasi algoritma Boyer-Moore pada permainan word search puzzle tidak hanya untuk satu arah, disesuaikan dengan karakteristik pencarian pada permainan word search puzzle
- 8. MAKSUD Algoritma Knuth-Morris-Pratt VS Algoritma Boyer-Moore Permainan word search puzzle
- 9. TUJUAN Algoritma Boyer-Moore lebih baik dari Algoritma Knuth-Morris-Pratt pada permainan word search puzzle pada panjang bidang papan permainan, panjang kata dan posisi kata
- 10. BATASAN MASALAH
- 11. Algoritma Knuth-Morris-Pratt VS Algoritma Boyer-Moore Bidang papan permainan memiliki bentuk matriks n x n Ukuran panjang bidang papan permainan dinamis Pengujian menggunakan beberapa pola kata dari beberapa panjang kalimat yaitu 3-10 karakter dan menggunakan 8 sampel dengan posisi random Pengujian kata-kata diambil dari nama-nama hewan dalam Bahasa Indonesia.
- 13. * Metode Penelitian Eksperimental Tahap Pengumpulan Data Tahap Analisis Algoritma
- 14. * INISIALISASI PAPAN PERMAINAN
- 15. *
- 16. * PENCARIAN KATA PADA PAPAN PERMAINAN
- 17. PENCARIAN KATA PADA PERMAINAN 1. Kiri ke kanan, jika tidak ketemu ubah cara baca 2. Kanan ke kiri, jika tidak ketemu ubah cara baca 3. Atas ke bawah, jika tidak ketemu ubah cara baca 4. Bawah ke atas, jika tidak ketemu ubah cara baca 5. Secara diagonal dari kiri atas ke kanan bawah, jika tidak ketemu ubah cara baca 6. Secara diagonal dari kanan bawah ke kiri atas, jika tidak ketemu ubah cara baca 7. Secara diagonal dari kanan atas ke kiri bawah, jika tidak ketemu ubah cara baca 8. Secara diagonal dari kiri bawah ke kanan atas, , jika tidak ketemu ubah cara baca
- 19. *
- 20. ALGORITMA KNUTH-MORRIS-PRATT Fungsi pinggiran untuk pergeseran Memiliki kompleksitas O(M+N) Arah pencocokan dari kiri ke kanan
- 21. ALGORITMA BOYER-MOOR Fungsi bad-character shift dan good-suffix shift untuk pergeseran Memiliki kompleksitas O(N/M) Arah pencocokan dari kanan ke kiri
- 22. * PSEUDECODE ALGORITMA DENGAN NOTASI Big-O
- 23. * ALGORITMA KNUTH-MORRIS-PRATT(1) Hasil dari notasi Big-O hitung nilai pinggiran : O(1) + O(1) + O(1) + O(M) + O(1) + O(1) + O(1) + O(1) + O(1) = 7 + 1M kali = O(M) Pseudocode Hitung Pinggiran :
- 24. * ALGORITMA KNUTH-MORRIS-PRATT(2) Hasil dari notasi Big-O hitung nilai pinggiran : O(M) + O(1) + O(1) + O(1) + O(N) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) = 10 + 1M kali + 1N kali = O(M+N) Pseudocode Pencarian Kata :
- 25. * ALGORITMA BOYER-MOORE(1) Hasil dari notasi Big-O hitung nilai pinggiran : O(M) + O(M) + O(1) + O(1) + O(N) + O(1) + O(1) + O(1) + O(1) = 6N+1N+2M kali = O(N/M) Pseudocode Pencarian Kata :
- 26. ANALISIS ALGORITMA PADA PERMAINAN
- 27. *
- 28. *
- 29. * 1 2
- 30. * 1 2
- 31. ANALISIS ALGORITMA TERHADAP KASUS
- 32. TEXT YHXBFLAMINGOHZV SMKOBXTHRABAXZ JHAEENHNLMMND JIKBKATDKSBH ATIBDZTBTEI NUSWNQYETU GPEMZCRTY KKRZBBBG RAIEKMV ILBFLT KAUAH TJYF MAC MM X
- 33. PENCARIAN MENGGUNAKAN ALGORITMA KNUTH-MORRIS- PRATT 1.Tahap Preprocessing (Menghitung nilai pinggiran) 2.Tahap Pencarian Kata
- 35. PENCARIAN MENGGUNAKAN ALGORITMA KNUTH-MORRIS-PRATT(1) Substring Pattern Prefix dan Suffix Nilai Pinggiran F L A M I N G O 0 0 1 0 0 0 0 0 * *
- 36. PENCARIAN MENGGUNAKAN ALGORITMA KNUTH-MORRIS-PRATT( 2) Tahap Pencarian Kata : Teks : Y H X B F L A M I N G O H Z V Pattern : F L A M I N G O F L A M I N G O 0 0 0 0 0 0 0 0 1) 2) Tidak terjadi ketidakcocokan, maka pattern digeser sejumlah 1 karakter Teks : Y H X B F L A M I N G O H Z V Pattern : F L A M I N G O Tidak terjadi ketidakcocokan, maka pattern digeser sejumlah 1 karakter F L A M I N G O 0 0 0 0 0 0 0 0 Teks : Y H X B F L A M I N G O H Z V Pattern : F L A M I N G O F L A M I N G O 0 0 0 0 0 0 0 0 3) Tidak terjadi ketidakcocokan, maka pattern digeser sejumlah 1 karakter
- 37. PENCARIAN MENGGUNAKAN ALGORITMA KNUTH-MORRIS-PRATT( 3) Tahap Pencarian Kata : 4) Teks : Y H X B F L A M I N G O H Z V Pattern : F L A M I N G O Tidak terjadi ketidakcocokan, maka pattern digeser sejumlah 1 karakter F L A M I N G O 0 0 0 0 0 0 0 0 Teks : Y H X B F L A M I N G O H Z V Pattern : F L A M I N G O F L A M I N G O 0 0 0 0 0 0 0 0 5) Tahap pencarian dengan algoritma Knuth-Morris-Pratt selesai setelah melakukan sebanyak 4 iterasi
- 38. PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE 1.Tahap Preprocessing (Menghitung nilai bad-character shift dan good-suffix shift) 2.Tahap Pencarian Kata
- 40. PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE BAD-CHARACTER SHIFT(1) Mulai : Index = Panjang (pattern)-2 F L A M I N G O Pindah = 1 Tabel comparator BmBc Bandingkan G dengan Null Hasil BmBc(sebelum) BmBc(sesudah) Karakter Null Karakter G Nilai OH Null Nilai OH 1 1) Mulai : Index = Panjang (pattern)-3 F L A M I N G O Pindah = 2 Tabel comparator BmBc Bandingkan N dengan G" Hasil BmBc(sebelum) BmBc(sesudah) Karakter G Karakter N G Nilai OH 1 Nilai OH 2 1 2) * *
- 41. PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE BAD-CHARACTER SHIFT(2) Mulai : Index = Panjang (pattern)-4 F L A M I N G O Pindah = 3 Tabel comparator BmBc Bandingkan I dengan G,N Hasil BmBc(sebelum) BmBc(sesudah) Karakter G N Karakter I N G Nilai OH 1 2 Nilai OH 3 2 1 3) Mulai : Index = Panjang (pattern)-5 F L A M I N G O Pindah = 4 Tabel comparator BmBc Bandingkan M dengan G,N,I Hasil BmBc(sebelum) BmBc(sesudah) Karakter G N I Karakter M I N G Nilai OH 1 2 3 Nilai OH 4 3 2 1 4) * *
- 42. PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE BAD-CHARACTER SHIFT(3) Mulai : Index = Panjang (pattern)-6 F L A M I N G O Pindah = 5 5) Tabel comparator BmBc Bandingkan A dengan G,N,I,M BmBc(sebelum) BmBc(sesudah) Karakter G N I M Karakter A M I N G Nilai OH 1 2 3 4 Nilai OH 5 4 3 2 1 Mulai : Index = Panjang (pattern)-7 Hasil F L A M I N G O Pindah = 6 6) Tabel comparator BmBc Bandingkan L dengan G,N,I,M,A Hasil BmBc(sebelum) BmBc(sesudah) Karakter G N I M A Karakter L A M I N G Nilai OH 1 2 3 4 5 Nilai OH 6 5 4 3 2 1 * *
- 43. PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE BAD-CHARACTER SHIFT(4) Mulai : Index = Panjang (pattern)-1 F L A M I N G O Pindah = 7 7) Tabel comparator BmBc Hasil BmBc(sebelum) BmBc(sesudah) Karakter G N I M A L Karakter F L A M I N G Nilai OH 1 2 3 4 5 6 Nilai OH 7 6 5 4 3 2 1 Mulai : Index = Panjang (pattern)-1 Bandingkan F dengan G,N,I,M,A,L F L A M I N G O Pindah = 8 8) Tabel comparator BmBc Bandingkan O dengan G,N,I,M,A,L,F Hasil BmBc(sebelum) BmBc(sesudah) Karakter G N I M A L F Karakter F L A M I N G 0 Nilai OH 1 2 3 4 5 6 7 Nilai OH 7 6 5 4 3 2 1 0 * *
- 44. PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE GOOD-SUFFIX SHIFT(5) * *
- 45. PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE GOOD-SUFFIX SHIFT(6) * *
- 46. PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE GOOD-SUFFIX SHIFT(7) 1) Suffix 2) Suffix Index 7 Prefix O Move Suffix NULL Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? Index 0 1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 1 Index 6 Prefix G Move Suffix O Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? Index 0 1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 1 * *
- 47. PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE GOOD-SUFFIX SHIFT(8) 3) Suffix 4) Suffix Index 5 Prefix N Move Suffix GO Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? Index 0 1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 8 1 Index 4 Prefix I Move Suffix NGO Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? Index 0 1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 8 8 1 * *
- 48. PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE GOOD-SUFFIX SHIFT(9) 5) Suffix 6) Suffix Index 3 Prefix M Move Suffix INGO Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? Index 0 1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 8 8 8 1 Index 2 Prefix A Move Suffix MINGO Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? Index 0 1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 8 8 8 8 1 * *
- 49. PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE GOOD-SUFFIX SHIFT(10) 7) Suffix 8) Suffix Index 1 Prefix L Move Suffix AMINGO Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? Index 0 1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 8 8 8 8 8 1 Index 0 Prefix F Move Suffix LAMINGO Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? Index 0 1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 8 8 8 8 8 8 1 * *
- 50. PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE (11) 1) BmBc & BmGs Index 0 1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai OH 7 6 5 4 3 2 1 0 Nilai MH 8 8 8 8 8 8 8 1 Teks : Y H X B F L A M I N G O H Z V Pattern : F L A M I N G O BmGs [7] = BmBc[M] -7 + 7 atau Max (1 = 4 - 7 + 7 ) = 4 2) Teks : Y H X B F L A M I N G O H Z V Pattern : F L A M I N G O Tahap pencarian dengan algoritma Boyer-Moore diatas pencarian selesai setelah melakukan sebanyak 1 iterasi. * *
- 51. IMPLEMENTASI SISTEM * *
- 52. * IMPLEMENTASI ANTAR MUKA PERMAINAN(1) Papan Permainan
- 53. * IMPLEMENTASI ANTAR MUKA PERMAINAN(2) Set Papan Permainan
- 54. * IMPLEMENTASI ANTAR MUKA PERMAINAN(3) Pencarian Menggunakan Algoritma Knuth-Morris-Pratt
- 55. * IMPLEMENTASI ANTAR MUKA PERMAINAN(4) Pencarian Menggunakan Algoritma Boyer-Moore
- 56. * PENGUJIAN
- 57. * PENGUJIAN PADA PANJANG PAPAN(1) Kondisi dengan bidang papan 20x20, 30x30,40x40 dan 50x50 Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random Pengujian akan dilakukan 4 kali sesuai dengan bidang papan dengan kondisi pola kata random
- 58. * PENGUJIAN PADA PANJANG PAPAN(2)
- 59. PENGUJIAN PADA PANJANG PAPAN(3) * *
- 60. PENGUJIAN PADA POSISI POLA 20x20(1) Kondisi dengan bidang papan 20x20 Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random Pengujian akan dilakukan 8 kali sesuai dengan banyak kata dengan kondisi posisi pola terpenuhi semua. * *
- 61. * PENGUJIAN PADA POSISI POLA 20x20(2)
- 62. PENGUJIAN PADA POSISI POLA 20x20(3) * *
- 63. PENGUJIAN PADA POSISI POLA 30x30(1) Kondisi dengan bidang papan 30x30 Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random Pengujian akan dilakukan 8 kali sesuai dengan banyak kata dengan kondisi posisi pola terpenuhi semua. * *
- 64. * PENGUJIAN PADA POSISI POLA 30x30(2)
- 65. PENGUJIAN PADA POSISI POLA 30x30(3) * *
- 66. PENGUJIAN PADA POSISI POLA 40x40(1) Kondisi dengan bidang papan 40x40 Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random Pengujian akan dilakukan 8 kali sesuai dengan banyak kata dengan kondisi posisi pola terpenuhi semua. * *
- 67. * PENGUJIAN PADA POSISI POLA 40x40(2)
- 68. PENGUJIAN PADA POSISI POLA 40x40(3) * *
- 69. PENGUJIAN PADA POSISI POLA 50x50(1) Kondisi dengan bidang papan 50x50 Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random Pengujian akan dilakukan 8 kali sesuai dengan banyak kata dengan kondisi posisi pola terpenuhi semua. * *
- 70. * PENGUJIAN PADA POSISI POLA 50x50(2)
- 71. PENGUJIAN PADA POSISI POLA 50x50(3) * *
- 72. KESIMPULAN * *
- 73. Secara umum algoritma Boyer-Moore lebih efisien daripada algoritma Knuth-Morris-Pratt. Pencarian pada posisi diagonal dapat menambah waktu pencarian pada kedua algoritma Knuth-Morris-Pratt dan algoritma Boyer-Moore Parameter seperti panjang papan, posisi pola dan panjang kata dapat mempengaruhi efisiensi algoritma pencarian string pada algoritma Knuth-Morris-Pratt *
- 74. * SARAN
- 75. * Algoritma Boyer-Moore pada word search puzzle dapat diterapkan pada aplikasi game sesungguhnya
- 76. * DEMO SIMULASI
- 77. * TERIMA KASIH