Sehr geehrter Nutzer, sehr geehrte Nutzerin,
wir haben unseren Auftritt mit Techniken wie CSS barrierearm gestaltet. Leider unterstützt Ihr Browser diese Webstandards nicht komplett oder die Verwendung von Stylesheets ist ausgeschaltet.

Zur Navigation - Metanavigation überspringen |
Zum Inhalt - Navigation überspringen


Zusatznavigation

English Logo Leibniz Universität Hannover Kontakt Sitemap
Programmiersprachen und Übersetzer

PSUE  > Lehre > WiSe 2019/20 > Textalgorithmen

Textalgorithmen

Vorlesung

Dozent: Prof. Dr. Rainer Parchmann
Termin: Dienstag, 10.15 - 11.45 Uhr in Raum F 142 (Hauptgebäude)
Beginn: 15. Oktober 2019

Übung

Termin: Mittwoch, 12.15 - 13.45 Uhr in Raum F 142 (Hauptgebäude)
Beginn: 16. Oktober 2019

Vorlesungsinhalte

Diese Vorlesung wendet sich hauptsächlich an Studenten des Masterstudiengangs Informatik.

In dieser Vorlesung werden Algorithmen für die exakte Suche nach dem Auftreten eines Musters (pattern) in einer größeren Struktur (text) vorgestellt und analysiert werden. Zunächst einmal handelt es sich bei dem Muster und der größeren Struktur um einfache Zeichenketten, später werden Verallgemeinerungen auf 2-dimensionale Strukturen und Bäume betrachtet. Die behandelten Verfahren reichen dabei von einfacher Zeichenkettensuche, wie man sie etwa in einem Editor benötigt, bis zu komplexen Verfahren zum simultanen Suchen mehrerer gegebener Zeichenketten. Es sollen verschieden Formen der Vorverarbeitung des Suchmusters und des Textes und die daraus resultierenden Strukturen (Tries, Suffix-Bäume, DAWGs usw.) untersucht und mathematisch analysiert werden. Verfahren dieser Art sind besonders in der Textverarbeitung und in der Analyse von Gen–Sequenzen („Computational Biology“) wichtig.

Vorausgesetzt werden elementare Kenntnisse über Algorithmen und Datenstrukturen und deren Analyse sowie aus der theoretischen Informatik.

Inhalt der Vorlesung:

  • Einleitung
  • Zeichenketten
  • Suche nach einem Schlüsselwort
  • Simultane Suche nach mehreren Schlüsselwörtern
  • Tries
  • Suffixbäume
  • Gerichtete Azyklische Wort Graphen (DAWG)
  • Mustersuche in Bäumen

Materialien zur Vorlesung

Programmtexte, Beispielprogramme sowie Übungsaufgaben und weiteres Material werden über Stud.IP zur Verfügung gestellt.

Skript zur Vorlesung

Die einzelnen Kapitel des Skripts werden (in vorläufiger Version) mit den Folienkopien als pdf-Dateien im Stud.IP veröffentlicht. Das endgültige Skript zur Vorlesung wird am Ende der Vorlesung veröffentlicht.

Übungen zur Vorlesung

In einer der beiden Übungsstunden werden zum einen die wöchentlich herausgegebenen Übungszettel besprochen. Die Übungszettel und eventuelle Lösungshinweise finden Sie im Ordner "Übungsblätter" zur Übung.

In der zweiten Übungsstunde werden Varianten der Algorithmen sowie größere Beispiele vorgestellt..

Abschluss der Vorlesung

Abschluss der Vorlesung ist eine mündliche Prüfung von ca. 30 Minuten Dauer.


Zusatzinformationen

Lehre im WiSe 2019/20


Fußzeile