Automata in Text Pattern Matching

Přednášející:

Bořivoj Melichar (gar.)

Cvičící:

Ondřej Guth

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Students learn algorithms for searching in texts using finite automata. They become acquainted with the searching problems taxonomy and learn the principles of automata constructions for solving these problems. They will be able to apply the gained knowledge in the design of applications required text pattern matching, such as data streaming, DNA sequencing, etc.

Požadavky:

Basics of formal language theory, language translations, and finite automata.

Osnova přednášek:

1. Text systems, basic notions, taxonomy of text pattern matching problems.

2. Forward pattern matching, models of searching algorithms.

3. Nondeterministic search automata.

4. Simulation of nondeterministic search automata, bit parallelism, dynamic programming.

5. Prefix and suffix automata.

6. Factor automata, factor oracle, suffix oracle.

7. Borders and periods in texts.

8. Repetitions in texts, exact and approximate.

9. Simulation of nondeterministic search automata, fail function, the MP a KMP algorithms.

10. Simulation of nondeterministic search automata, fail function, the AC algorithm.

11. Backward single pattern matching, the BM algorithm, the CW algorithm.

12. State-of-the-art in text pattern matching (e.g., matching in a multidimensional text, searching in a compressed text).

Osnova cvičení:

1. Finite automata, basic operations with finite automata. Taxonomy of pattern matching problems for exact and approximate matching.

2. Nondeterministic search finite automata. Deterministic search finite automata and their complexity.

3. Simulation of nondeterministic search finite automata, bit parallelism, dynamic programming, MP & KMP algorithms, AC algorithm.

4. Construction of prefix and suffix automata. Construction of factor automata, factor & suffix oracles.

5. Computation of borders and periods of text. Searching exact and approximate repetitions in text.

6. Backward pattern matching - BM & CW algorithms.

Cíle studia:

The module deals with automata models of algorithms for text searching. The main topics are text pattern matching and repetitions. In both cases, both exact and inexact pattern matchings are considered. The fundamental formal tool for description of the algorithms is the finite automaton. The knowledge gained in this module can be applied in analysis and design of algorithms for text pattern matching.

Studijní materiály:

1. Melichar, B., Holub, J., Polcar, T. ''Text searching algorithms''. Volume I and II, Lecture notes. Prague, CTU, 2008.

2. Melichar, B., et al. ''Text searching algorithms''. Seminars. Prague, CTU, 2008.

Poznámka:

Rozsah=prednasky+proseminare+cviceni2p+1c, Prednasejici: prof. Ing. Bořivoj Melichar DrSc.

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

	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
Út	místnost T9:344 Melichar B. 11:00–12:30 (přednášková par. 1) Dejvice NBFIT ucebna
St
Čt
Pá	místnost T9:302 Guth O. 11:00–12:30 LICHÝ TÝDEN (přednášková par. 1 paralelka 101) Dejvice NBFIT učebna

Předmět je součástí následujících studijních plánů:

• Computer Science, Presented in English, Version for Students, who Enrolled in 2010 and 2011 (povinný předmět zaměření)
• Master Informatics, Presented in English - Version for Students who Enrolled in 2010 (VO)
• Master Informatics, Presented in English - Version for Students who Enrolled in 2011 (VO)
• Master Informatics, Presented in English - Version for Students who Enrolled in 2012 (VO)
• Computer Science, Presented in English - Version for Students who Enrolled in 2012 (povinný předmět zaměření)