Automaty ve vyhledávání v textech

Přednášející:

Ondřej Guth (gar.), Bořivoj Melichar (gar.)

Cvičící:

Ondřej Guth (gar.)

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

Rozvrh na zimní semestr 2018/2019:

Rozvrh není připraven

Rozvrh na letní semestr 2018/2019:

	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	místnost T9:302 Guth O. 16:15–17:45 (přednášková par. 1) Dejvice NBFIT učebnamístnost T9:302 Guth O. 18:00–18:45 (přednášková par. 1 paralelka 101) Dejvice NBFIT učebna
St
Čt
Pá

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

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