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:
Studenti získají znalosti efektivních algoritmů vyhledávání v textových informacích. Naučí se pracovat s tzv. zhuštěnými datovými strukturami, které vynikají jak rychlostí přístupu tak úsporou místa v paměti. Získané znalosti budou schopni uplatnit při návrhu aplikací zabývajících se vyhledáváním v textu.

Osnovy přednášek:

1.		Úvod, základní definice, border array.
2.		Úplné indexování textu: Suffix array.
3.		Úplné indexování textu: Suffix tree, konstrukce LCP.
4.		Úplné indexování textu: factor, suffix automata, on-line konstrukce.
5.		Algoritmy přesného vyhledávání.
6.		FFT ve vyhledávání.
7.		Succinct data structure: metody rank & select.
8.		Succinct data structure: wavelet tree.
9.		FM-Index.
10.		Reprezentace slovníku, kontrola pravopisu.
11.		Přibližné vyhledávání.
12.		Vyhledávání v bioinformatice a v muzikologii.
13.		Vyhledávání v bioinformatice a v muzikologii.

Osnovy cvičení:

1.		Základní pojmy.
2.		Úplné indexování textu
3.		Algoritmy přesného vyhledávání.
4.		FFT ve vyhledávání
5.		Succinct data structure
6.		FM-Index, přibližné vyhledávání.

Literatura:

W.		F. Smyth: ''Computing Patterns in Strings'', Pearson Addison Wesley (UK), 2003, 423 pp. ISBN-10: 0201398397
M.		Crochemore, W. Rytter: ''Jewels of Stringology''. World Scientific Publishing Company, 2003. ISBN-10: 9810248970.
G.		Navarro, M. Raffinot: ''Flexible Pattern Matching in Strings''. Cambridge University Press, 2008. ISBN-10: 0521039932.
M.		Crochemore, C. Hancart, T. Lecroq: ''Algorithms on Strings''. Cambridge University Press, 2007. ISBN-10: 0521848997

Požadavky:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/MI-EVY/

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

Plán Obor Role Dop. semestr NI-TI.2018 Teoretická informatika PS Není MI-SP-SP.2016 Systémové programování PZ 1