Automaty ve vyhledávání v textech
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:
-
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ů:
-
- 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)