Stringologie

(Dr. Peter Leupold)

(3 Std. Vorlesung, 1 Std. Übung)


Vorlesung:Dienstag18-20 Uhrim Raum -1319
Donnerstag16-17 Uhrim Raum 1332
Übung:Donnerstag17-18 Uhrim Raum 1332
Beginn: Dienstag, den 26.10.2010, 18.15 Uhr

Inhalt

Eine der einfachsten und zugleich meistbenutzten Datenstrukturen ist der String, d.h. eine Kette von Zeichen. Im Allgemeinen ist es relativ einfach, Standardoperationen für Strings effizient zu implementieren. In den letzten Jahrzehnten wurden jedoch zunehmend stringförmig vorliegende Daten von enormer Größe produziert. Zum Beispiel ermöglicht es die weitgehende Automatisierung der Gensequenzierung, ganze Genome in kurzer Zeit zu lesen. Ebenso werden zunehmend Textkorpora digitalisiert, das Internet stellt einen Textkörper von gewaltiger Größe dar.

Bei der Suche in derart umgangreichen Texten kommen selbst sehr geringe Effizienzunterschiede in den Algorithmen zum Tragen. Die theoretisch optimalen Methoden sind nicht stets die besten in der Praxis, so dass sich Computerexperimente zur Auswahl empfehlen. Für verschiedene Arten von Daten (Sprache, DNA, zufällig verteilte Strings ...) sind unter Umständen verschiedene Lösungen optimal. Da häufig viele gleichartige Anfragen zu erwarten sind, lohnt sich häufig eine Vorverarbeitung zu höheren Datenstrukturen wie Suffix-Arrays. Mit diesen Problemstellungen beschäftigt sich die Stringologie.

Die Vorlesung stellt übliche Fragestellungen und entsprechende Lösungsansätze vor. Dazu werden zunächst einige kombinatorische Eigenschaften von Strings dargestellt, insbesondere zur Periodizität. Anschließend werden Standardmethoden zur Lösung elementarer Informationssuchaufgaben behandelt, die sodann verfeinert werden. Schließlich werden noch ausgewälte, besonders interessante Ergebnisse aus der Stringologie vorgestellt.

Literatur

Crochemore, M.; Hancart, C. & Lecroq, T.:
Algorithms on Strings
Cambridge University Press, 2007.
Crochemore, M. & Rytter, W.:
Jewels of Stringology
World Scientific, 2003.

Angesprochener Hörerkreis:

Vorkenntnisse/Voraussetzungen:

Verständnis einer prozeduralen Programmiersprache (Pseudocode), Endliche Automaten.
Zulassungsvoraussetzungen zum Master gemäß Prüfungsordnung.

Leistungsnachweis:

Mündliche Prüfung (ca. 30 Min) nach erfolgreicher Teilnahme an den Übungen