Das Ziel eines Proseminar ist einerseits die vertieften inhaltlichen Auseinandersetzung mit einem Thema. Andererseits dient ein Proseminar aber auch dazu, die Fähigkeiten im Ausarbeiten und Halten von Vorträgen zu verbessern, und wir werden versuchen, Sie dabei zu unterstützen. Dazu gehören aus aktuellem Anlass auch die Grundlagen wissenschaftlichen Arbeitens, beispielsweise das korrekte Zitieren.
Die Verarbeitung von Texten hat in der Informatik eine lange Tradition. Waren es zu Anfang vor allem Algorithmen zur schnellen Suche in (kurzen) Texten und beim Bearbeiten von Texten (z.B. in den bekannten Programmen grep, awk, emacs, vi) und zur Kompression (compress und zip), so gewinnt zunehmend die Verarbeitung riesiger unstrukturierter Textmengen (oder Datenmengen) an Bedeutung. Einige wichtige Beispiele sind Volltextsuchmaschinen für das Internet und Indizierung von Genomdaten.
Desweiteren gibt es Anwendungen in der Theorie der formalen Sprachen, beim Übersetzerbau, bei der Implementierung von Programmiersprachen, bei Multimedia Systemen und bei der Bildverarbeitung.
Das wohl grundlegendste Problem in der Textverarbeitung ist das Suchproblem (Pattern Matching), in dem es darum geht, zu entscheiden ob, wo und wie oft ein Muster in einem Text vorkommt.
In diesem Seminar werden verschiedene Algorithmen zur Lösung dieses Problems betrachtet, die Stärken in unterschiedlichen Anwendungen haben. Wir beginnen mit der einfachen linearen Suche, betrachten die Suche nach mehreren Mustern und die durch Vorverarbeitung des Textes (Indizierung) beschleunigte Suche. Anschließend betrachten wir noch Ansätze zur fehlertoleranten Suche, Textkompression und Suche in Bildern.
Es wird auf eine klare Darstellung der Probleme und Algorithmen Wert gelegt, wobei auch die Analyse (Korrektheit und Laufzeit) berücksichtigt werden soll.