Teknik Informatika (S1)

Permanent URI for this collection

https://repository.unpad.ac.id/handle/kandaga/269

Browse

Browsing Teknik Informatika (S1) by Subject "Algoritma"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    ANALISIS PERBANDINGAN ALGORITMA DIJKSTRA DAN A* DALAM MENENTUKAN JALUR KELUAR TERCEPAT PADA SIMULASI LABIRIN
    (2018-05-19) RIO NUR ARDIANSYAH; Ino Suryana; Erick Paulus
    Permasalahan jalur terpendek (Shortest Path Problem) merupakan salah satu topik permasalahan matematika yang paling popular dalam menjadi topik penelitian. Permasalahan jalur terpendek merupakan bagaimana suatu algoritma dapat menemukan jalur terpendek yang harus ditempuh dalam sebuah peta berjalur (graf) dari titik awal menuju titik akhir yang telah ditentukan. Algoritma Dijkstra dan A* merupakan algoritma pencarian jalur terpendek yang sampai saat ini masih umum digunakan. Kedua algoritma tersebut memiliki cara kerja pencarian jalur terpendek yang hampir sama, dengan tahap pengerjaan yang cukup sederhana. Ketika dihadapkan pada graf yang sederhana, kinerja algoritma Dijkstra dan A* cenderung sama. Namun, jika dihadapkan kepada graf yang besar dan memiliki banyak kemungkinan jalur yang dapat diambil, kinerja kedua algoritma tersebut akan berbeda. Graf yang memiliki jalur-jalur yang rumit salah satu contohnya adalah sebuah labirin. Labirin dapat memiliki banyak kemungkinan jalur yang dapat diambil dengan ukuran dan kondisi jalur yang tidak memiliki batasan, seperti lalu lintas, arah jalur, keadaan jalur, dan batasan lainnya. Penelitian ini dilakukan untuk mengetahui kinerja algoritma Dijkstra dan A* dalam menentukan jalur keluar terpendek pada berbagai labirin. Terdapat 12 labirin berukuran 512 x 512 sel yang diuji coba untuk mencari jalur keluar terpendek. Pada penelitian, dikembangkan sebuah perangkat lunak untuk melakukan uji coba algoritma Dijkstra dan A* dalam mencari jalur terpendek pada setiap labirin. Berdasarkan penelitian, algoritma Dijkstra cenderung memiliki kinerja yang lebih buruk dibandingkan algoritma A* dengan perbandingan waktu proses pencarian 1,95:1. Hal ini disebabkan oleh proses kerja algoritma Dijkstra yang melakukan pengecekan terhadap seluruh kemungkinan jalur, berbeda dengan algoritma A* yang melakukan pengecekan jalur secara terarah menuju titik akhir (titik tujuan).
  • No Thumbnail Available
    Item
    Perbandingan Algoritma Knuth Morris Pratt dan Boyer Moore dalam Pencarian String pada File Teks Berbasis Android
    (2018-09-04) MOHAMMAD GHIFARI YUSUF; Akik Hidayat; Ino Suryana
    Pencarian string di dalam teks disebut juga dengan pencocokan string (string matching atau pattern matching), permasalahan pencarian string adalah untuk mencari beberapa karakter atau pattern dalam sejumlah besar teks. Contoh permasalahan yang dihadapi adalah dalam aplikasi text editor seperti Microsoft Word atau Notepad, dan dalam lingkup yang lebih besar lagi adalah pencarian di internet yang dilakukan oleh mesin pencari seperti Google, Yahoo!, dan Bing. Algoritma Knuth Morris Pratt merupakan algoritma yang menggunakan metode alami, yaitu pencarian string dari arah kiri ke kanan. Sedangkan, algoritma Boyer Moore merupakan algoritma yang melakukan pencarian string dari arah kanan ke kiri. Penelitian ini dilakukan untuk mengetahui perbandingan algoritma Knuth Morris Pratt dan Boyer Moore dalam melakukan pencarian string pada file teks. Ada 5 file teks berjenis txt yang diuji coba untuk mencari 3 pattern yang berbeda. Pada penelitian, dikembangkan sebuah aplikasi berbasis Android untuk melakukan uji coba algoritma Knuth Morris Pratt dan Boyer Moore dalam mencari pattern tersebut pada setiap file teks. Berdasarkan penelitian, algoritma Boyer Moore lebih efisien dibanding algoritma Knuth Morris Pratt dengan perbandingan efisiensi algoritmanya adalah 2,9:1 iterasi per milidetik.