|
|
|
|
|
Algorithmen für die Verarbeitung von Texten haben eine lange Geschichte in der Informatik.
Probleme, in denen Texte verarbeitet werden müssen, tauchen nicht nur im Zusammenhang mit Textverarbeitungssystemen (z.B. den bekannten UNIX-Programmen grep, awk, emacs, vi, compress und zip) auf, sondern kommen in Bereichen wie der Theorie der formalen Sprachen, beim Übersetzerbau, bei der Implementierung von Programmiersprachen, bei Volltextdatenbanken, bei Multimedia Systemen, der Bildverarbeitung und der Bioinformatik vor - insbesondere die Bioinformatik hat in den letzten Jahren zu einem erneuerten Forschungsinteresse an Textalgorithmen geführt.
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. Im Seminar werden verschiedene Variationen von Algorithmen zur Lösung dieses Problems betrachtet (exact, approximate; off-line, on-line). Dazu kommen Algorithmen zur Analyse und zum Vergleich von Texten (Symmetrien in Texten, "Edit Distance", Unifikation) und Algorithmen zur Textkomprimierung.
Es wird auf eine klare Darstellung der Probleme und Algorithmen Wert gelegt, wobei auch die Analyse (Korrektheit und Laufzeit) berücksichtigt werden soll. Die zwei letzten Seminarthemen befassen sich mit anspruchsvolleren Analysen des Suchalgorithmus von Boyer-Moore und sind deshalb mit einem Stern gekennzeichnet.
Die meisten Themen stammen aus dem Buch "`Text Algorithms"' von Maxime Crochemore und Wojciech Rytter, Kapitel 1 und 2 dieses Buches geben eine gute Übersicht und führen in das Thema ein.
|
Merkblatt zur Gestaltung eines Seminarvortrags. (Die Tips auf diesem Merkblatt sind keine offiziellen Anforderungen oder Bewertungskriterien der TU München, sondern aus der Praxis eines Seminarleiters heraus entstandene Ratschläge.) |
Weitere Auskünfte und Anmeldungen bei Martin Raab, Jesper Larsson Träff.