Vorlesung Textalgorithmen

Wintersemester 2006/07

Lehrbeauftragter:	Dr. Ralf Stiebe
Semester:	10
Wochenstunden:	4+0+0
Zuhörerkreis:	Hauptstudium Informatik, Ingenieurinformatik, Computervisualistik
Voraussetzungen:	Einführung in Algorithmen und Datenstrukturen, Theoretische Informatik (speziell Endliche Automaten)

mündliche Prüfung mit oder ohne Note

Exakte Suche nach einem Wort
(Knuth-Morris-Pratt-Algorithmus, Boyer-Moore-Algorithmus, Vishkins Duell-Algorithmus, Shift-And-Algorithmus, Karp-Rabin-Algorithmus)
Neben der Präsentation der Algorithmen stehen ihre Korrektheitsbeweise sowie Laufzeitanalysen im Mittelpunkt.
Suche nach Mengen von Wörtern
(Suchwort-Bäume [Tries], Aho-Corasick-Algorithmus, Shift-And-Algorithmus für Mengen, Wu-Manber-Algorithmus)
Außerdem wird kurz auf weitere Anwendungen von Tries (Wörterbücher, LZW-Kompression) eingegangen.
Inexakte Suche
Es werden der auf Dynamischer Programmierung beruhende Algorithmus zum Vergleich zweier Zeichenketten und einige Varianten betrachtet. Speziell untersucht wird die Suche nach Vorkommen mit höchstens k Fehlern.
Index-Strukturen (Suffixbäume und Suffix-Arrays)
Diese Datenstrukturen sind geeignet, einen großen Text so zu speichern (zu indexieren), dass man jedes Suchwort sehr schnell findet. Es geht um Algorithmen zur effizienten Konstruktion von Suffixbäumen und Suffix-Arrays sowie um die Anwendungen dieser Datenstrukturen.

Skript, zunächst aus einer früheren Vorlesung
Dan Gusfield, Algorithms on Strings, Trees, and Sequences. Cambridge University Press, New York, 1997.
Gonzalo Navarro and Mathieu Raffinot, Flexible Pattern Matching in Strings. Cambridge University Press, New York, 2002.
Alberto Apostolico and Zvi Galil, Pattern Matching Algorithms. Oxford University Press, New York, 1997.
Maxime Crochemore and Thierry Lecroq, Pattern Matching and Text Compression Algorithms. Chapter 8 of The Computer Science and Engineering Handbook edited by Allen B. Tucker, CRC Press, 2003.
verschiedene Originalarbeiten

Serie 1 (Termin: 25.10.2006)
Serie 2 (Termin: 15.11.2006)
Serie 3 (Termin: 29.11.2006)
Serie 4 (Termin: 13.12.2006)
Serie 5 (Termin: 22.1.2007)

Homepage von Thierry Lecroq, u.a. mit zahlreichen Animationen
- zur exakten Suche
- und zur inexakten Suche
und einer umfangreichen Bibliographie
Textsuch-Algorithmen von H.W. Lang (FH Flensburg)
Skripte zur Bioinformatik von Volker Heun (LMU München), mit einer grundlegenden Einführung in die Problemstellungen der Bioinformatik und Anwendungen von Textalgorithmen

Last modified: Wed Jan 31 12:51:24 MEZ 2007