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

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ý, Jan Trávníček, Jan Žďárek
Cvičící:
Ondřej Guth (gar.), Tomáš Pecka, Štěpán Plachý, Jan Trávníček, Jan Žďárek
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:

Vyhledávání v textu (obecně v datech) je oblastí problémů a jejich řešení zajímavých z teoretického i praktického hlediska. Data mohou být pro hledání chápána jako jednorozměrná (text) nebo vícerozměrná (strom, obrázek). Vyhledávat lze něco předem daného (konkrétní řetězec, množinu určenou např. regulárním výrazem) či neznámého (např. pravidelnost), hledat lze přesně či přibližně. Předmět přináší ucelený pohled na problémy vyhledávání (taxonomii) a zaměřuje se na algoritmy, jejichž základním výpočetním modelem je automat (konečný, zásobníkový, lineárně omezený nebo stromový).

Požadavky:

Znalost základů teorie formálních jazyků a algoritmů nad konečnými automaty na úrovni probírané v předmětu BI-AAG. Konkrétně jde o Chomského hierarchii jazyků, podmnožinovou konstrukci a odstranění epsilon-přechodů.

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ý automat jako model pro vyhledávání v textu.

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

3. Automaty pro indexování. Hledání hranic a period v textu. Hledání přesných a přibližných repetic v textu.

4. Vyhledávání dalších pravidelností textových řetězců (pokrytí a jader) pomocí automatů pro indexování.

5. Vyhledávání s regulárními výrazy. Rozšíření o zpětné reference.

6. Synchronizující konečné automaty a optimální paralelní algoritmy nad konečnými automaty.

7. Lokálně testovatelné jazyky.

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

9. Stromové automaty, základní operace se stromovými automaty, porovnání s konečnými automaty.

10. Vyhledávání a indexování ve stromech se zásobníkovými a stromovými automaty, nelineární vzorky.

11. Kombinatorické vyhledávání a indexování vícerozměrného textu (algoritmy nad acyklickými grafy).

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

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í. Nedeterministický konečný automat jako model pro vyhledávání v textu.

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

3. Automaty pro indexování. Hledání hranic a period v textu. Hledání přesných a přibližných repetic v textu.

4. Vyhledávání dalších pravidelností textových řetězců (pokrytí a jader) pomocí automatů pro indexování.

5. Vyhledávání s regulárními výrazy. Rozšíření o zpětné reference.

6. Synchronizující konečné automaty a optimální paralelní algoritmy nad konečnými automaty.

7. Lokálně testovatelné jazyky.

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

9. Stromové automaty, základní operace se stromovými automaty, porovnání s konečnými automaty.

10. Vyhledávání a indexování ve stromech se zásobníkovými a stromovými automaty, nelineární vzorky.

11. Kombinatorické vyhledávání a indexování vícerozměrného textu (algoritmy nad acyklickými grafy).

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

Cíle studia:

Studenti získají znalosti algoritmů vyhledávání v textu, stromech a obrázcích za použití konečných, zásobníkových, lineárně omezených a stromový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), v obrázcích a ve stromech.

Studijní materiály:

1. Melichar, B.; Holub, J.; Polcar, T. Text Searching Algorithms. Volume I: Forward String Matching. Dostupné z: https://psc.fit.cvut.cz/athens/TextSearchingAlgorithms/

2. Aho, A. V. Algorithms for Finding Patterns in Strings. In Handbook of Theoretical Computer Science, Algorithms and Complexity, 255-300. Elsevier, 1990. ISBN 9780444880710. DOI: 10.1016/B978-0-444-88071-0.50010-2.

3. Alur, R.; Madhusudan P. Visibly pushdown languages. In Proc. 36th Int. ACM Symposium on Theory of Computing (STOC), 2004.

4. Van Tang, N. A tighter bound for the determinization of visibly pushdown automata. In 11th International Workshop on Verification of Infinite-State Systems, INFINITY 2009, 2009.

5. Nowotka, D.; Srba J. Height-Deterministic Pushdown Automata. In 32nd International Symposium on Mathematical Foundations of Computer Science, MFCS'07, 2007.

6. Černý, J. Poznámka k homogénnym experimentom s konečnými automatmi. Matematicko-fyzikálny časopis Slovenskej Akadémie Vied, 14: 208-216. Dostupné z: https://dml.cz/handle/10338.dmlcz/126647

7. Pin, JE. On two combinatorial problems arising from automata theory. Combinatorial mathematics (Marseille-Luminy, 1981), 1983, Marseille-Luminy, pp.535-548. Dostupné z: https://hal.archives-ouvertes.fr/hal-00143937

8. Holub, J.; Štekr, S. Implementation of deterministic finite automata on parallel computers. Colloquium and Festschrift at the occasion of the 60th birthday of Derrick Kourie (Computer Science), Windy Brow, South Africa, 28 June 2008. Dostupné z: http://hdl.handle.net/2263/9145

9. Yechezkel, Z. Locally testable languages. Journal of Computer and System Sciences 6, 151-167 (1972). Dostupné z: https://doi.org/10.1016/S0022-0000(72)80020-5

10. James, R.; Dakotah, L. Extracting Forbidden Factors from Regular Stringsets. Proceedings of the 15th Meeting on the Mathematics of Language, 2017, London, pp.36-46. Dostupné z: https://www.aclweb.org/anthology/W17-3404/

Poznámka:

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

Další informace:
https://courses.fit.cvut.cz/MI-AVY
Rozvrh na zimní semestr 2021/2022:
Rozvrh není připraven
Rozvrh na letní semestr 2021/2022:
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:347
Guth O.
Trávníček J.

11:00–12:30
(přednášková par. 1)
Dejvice
NBFIT učebna
místnost T9:347
Plachý Š.
Pecka T.

12:45–13:30
(přednášková par. 1
paralelka 101)

Dejvice
NBFIT učebna
St
Čt

Předmět je součástí následujících studijních plánů:
Platnost dat k 19. 8. 2022
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1433406.html