Claim Missing Document
Check
Articles

Found 1 Documents
Search
Journal : Sainstek

ANALISIS EDIT DISTANCE MENGGUNAKAN ALGORITMA DYNAMIC PROGRAMMING Mulyanto, Arip
Sainstek Vol 5, No 2, 2010
Publisher : Sainstek

Show Abstract | Download Original | Original Source | Check in Google Scholar | Full PDF (48.228 KB)

Abstract

Edit distance merupakan jumlah minimum point mutation yang diperlukan untuk merubah suatu string ke string yang lain. Point mutation tersebut adalah mengganti, menambah dan menghapus sebuah karakter. Konsep edit distance banyak digunakan dalam proses manipulasi data berbagai aplikasi komputer. Berbagai algoritma dapat digunakan dalam pencarian dan penentuan edit distance. Dalam penelitian ini, dilakukan eksperimen untuk mencari edit distance menggunakan algoritma dynamic programming. Sedangkan proses perhitungannya dibantu dengan fungsi-fungsi yang ada dalam Microsoft Excel. Hasil eksperimen menunjukkan kompleksitas waktu (time complexity) untuk algoritma dynamic programming adalah O(|s1|*|s2|). Jika s1 dan s2 mempunyai panjang yang hampir sama, katakanlah n, maka kompleksitas waktunya adalah O(n2). Kompleksitas ruang (spacecomplexity) untuk algoritma ini juga O(n 2), karena keseluruhan dari matriks digunakan untuk menemukan solusi yang optimal. Kata kunci : edit distance, dynamic programming, kompleksitas.
Co-Authors Abas Kaluku Abdillah, Tajjudin Abdul Aziz Bouty Abdul Rahman Syah Daud Abdul Rifai Saputra Lakita Abuna, Greyis Agus Lahinta Ahmad Azhar Kadim Alfian Zakaria Amir, Ramiza Andre Alfri Pua Apriyati Rahmi Pateda Pateda Arfan Utiarahman Bait Syaiful Rijal Budiyanto Ahaliki Dai, Roviana H. Deisy Almafira Rantung Delvia Anwar Dian Novian Dukalang, Herdin H. Dunggio, Mahmud Septian Dwinanto, Arif Edi Setiawan Eka Vickraien Dangkua, Eka Vickraien Fadly Achmad Gaib, Rukli Prasetya Galang Leoni Yagri MS Punu Gani, Abdul Wahid Gani, Hilmansyah Halusa, Dewi Hemila, Hemila Hermila A Huzaima Mas’ud Ibrahim, Salmawati Idham Halid Lahay Indah Wardati Indhitya R Padiku Ismail Daud, Ismail Jemmy A Pakaya Lanto Ningrayati Amali Lillyan Hadjaratie Maemunah M mamonto, fara humaira Manda Rohandi Mashuri, Muh Fahrial Masi, Muhammad Ali Mas’ud, Huzaima Moh Ramdhan Arif Kaluku Moh. Hidayat Koniyo mohammad syafri tuloli Muchlis Polin Mukhlisulfatih Latief Muthia Muthia Muthia, Muthia Narce, Novia Ngabito, Musdalifah Dwi Putri Nikmasari Pakaya Nugraha, Bariq Pakaja, Jemmy A Pakaya, Jemmy A Pakaya, Nikmasari palada, sri widya Pangestu, Wahyu Adji Panu, Mohamad Fiqriansyah Pateda, Apriyati Rahmi Pateda Poloka, Asriyanti Pomalo, Nurdian Rahman Takdir Rahmat Taufik R.L Bau Ramadan Nuryansah Haras Renaldo Hadji Rezkiawan Tantawi Rio Monoarfa Rusdiyanto Patuke S Supriyadi Salahudin Olii Siti Rahayu J. Ismail Sitti Suhada Sri Ayu Ashari Sunardi Sunardi Surya Handrisusanto Ahmad Suwandi, Ihsanulfu’ad Tajuddin Abdillah Tegela, Nelly Tuloli, Mohomad Syafri Usman, Wahyu Setiawan Wulandari Adam Yassin, Rochmad M Thohir Yassin, Rochmad Mohammad Thohir