Stringology
Code  Completion  Credits  Range 

PISTR  ZK  4  3C 
 Garant předmětu:
 Lecturer:
 Tutor:
 Supervisor:
 Department of Theoretical 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:
 Further information:
 No timetable has been prepared for this course
 The course is a part of the following study plans:

 Informatics (doctoral) (compulsory elective course)
 Informatics (compulsory elective course)