Předmět je základní jednotka výuky, jejímž prostřednictvím si student osvojí ucelenou část souboru znalostí a dovedností, potřebnou pro zvládnutí studijního oboru/specializace. Za věcný obsah předmětu zodpovídá garant předmětu. Časovou náročnost předmětu zhruba vyjadřuje atribut předmětu rozsah kontaktní výuky. Například rozsah = 2+2  značí, že předmět bude mít týdně dvě hodiny přednášek a dvě hodiny cvičení týdně. Na závěr semestru musí vyučující provést vyhodnocení, nakolik si ten který student osvojil poznatky a dovednosti, kterých měl během výuky nabýt. Jakým způsobem toto hodnocení vyučující provedou určuje atribut způsob zakončení. U předmětu lze definovat, že předmět je zakončen pouze zápočtem(Z), klasifikovaným zápočtem(KZ), pouze zkouškou(ZK), nebo zápočtem a zkouškou(Z,ZK). Náročnost úspěšného absolvování předmětu je vyjádřena ECTS kreditními body. Výuka předmětu probíhá během semestru. Opakovaně se předmět vyučuje vždy v zimním(Z), nebo v letním(L) semestru každého akademického roku. Výjimečně může předmět být nabízen studentům v obou semestrech(Z,L). Za organizační zajištění výuky zodpovídá přiřazená katedra, která zejména vytvoří časový rozvrh předmětu a zajistí pro předmět vyučující. Někteří přednáší a zkouší, jiní vedou cvičení a udělují zápočty.
Obsahová náplň a další organizační informace, týkající se předmětu je popsána pomocí různých popisných textů(anotace, týdenní osnova, literatura, apod.)
$DODATEK_POPIS

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ý).

Osnovy 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.

Osnovy 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.

Literatura:

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/

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ů.

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr MI-ZI.2016 Znalostní inženýrství V 2 MI-ZI.2018 Znalostní inženýrství V 2 MI-PSS.2016 Počítačové systémy a sítě V 2 MI-WSI-ISM.2016 Webové a softwarové inženýrství V 2 MI-SP-TI.2016 Systémové programování PZ 2 MI-WSI-WI.2016 Webové a softwarové inženýrství V 2 MI-WSI-SI.2016 Webové a softwarové inženýrství V 2 MI-SPOL.2016 Nespecifikovaný/á obor/specializace studia - Unspecified Branch/Specialisation of Study VO 2 MI-SP-SP.2016 Systémové programování V 2 MI-NPVS.2016 Návrh a programování vestavných systémů V 2 MI-WSI-ISM.2016 Webové a softwarové inženýrství V 2