Automaty ve vyhledávání v textech
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
MI-AVY | Z,ZK | 4 | 2+1 | česky |
- Přednášející:
- Bořivoj Melichar (gar.)
- Cvičící:
- Ondřej Guth
- Předmět zajišťuje:
- katedra teoretické informatiky
- Anotace:
-
Studenti získají znalosti algoritmů vyhledávání v textu za použití konečných automatů. Seznámí se s taxonomií vyhledávacích problémů a naučí se principy konstrukce automatů pro řešení těchto problémů. Získané znalosti budou schopni uplatnit při návrhu aplikací zabývajících se vyhledáváním v textu (např. DNA sekvence, datové proudy).
- Požadavky:
-
Znalost základů teorie formálních jazyků a překladů a konečných automatů.
- Osnova přednášek:
-
1. Textové systémy, základní pojmy, klasifikace vyhledávacích problémů.
2. Sousměrné vyhledávání, modely vyhledávacích algoritmů.
3. Nedeterministické vyhledávací automaty.
4. Simulace nedeterministických vyhledávacích automatů, bitový paralelismus, dynamické programování.
5. Prefixové a suffixové automaty.
6. Faktorové automaty, factor oracle, suffix oracle.
7. Hranice a periody v textu.
8. Repetice v textu, přesné a přibližné.
9. Simulace nedeterministických vyhledávacích automatů, fail funkce, MP a KMP algoritmy.
10. Simulace nedeterministických vyhledávacích algoritmů, fail funkce, AC algoritmus.
11. Protisměrné vyhledávání jednoho vzorku, BM algoritmus, CW algoritmus.
12. Aktuální výsledky v oblasti vyhledávání v textu (např. vyhledávání ve vícerozměrném textu, vyhledávání v komprimovaném textu).
- Osnova cvičení:
-
1. Konečné automaty, základní operace s konečnými automaty. Formulace základních vyhledávacích problémů pro přesné a přibližné vyhledávání.
2. Nedeterministické konečné automaty jako modely pro vyhledávání v textu. Deterministické vyhledávací automaty a jejich složitost.
3. Simulace vyhledávacích automatů, bitový paralelismus, dynamické programování. Simulace vyhledávacích automatů, MP a KMP algoritmy. Simulace vyhledávacích algoritmů, AC algoritmus.
4. Konstrukce prefixových a sufixových automatů. Konstrukce faktorových automatů, faktor a sufix oracle automatů.
5. Hledání hranic a period v textu. Hledání přesných a přibližných repetic v textu.
6. Protisměrné vyhledávání, BM algoritmus. Protisměrné vyhledávání, CW algoritmus.
- Cíle studia:
-
Předmět se zabývá automatovými modely algoritmů vyhledávání v textu. Hlavními tématy je vyhledávání vzorků a opakujících se částí textu. V obou případech se jedná jak o přesné vyhledávání, tak o přibližné vyhledávání. Hlavním formálním systémem, který je pro popis algoritmů použit, jsou konečné automaty. Znalosti z tohoto předmětu lze uplatnit při analýze a návrhu algoritmů vyhledávání v textu.
- Studijní materiály:
-
Melichar, B., Holub, J., Polcar, T. ''Text searching algorithms''. Volume I and II, Lecture notes. Prague, CTU, 2008.
Melichar, B., et al. ''Text searching algorithms''. Seminars. Prague, CTU, 2008.
- Poznámka:
-
Rozsah=prednasky+proseminare+cviceni2p+1c, Prednasejici: prof. Ing. Bořivoj Melichar DrSc.
- Rozvrh na zimní semestr 2011/2012:
- Rozvrh není připraven
- Rozvrh na letní semestr 2011/2012:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po Út St Čt Pá - Předmět je součástí následujících studijních plánů:
-
- Zaměření Teoretická informatika - verze pro ty, kteří se zapsali v roce 2010 (povinný předmět zaměření)
- Zaměření Teoretická informatika - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět zaměření)
- Zaměření Teoretická informatika - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět zaměření)