Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Efficient Text Pattern Matching

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
MIE-EVY.16 Z,ZK 5 2P+1C
Přednášející:
Jan Holub (gar.), Radomír Polách
Cvičící:
Radomír Polách
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:

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.

Požadavky:
Osnova přednášek:

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.

Osnova cvičení:

1. Basic definitions.

2. Text full index

3. Exact pattern matching algorithms.

4. FFT in pattern matching.

5. Succinct data structure

6. FM-Index, approximate pattern matching.

Cíle studia:

The pattern matching is a key task in most applications. Its importance is increasing with enlargement of the mass of information collected. Efficient algorithms and data structures for pattern matching are therefore crucial in information processing, but also in other fields like security (e.g., intrusion detection, virus scans). This module provides an extensive overview of such algorithms and data structures.

Studijní materiály:

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

Poznámka:

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

Další informace:
https://courses.fit.cvut.cz/MIE-EVY/
Rozvrh na zimní semestr 2019/2020:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
místnost TH:A-1247
Holub J.
09:15–10:45
(přednášková par. 1)
Thákurova 7 (FSv-budova A)
seminární místnost
Út
místnost T9:301
Polách R.
09:15–10:45
LICHÝ TÝDEN

(přednášková par. 1
paralelka 101)

Dejvice
NBFIT učebna
St
Čt

Rozvrh na letní semestr 2019/2020:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 15. 9. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet4658006.html