Stringalgorithmen (Vorlesung)

Thema

Stringalgorithmen

Vorlesungsinhalt

Eines der grundlegendsten Objekte in der Informatik ist die Zeichenkette (engl. "String"). Die gesamte Textverabreitung durch Computer basiert auf Zeichenketten, aber auch alle anderen Arten von Daten sind spätestens auf Maschinenebene als Sequenzen (von Bits) repräsentiert.
Als Stringalgorithmen bezeichnen wir Algorithmen die auf Strings als Eingabe arbeiten und Probleme lösen die speziell bei der Verarbeitung von Strings auftreten. Ein klassisches Beispiel für einen Stringalgorithmus ist das "Pattern Matching", d.h. das Aufspüren aller Vorkommen eines Wortes in einem größeren Text. Man kann sich leicht vorstellen, dass dieses Problem vielerlei praktische Anwendung findet. Das Pattern Matching lässt sich in der Tat mit solch grundlegenden Aufgaben wie dem Sortieren oder dem Berechnen arithmetischer Operationen vergleichen.

Durch die Verfügbarkeit großer Datenmengen hat das Pattern Matching, sowie andere Stringalgorithmen in den letzten Jahren noch an Bedeutung dazu gewonnen. Es ist in den Naturwissenschaften üblich auch Daten bei denen es nicht um Texte im klassischen Sinne handelt in Form von Strings darzustellen um so auf den Computer als Analysewerkzeug zurückgreifen zu können. Zum Beispiel wird das Erbgut von Lebewesen normalerweise vereinfacht als sehr lange Zeichenkette dargestellt.

Wir werden Algorithmen für das Pattern Matching sowie andere grundlegende Stringalgorithmen kennen lernen. Aufgrund der hohen praktischen Relevanz von Stringalgorithmen werden wir nicht nur die Korrektheit der Algorithmen sondern auch ihre zeit- und platzeffiziente Implementierung ins Auge fassen.

Teilnahmevoraussetzungen

Sie sollten die Grundvorlesungen aus den ersten Semestern Informatik erfolgreich besucht haben.

Insbesondere ist es hilfreich ein Grundverständnis der Automaten- und Algorithmentheorie zu haben.