Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2020/2021

Automaty ve vyhledávání v textech

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
MI-AVY Z,ZK 4 2P+1C česky
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ů:
Platnost dat k 30. 10. 2020
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1433406.html