Studenti budou umět:

budou mít znalosti efektivních algoritmů vyhledávání v textových informacích.

pracovat s tzv. zhuštěnými datovými strukturami, které vynikají jak rychlostí přístupu tak úsporou místa v paměti.

uplatnit získané znalosti při návrhu aplikací zabývajících se vyhledáváním v textu.

Students will be able to:

Understand pattern matching as a key task in most applications.

Understand efficient algorithms and data structures for pattern matching (not only in information processing, but also in other fields like security - intrusion detection, virus scans).

Have an extensive overview of such algorithms and data structures.

Pro zı́skánı́ zápočtu je potřeba dostatek bodů ze zápočtových testů. Zkouška se skládá z povinné pı́semné a povinné ústnı́ části.

Z: Pokorný J., Dokumentografické informační systémy, Karolinum, 2005, ISBN 80-246-1148-1

Z: M.Crochemore, C. Hancart, T. Lecroq: Algorithms on Strings. Cambridge University Press, 2014. ISBN-10: 1107670993

D: Melichar B., Textové informační systémy, Praha, 1994, ISBN 8001012069, 9788001012062

D: W.F. Smyth: Computing Patterns in Strings, Pearson Addison Wesley (UK), 2003, 423 pp. ISBN-10: 0201398397

D: M.Crochemore, W. Rytter: Jewels of Stringology. World Scientific Publishing Company, 2003. ISBN-10: 9810248970

D: G.Navarro, M. Raffinot: Flexible Pattern Matching in Strings. Cambridge University Press, 2008. ISBN-10: 0521039932

R: Pokorný J., Dokumentografické informační systémy, Karolinum, 2005, ISBN 80-246-1148-1

R: M.Crochemore, C. Hancart, T. Lecroq: Algorithms on Strings. Cambridge University Press, 2014. ISBN 1107670993

A: Melichar B., Textové informační systémy, Praha, 1994, ISBN 8001012069, 9788001012062

A: W.F. Smyth: Computing Patterns in Strings, Pearson Addison Wesley (UK), 2003, 423 pp. ISBN 0201398397

A: M.Crochemore, W. Rytter: Jewels of Stringology. World Scientific Publishing Company, 2003. ISBN 9810248970

A: G.Navarro, M. Raffinot: Flexible Pattern Matching in Strings. Cambridge University Press, 2008. ISBN 0521039932

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.

1. Introduction, basic definitions, border array.

2. Text full index: Suffix array.

3. Text full index: Suffix tree, LCP construction.

4. Text full index: Factor, suffix automata, on-line construction.

5. Exact pattern matching algorithms.

6. FFT in pattern matching.

7. Succinct data structure: rank & select.

8. Succinct data structure: wavelet tree.

9. FM-Index.

10. Dictionary representation, spell checking.

11. Approximate pattern matching.

12. Pattern matching in bioinformatics and musicology.

13. Pattern matching in bioinformatics and musicology.

https://edux.fit.cvut.cz/courses/MI-EVY/

(nutné přihlášení)

https://edux.fit.cvut.cz/courses/MI-EVY/

(login necessary)

Automaty a gramatiky

Automata and grammars