Poslední úprava: Jirát Jiří Ing. Ph.D. (09.01.2014)
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.
Poslední úprava: Jirát Jiří Ing. Ph.D. (09.01.2014)
Students get knowledge of efficient algorithms for text pattern matching. They learn to use so called succinct data structures that are efficient in both access time and memory complexity. They will be able to use the knowledge in design of applications that utilize pattern matching.
Výstupy studia předmětu -
Poslední úprava: Jirát Jiří Ing. Ph.D. (13.01.2014)
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.
Poslední úprava: Jirát Jiří Ing. Ph.D. (31.01.2014)
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.
Literatura -
Poslední úprava: Jirát Jiří Ing. Ph.D. (09.01.2014)
Z:W.F. Smyth: ''Computing Patterns in Strings'', Pearson Addison Wesley (UK), 2003, 423 pp. ISBN-10: 0201398397
Z:M.Crochemore, W. Rytter: ''Jewels of Stringology''. World Scientific Publishing Company, 2003. ISBN-10: 9810248970.
Z:G.Navarro, M. Raffinot: ''Flexible Pattern Matching in Strings''. Cambridge University Press, 2008. ISBN-10: 0521039932.
Z:M.Crochemore, C. Hancart, T. Lecroq: ''Algorithms on Strings''. Cambridge University Press, 2007. ISBN-10: 0521848997
Poslední úprava: Jirát Jiří Ing. Ph.D. (09.01.2014)
R:W.F. Smyth: ''Computing Patterns in Strings'', Pearson Addison Wesley (UK), 2003, 423 pp. ISBN-10: 0201398397
R:M.Crochemore, W. Rytter: ''Jewels of Stringology''. World Scientific Publishing Company, 2003. ISBN-10: 9810248970.
R:G.Navarro, M. Raffinot: ''Flexible Pattern Matching in Strings''. Cambridge University Press, 2008. ISBN-10: 0521039932.
R:M.Crochemore, C. Hancart, T. Lecroq: ''Algorithms on Strings''. Cambridge University Press, 2007. ISBN-10: 0521848997
Studijní opory -
Poslední úprava: Jirát Jiří Ing. Ph.D. (09.01.2014)
https://edux.fit.cvut.cz/courses/MI-EVY/
(nutné přihlášení)
Poslední úprava: Jirát Jiří Ing. Ph.D. (09.01.2014)
https://edux.fit.cvut.cz/courses/MI-EVY/
(login necessary)
Sylabus -
Poslední úprava: Jirát Jiří Ing. Ph.D. (09.01.2014)
1. Úvod, základní definice, border array.
2. Úplné indexování textu: Suffix array.
3. Úplné indexování textu: Suffix tree, konstrukce LCP.