Ausgewählte Kapitel der Algorithmik und Theorie - String-Algorithmen

08 07230 Ausgewählte Kapitel der Algorithmik und Theorie - String-Algorithmen

2 St. [T:1,P:1],
Do 10.00-11.30, SE III
Albert J., Tischler G.

08 07240 Übungen hierzu
2 St., Mi 15-17, SE I
Albert J., Tischler G.

Vorläufiges Inhaltsverzeichnis

1. Tools
   1. Strings and automata
   2. Combinatorics
   3. Implementation of automata
   4. Basic pattern matching
2. Pattern matching automata
   1. Tries
   2. Searching for a single string
   3. Searching for multiple strings
3. Searching with a sliding window
4. Suffix arrays
   1. Searching
   2. Construction
   3. Longest common prefix table
5. Index structures
   1. Suffix tries
   2. Suffix trees
6. Alignments
   1. Edit distance
   2. Longest common subsequence
7. Regular expression matching
8. Succinct indexes

Literatur:

• M. Crochemore, C. Hancart, T. Lecroq: Algorithms on Strings (Cambridge University Press, 2007)
• D. Gusfield: Algorithms on Strings, Trees and Sequences (Cambridge University Press, 1997)

Die Textbücher zur Vorlesung liegen ausschließlich in Englisch vor, Vorlesungssprache ist jedoch Deutsch.

Die  Folien zur Vorlesung und die Übungsblätter gibt es auf WueCampus.