Automaty ve vyhledávání v textech

Přednášející:

Ondřej Guth (gar.), Tomáš Pecka, Štěpán Plachý, Radomír Polách, Jan Trávníček, Jan Žďárek

Cvičící:

Ondřej Guth (gar.), Tomáš Pecka, Štěpán Plachý, Radomír Polách, Jan Trávníček, Jan Žďárek

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ů a dále ve stromech za použití automatů stromových. 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) a ve stromech.

Požadavky:

Znalost základů teorie formálních jazyků a konečných automatů.

Osnova přednášek:

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í. Nedeterministické konečné automaty jako modely pro sousměrné vyhledávání v textu.

2. Simulace vyhledávacích automatů, bitový paralelismus, dynamické programování.

3. Deterministické vyhledávací automaty a jejich složitost.

4. Konstrukce prefixových a sufixových automatů. Konstrukce faktorových automatů, faktor a sufix oracle automatů. Hledání hranic a period v textu. Hledání přesných a přibližných repetic v textu.

5. Vyhledávání pravidelností textových řetězců pomocí automatů pro indexování.

6. Konečné automaty a zobecněné řetězce: indexování, pravidelnosti.

7. Protisměrné vyhledávání v textu.

8. Třídy deterministických a nedeterministických zásobníkových automatů, determinizace zásobníkových automatů.

9. Stromové automaty.

10. Vyhledávání a indexování ve stromech, nelineární vzorky.

11. Stromové regulární výrazy.

Osnova cvičení:

Cíle studia:

Předmět se zabývá automatovými modely algoritmů vyhledávání v textu a ve stromech. 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ími formálními systémy, které jsou pro popis algoritmů použity, jsou konečné automaty pro algoritmy nad textem a stromové automaty pro algoritmy nad stromy. Znalosti z tohoto předmětu lze uplatnit při analýze a návrhu algoritmů vyhledávání v textu a ve stromech.

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:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/MI-AVY

Další informace:

https://courses.fit.cvut.cz/MI-AVY

Rozvrh na zimní semestr 2020/2021:

Rozvrh není připraven

Rozvrh na letní semestr 2020/2021:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Znalostní inženýrství, verze 2016 a 2017 (volitelný předmět)
• Počítačové systémy a sítě, verze 2016 až 2019 (volitelný předmět)
• Návrh a programování vestavných systémů, verze 2016 až 2019 (volitelný předmět)
• Zaměření Informační systémy a management, verze 2016 až 2019 (volitelný předmět)
• Zaměření Softwarové inženýrství, verze 2016 až 2019 (volitelný předmět)
• Zaměření Webové inženýrství, verze 2016 až 2019 (volitelný předmět)
• Společný magisterský plán před přiřazením do oboru, verze 2016 až 2019 (VO)
• Zaměření Systémové programování, verze 2016 až 2019 (volitelný předmět)
• Zaměření Teoretická informatika, verze 2016-2017 (povinný předmět zaměření)
• Znalostní inženýrství, verze 2018 to 2019 (volitelný předmět)