Klassische Stringalgorithmik
Modulnummer: W06-10
Englischer Titel: Algorithms on Strings
Leistungspunkte: 6
Lehrperson: Schmid
Empfohlene Vorkenntnisse
Grundkenntnisse in Theoretischer Informatik, insbesondere Algorithmen und Datenstrukturen, Formale Sprachen und Automatentheorie, Komplexität (wie in den Veranstaltungen "Einführung in die Theoretische Informatik" und "Algorithmen und Datenstrukturen" vermittelt).
Zwingende Voraussetzungen
keine
Inhalt
Die Zeichenkette ist eines der grundlegendsten Objekte in der Informatik zur Repräsentation von Daten oder Information (in der Literatur sind auch die Begriffe Wort, Text, Dokument oder Sequenz üblich; wir verwenden hauptsächlich den englischen Begriff "String", welcher in der praktischen Informatik auch als Bezeichnung eines grundlegenden Datentyps gebräuchlich ist). Beispielsweise werden Textdokumente in natürlicher Sprache, aber auch wissenschaftliche Daten wie Biosequenzen in der Informatik als Strings behandelt. Im Gegensatz zu Bäumen, Graphen oder anderen noch komplexeren Datenstrukturen (beispielsweise relationale Daten), haben Strings eine sehr einfache, lineare Struktur: Es gibt einen Anfang und ein Ende, und jedes Element des Strings besitzt einen wohldefinierten Vorgänger (außer das Startsymbol) und einen wohldefinierten Nachfolger (außer das Endsymbol). Viele grundlegende Berechnungsprobleme zur Textanalyse lassen sich effizient lösen (bspw. Patternmatching) und die Informatik hat dazu in den letzten 50 Jahren viele effiziente Algorithmen (sowie spezielle Datenstrukturen und kombinatorische Resultate) entwickelt.
Dieser Kurs ist eine Einführung in das Gebiet der Stringalgorithmen (auch ``Stringology'' genannt). Hauptziel der Veranstaltung ist es, einige klassische Stringalgorithmen, sowie relevante kombinatorische Resultate und grundlegende Datenstrukturen kennen zu lernen. Wir werden uns hauptsächlich auf theoretische Resultate beschränken (Worst-Case Laufzeitanalysen, Korrektheitsbeweise, untere Komplexitätsschranken), aber auch klassische Anwendungsgebiete der behandelten Algorithmen kennen lernen.
Erforderliche Arbeitsleistungen für LP-Vergabe und Prüfungszulassung
- aktive Teilnahme
Lehrveranstaltungen
Vorlesung: 3 SWS [[3 LP, MAP 1 LP]]
Übung: 1 SWS [[2 LP]]
Forschungsorientiert
nein
Angeboten für Studiengänge
Monobachelor: ja
Kombinationsbachelor: ja
Infomit: ja
Angeboten im
Wintersemester: nein
Sommersemester: nein
Turnus
Unregelmäßig