Důkaz - Složitost Aho-Corasick
- Ellrohir
- Matfyz(ák|ačka) level III
- Příspěvky: 140
- Registrován: 21. 12. 2007 13:29
- Typ studia: Informatika Bc.
- Login do SIS: secka7am
- Bydliště: Praha
- Kontaktovat uživatele:
Důkaz - Složitost Aho-Corasick
mohl by mi někdo poradit, kde najdu srozumnitelně (a nejlépe česky - anglicky sice rozumím dobře, ale učit se v aj mi moc nejde) vysvětlený důkaz složitosti algoritmu Aho-Corasick? protože Kučera nemá v textech k algovizi vůbec nic a Marešovy skripta tam je cosi o násobení polynomů, což nějak nechápu jak souvisí s AC...
Re: Důkaz - Složitost Aho-Corasick
V zapiskoch z Maresovej prednasky ( http://mj.ucw.cz/vyuka/0708/ads2/ads2.ps ) to myslim je.
Btw ten dokaz zlozitosti prace interpreteru spociva v tom, ze si uvedomis, ze na to, aby si k-krat zavolal funkciu fail musis najprv k-krat zavolat funkciu g, pretoze g ta v automate posuva o hladinu dalej od stavu 0, naopak fail ta posuva aspon o jednu hladinu blizsie k stavu 0. Inymi slovami celkovy pocet zavolani fail je mensi rovny celkovemu poctu zavolani g. No a g sa vola vola pre kazdy nacitany znak raz => celkovo sa vola m-krat ( kde m je velkost prehladavaneho textu ).
Snad som to nedoplietol
Btw ten dokaz zlozitosti prace interpreteru spociva v tom, ze si uvedomis, ze na to, aby si k-krat zavolal funkciu fail musis najprv k-krat zavolat funkciu g, pretoze g ta v automate posuva o hladinu dalej od stavu 0, naopak fail ta posuva aspon o jednu hladinu blizsie k stavu 0. Inymi slovami celkovy pocet zavolani fail je mensi rovny celkovemu poctu zavolani g. No a g sa vola vola pre kazdy nacitany znak raz => celkovo sa vola m-krat ( kde m je velkost prehladavaneho textu ).
Snad som to nedoplietol
-
- Matfyz(ák|ačka) level I
- Příspěvky: 15
- Registrován: 18. 3. 2008 19:36
- Typ studia: Informatika Bc.
- Login do SIS: krysj7am
Re: Důkaz - Složitost Aho-Corasick
Ahaaa, tak takhle to je. Diky za tip.
Re: Důkaz - Složitost Aho-Corasick
Selsky duKaz: Kdyz lezes na strom (i opakovane), spadnes nanejvys z te vysky kam jsi vylezl.