|
|
|
||
Last update: Hladíková Jana (05.01.2018)
|
|
||
Last update: Hladíková Jana (05.01.2018)
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. |
|
||
Last update: Svozil Daniel prof. Mgr. Ph.D. (04.11.2018)
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
|
|
||
Last update: Hladíková Jana (05.01.2018)
https://edux.fit.cvut.cz/courses/MI-EVY/ (login necessary) |
|
||
Last update: Hladíková Jana (05.01.2018)
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. |
|
||
Last update: Svozil Daniel prof. Mgr. Ph.D. (08.02.2018)
Automata and grammars |
|
||
Last update: Svozil Daniel prof. Mgr. Ph.D. (07.02.2018)
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. |
Teaching methods | ||||
Activity | Credits | Hours | ||
Účast na přednáškách | 1 | 28 | ||
Příprava na přednášky, semináře, laboratoře, exkurzi nebo praxi | 1 | 28 | ||
Příprava na zkoušku a její absolvování | 1.5 | 42 | ||
Účast na seminářích | 0.5 | 14 | ||
4 / 4 | 112 / 112 |