Stringology

Lecturer:

Bořivoj Melichar (gar.)

Tutor:

Bořivoj Melichar (gar.)

Supervisor:

Department of Computer Science

Synopsis:

Algorithms for processing and searching in text.

Algorithms presented on the basis of finite automata as models of computation.

Principles of processing compressed text and parallel algorithms

Requirements:

Syllabus of lectures:

1. General principles of processing and searching in text.

2. Finite automata as a basic model of computation for text algorithms.

3. Finite automata as indexing tools.

4. Searching regularities in text (repetitions, periods, borders,.).

5. Methods based on simulation of finite automata.

6. Pattern matching in compressed text.

7. Parallel methods in stringology.

8. Searching for the longest common factor and subsequence in a set of strings.

9. String cover, superstring construction.

10. Use of text algorithms for more complex data structures (trees, matrices,.)

Syllabus of tutorials:

Study Objective:

The goal of the module is to present methods of construction of string processing algorithms. The construction is based on theory of finite automata. There are hundreds of tasks that are classified into many classes. For each class of tasks, a construction of appropriate algorithms is presented.

Study materials:

1. Crochemore, M., Rytter, W.: Jewels of stringology. World Scientific Publishing, 2003.

2. Melichar, B., Holub, J. Polcar, T.: Text searching algorithms. Available on: http://www.stringology.org/athens/, 2005.

Note:

Time-table for winter semester 2011/2012:

Time-table is not available yet

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans:

• Informatics (VO)