INI BELAJAR

-
KULIAH IWWW BELAJAR BLOGSPOT.

Komentar

Posting Komentar

Postingan populer dari blog ini

~ AHO-CORASICK ALGORITHM ~

-
Gambar
Algoritma Aho-Corasick Dalam ilmu komputer , algoritma Aho-Corasick adalah algoritma pencarian string yang ditemukan oleh Alfred V. Aho dan Margaret J. Corasick. [1] Ini adalah sejenis algoritma pencocokan kamus yang menempatkan elemen dari serangkaian string terbatas ("kamus") dalam teks masukan. Ini cocok dengan semua senar secara bersamaan. Kompleksitas algoritma linier di sepanjang senar ditambah panjang teks yang dicari ditambah jumlah output yang sesuai. Perhatikan bahwa karena semua kecocokan ditemukan, ada jumlah kuadrat dari kecocokan jika setiap pertandingan substring (misalnya kamus = a , aa , aaa , aaaa dan string masukan adalah aaaa ). Secara informal, algoritma ini membangun sebuah mesin negara yang terbatas yang menyerupai sebuah trie dengan tambahan link antara berbagai node internal. Tautan internal tambahan ini memungkinkan transisi yang cepat antara korespondensi string yang gagal (misalnya pencarian kucing dalam trie...
Baca selengkapnya

~ Algoritma Edmonds-Karp ~

-
Gambar
Dalam ilmu komputer , algoritma Edmonds-Karp adalah implementasi metode Ford-Fulkerson untuk menghitung aliran maksimum dalam jaringan arus pada waktu O ( V E 2 ). Algoritma ini pertama kali diterbitkan oleh Yefim Dinitz pada tahun 1970  dan diterbitkan secara independen oleh Jack Edmonds dan Richard Karp pada tahun 1972. [3] Algoritma Dinic mencakup teknik tambahan yang mengurangi waktu berjalan ke O ( V 2 E ). Algoritma Algoritma ini identik dengan algoritma Ford-Fulkerson , kecuali bahwa urutan pencarian saat menemukan jalan augmenting didefinisikan. Jalur yang ditemukan pastilah jalan terpendek yang memiliki kapasitas yang tersedia. Ini bisa ditemukan dengan pencarian yang luas , karena kita membiarkan tepi memiliki panjang satuan. Waktu berjalan O ( V E 2 ) ditemukan dengan menunjukkan bahwa setiap jalur augmenting dapat ditemukan pada waktu O ( E ), bahwa setiap kali setidaknya satu dari ujung E menjadi jenuh (tepi yang memiliki ar...
Baca selengkapnya

~ TOPOLOGICAL SORTING ~

-
Gambar
Di bidang ilmu komputer , semacam topologi atau urutan topologi dari graf berarah adalah urutan linear simpulnya sehingga untuk setiap tepi yang diarahkan uv dari simpul u ke simpul v , u datang sebelum v dalam pemesanan. Misalnya, simpul grafik dapat mewakili tugas yang harus dilakukan, dan ujung-ujungnya mungkin merupakan kendala yang harus dilakukan satu tugas sebelum yang lain; Dalam aplikasi ini, pemesanan topologi hanyalah urutan yang valid untuk tugas. Pemesanan topologis dimungkinkan jika dan hanya jika grafik tidak memiliki siklus terarah , yaitu jika merupakan grafik asiklik terarah (DAG). Setiap DAG memiliki paling sedikit satu pemesanan topologi, dan algoritma dikenal untuk menyusun urutan topologi setiap DAG dalam waktu linier . Contoh Aplikasi penyortiran topologi kanonik adalah penjadwalan urutan pekerjaan atau tugas berdasarkan ketergantungan mereka. Pekerjaan diwakili oleh simpul, dan ada tepi dari x ke y jika pekerjaan x harus ...
Baca selengkapnya