Fakultät für Informatik der Technischen Universität München,
Lehrstuhl für Theoretische Informatik und Grundlagen der KI


Hauptseminar im WS 2002/03

Pattern-Matching- und Textalgorithmen

(Brauer, Csirik, Holzer, Kiehn, König, Römer, Rossmanith)






Vorbesprechung: Dienstag, den 16.07.2002, 13:00 Uhr im Raum 1546 (Hauptgebäude an der Seite Theresienstraße).
Die Anmeldung zum Seminar und die Themenvergabe erfolgt erst bei der Vorbesprechung! Voranmeldungen werden nicht angenommen.

Seminar-Termin: Dienstags 14:00-16:00 Uhr, Raum 03.09.014.
Die beiden zusätzlichen Vorträge an Donnerstagen (31.10. und 7.11.) finden von 10:00-12:00 Uhr statt.


Kontaktpersonen: Barbara König, Peter Rossmanith


Inhalt

Dieses Seminar beschäftigt sich mit folgenden wichtigen Algorithmen auf Texten und Zeichenfolgen: dem Suchen von Zeichenfolgen in Texten und dem Messen von Ähnlichkeiten. Dabei werden verschiedene Algorithmen aus der Literatur betrachtet. Ziel des Seminars ist es, die Verfahren vorzustellen, in ihrer Laufzeit zu analysieren und miteinander zu vergleichen. Ein Interesse an theoretischen Fragestellungen wird von den Seminarteilnehmern erwartet. Gute Kenntnis des Stoffs der Vorlesung "Einführung in die Informatik IV" wird vorausgesetzt.

Vortragsthemen

Die den einzelnen Themen zugrundeliegende Literatur ist weiter unten auf dieser Seite angegeben.

  Datum Thema Vortragende/r Betreuung
     String-Matching    
  1 29.10.2002 Boyer-Moore [Gus 2.2] Thomas Hellwig Astrid Kiehn
  2 31.10.2002 Knuth-Morris-Pratt [Gus 2.3] Sebastian Stratbücker Astrid Kiehn
  3 5.11.2002 Seminumerical String Matching [Gus 4.4] Zhao Chen Astrid Kiehn
  4 7.11.2002 Approximate String Matching [AG 6.1] Dagmar Beyer Astrid Kiehn
     Suffix-Bäume    
  5 12.11.2002 Einführung in Suffix-Bäme [Gus 5] Shasha Meng Barbara König
  6 19.11.2002 Ukkonens Algorithmus [Gus 6.1] Florian Ruf Barbara König
  7 26.11.2002 Weiners Algorithmus [Gus 6.2] Daniel Stahr Barbara König
  8 3.12.2002 McCreights Algorithmus [Gus 6.3] Milko Izamski Barbara König
     Shortest Common Superstrings    
  9 10.12.2002 NP-Vollständigkeit [AG 8.1.1,8.1.2(,8.1.3),8.4] Stefan Wasner Markus Holzer
  10 17.12.2002 Approximationsalgorithmen [AG 8.3] Andreas Vogl Markus Holzer
  11 7.1.2003 Negative Strings [AG 8.5] Jing Li Markus Holzer
     Levenshtein Distance    
  12 14.1.2003 Klassische Algorithmen [AG 4.1,4.2,4.3.1] Michael Braun Peter Rossmanith
  13 21.1.2003 Subquadratischer Algorithmus [AG 4.3.2,4.3.3] Ling Xu Peter Rossmanith
  14 28.1.2003 Parametrisierte Algorithmen (Teil I) [AG 4.4.1,4.4.2] Michael Petter Peter Rossmanith
  15 5.2.2003 Parametrisierte Algorithmen (Teil II) [AG 4.4.3,4.4.4] Natalia Mahlke Peter Rossmanith


Literatur



Hinweise


Barbara König
Last modified: Fri Feb 7 09:27:38 MET 2003