Proseminar Pattern Matching

  Sommersemester 2012
 Dozent: Frank Hoffmann

 Impressum

<Aktuell | Allgemein | Schein | Termine >

Stand 05.03. : Unten finden Sie die vorläufige Vortragsliste.
Stand 02.04. : Die schon vergebenen Themen sind unten vermerkt.
Stand 15.06. : Der Termin am 19.06. fällt leider wegen organisatorischer
                      Problem kurzfristig aus, die beiden Vorträge werden wie auch die
                      zwei letzten Termine um eine Woche verschoben!!!
         

< Aktuell | Allgemein | Schein| Termine >


Inhalt

Im Proseminar werden Standardthemen zum Pattern Matching vorgestellt. Alles zusammen umfassen diese in etwa den Umfang einer 2-stündigen
1-semestrigen Vorlesung zum Thema.
Neben den fachlichen Aspekten werden wir besonders auf Fragen einer ansprechenden Präsentation Wert legen
und diese auch nach jedem Vortag kritisch analysieren.

Literatur:

         Dan Gusfield, Algorithms on Strings, Trees and Sequences,Cambridge University Press 1997
         
         Volker Heun:  Skriptum zur Vorlesung Algorithmen und Sequenzen (München 2007/08) 
         
         Linear Work Suffix Array Construction" von J. Kärkkäinen, P. Sanders, S. Burkhardt (JACM Vol.53/6, 918-936)

Es sollen natürlich auch eigenständige Literaturrecherchen durchgeführt werden.

Hinweise zum Vortrag:
         Hoffmann, Knauer, Wie gestalte ich einen Seminarvortrag ? pdf-file
         I. Parberry,  How to Present a Paper in Theoretical Computer Science: A Speaker's Guide for Students.

Vortragsthemen und Vortragende:   ( mit gefühlter Schwierigkeit 1=leicht, 3=etwas anspruchsvoller)   
  1. Klassische Pattern Matching Algorithmen (1) (Kairies)
  2. Der Aho-Corasick-Algorithmus (1) (Dobmann)
  3. Matching gegen reguläre Ausdrücke (1) (Wienhold)
  4. Seminumerisches String Matching: die Shift-And-Methode und Karp-Rabin's-Fingerprint  (2) (Makus))
  5. Suffixbäume I: Einführung und erste Anwendungen (1) (Bohlen)
  6. Suffixbäume II: Linearzeitkonstruktion nach Ukkonen (2 Vorträge) (3) (Hoffmann)
  7. Suffixbäume III: Anwendungen mit lca-Anfragen (2) (Adfeldt)
  8. Linearzeit-Vorverarbeitung für lca-Anfragen (3) (Kostulski)
  9. Suffixarrays: Einführung und Anwendungen (2) (Röhrig)
  10. Suffixarrays in linearer Zeit konstruieren (3) (offen)
  11. Suffixbäume und Ziv-Lempel-Kompression (2) (Krakowczyk)
  12. Dyn. Programmieren I: Editierabstand (1) (Förster)
  13. Dyn. Programmieren II: Globales und lokales Alignment  (1) (Pannwitz)
  14. Hirschbergs Algorithmus (DP mit linearem Speicher) (2) (Yüksel)
  15. Der 4-Russen-Trick (Subquadratisches DP) (3) (Mullins)
  16. Suffixbäume und Dynamisches Programmieren (2) (Petzold)
  17. Das Shortest-Superstring-Problem (3) (Husse)

< Aktuell | Allgemein | Schein| Termine >


Für den Scheinerhalt muss

Die Note richtet sich nach Form und Inhalt des Vortrags und der Ausarbeitung.

< Aktuell | Allgemein | Schein | Termine>

 Die Seminare finden Di 16-18 Uhr im Seminarraum 053 Takustr. 9 statt. Wir fangen 16 Uhr s.t. an. Pro Termin wird es zwei Vorträge geben.

Termin
 Themen
 Vortragende
     Ausarbeitung
10.04.
 Organisatorisches
 Hoffmann
08.05.
 1+2
 Kairies/Dobmann
15.05.
 3+4
 entfällt/Makus
22.05.
 5+7
 Bohlen/Adfeldt
29.05.
 6
 Hoffmann
05.06.
 9
 ---/Röhrig
12.06.
 11+8
 Krakowczyk/Kostulski
 26.06.
           12+13
    Förster/Pannwitz
 03.07.
           14+15
     Yüksel/Mullins
 10.07.
           16+17
     Petzold/Husse


Sprechzeit des Dozenten: Mittwochs 14 - 15,  Zi. 115 bzw. nach Vereinbarung




Probleme mit der Webseite? (ausser Farbbeschwerden ;-) -> hoffmann[at]inf.fu-berlin.de