Universität Bonn

Institut für Informatik V

Prof. Dr. N. Blum, M. Nikolaidou, C. Rick

Seminar: Combinatorial Pattern Matching
(SS 2000)

Beschreibung:

Entwurf und Analyse von Methoden zur Behandlung von Zeichenketten (Strings) haben sich in den letzten Jahren zu einem eigenständigen Teilgebiet der algorithmischen Forschung entwickelt. Dies ist u.a. auf das Sequenzierungsprojekt des menschlichen Genoms zurückzuführen. Aber auch zur Komprimierung von Daten oder zum Auffinden von Dokumenten werden laufend neue Verfahren benötigt.

Theoretische Ergebnisse - etwa über Symmetrien und Periodizität von Sequenzen - können zur Entwicklung effizienterer Algorithmen genutzt werden. Auf diese Weise lassen sich Theorie und Praxis in diesem Gebiet oft gut miteinander verbinden. Mittlerweile haben sich eine Reihe grundlegender Techniken und Datenstrukturen als sehr vielseitig einsetzbar erwiesen. Eine Auswahl davon soll in den Vorträgen des Seminars diskutiert werden.

Seminartermin:

jeweils Dientags, 16-18 Uhr, N102
verschoben auf Mittwochs, 13-15 Uhr, N102

Vorbesprechung:

Dienstag, 8. Februar 2000, 16 s.t., N102
Es sind noch Plätze frei!
Interessenten wenden sich bitte direkt an M. Nikolaidou (N105) oder C. Rick (N106).

Vortragsmodus:

Vortragsausarbeitung, Einzelvortrag

Bereich:

A/C

Voraussetzungen:

Vordiplomkenntnisse im Bereich Algorithmen und Datenstrukturen

Plätze:

12

Themenübersicht:

  1. Fundamental Preprocessing, Periodicity Lemma
  2. Boyer/Moore & Knuth/Morris/Pratt
  3. Linearity of Boyer/Moore
  4. Multi Pattern Matching (Aho/Corasick)
  5. Linear Construction of Suffix Trees
  6. Suffix Arrays
  7. Linear Time Lempel/Ziv
  8. Lowest Common Anchestors (LCA)
  9. Application of Suffix Tree & LCA
  10. Edit Distance
  11. Approximate String Matching
  12. Exclusion Methods

Literatur:

D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997

Tips zur Vorbereitung eines Seminarvortrags:

  1. Regeln speziell für unser Seminar
  2. Student Speakers Guide
Universität Bonn / Informatik / Abteilung V
08.02.2000 - rick@informatik.uni-bonn.de