Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2024/2025

Stringology

The course is not on the list Without time-table
Code Completion Credits Range
PI-STR 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 time-table has been prepared for this course
The course is a part of the following study plans:
Data valid to 2024-04-21
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet1602106.html