LTI
LTI

Proseminar: String Matching

  • Leitung:
    PD Dr. Hanjo Täubig
  • Modul: IN0013,
  • Bereich:
    2 SWS Proseminar im Bereich Informatik III (Theoretische Informatik)
  • Anmeldung:
    Die Anmeldung erfolgt über TUMonline oder alternativ per Mail an den Seminarleiter (Hanjo Täubig, taeubig@in.tum.de).
  • Zeit:
    Das Proseminar wird als Blockveranstaltung in 2 Blöcken abgehalten:
    • Mittwoch 14.12.2016 14-20 Uhr (MI 03.11.018)
    • Samstag 21.01.2017 10-16 Uhr (MI 03.11.018)
    Der Seminarraum 03.11.018 ist dienstags 14-16 Uhr für die Proseminar-Teilnehmer reserviert. Hier können die Teilnehmer gemeinsam an den Folien und Ausarbeitungen arbeiten und mit dem Seminarleiter die dabei auftretenden Probleme diskutieren.
  • Schein:
    Einen Seminarschein erhält, wer einen Vortrag gehalten, eine Ausarbeitung geschrieben und regelmäßig aktiv am Seminar teilgenommen hat.
  • Hörerkreis:
    Studierende im Grundstudium der Informatik
    Studierende im Bachelorstudiengang Informatik
    Studierende mit Nebenfach Informatik
  • Voraussetzungen:
    Voraussetzung für die Teilnahme am Proseminar sind neben Interesse an Algorithmen, auch Englischkenntnisse, die ausreichend für die Bearbeitung der überwiegend englischsprachigen Literatur sein müssen.

Zusammenfassung

Das Ziel eines Proseminar ist einerseits die vertieften inhaltlichen Auseinandersetzung mit einem Thema. Andererseits dient ein Proseminar aber auch dazu, die Fähigkeiten im Ausarbeiten und Halten von Vorträgen zu verbessern, und wir werden versuchen, Sie dabei zu unterstützen. Dazu gehören aus aktuellem Anlass auch die Grundlagen wissenschaftlichen Arbeitens, beispielsweise das korrekte Zitieren.

Die Verarbeitung von Texten hat in der Informatik eine lange Tradition. Waren es zu Anfang vor allem Algorithmen zur schnellen Suche in (kurzen) Texten und beim Bearbeiten von Texten (z.B. in den bekannten Programmen grep, awk, emacs, vi) und zur Kompression (compress und zip), so gewinnt zunehmend die Verarbeitung riesiger unstrukturierter Textmengen (oder Datenmengen) an Bedeutung. Einige wichtige Beispiele sind Volltextsuchmaschinen für das Internet und Indizierung von Genomdaten.

Desweiteren gibt es Anwendungen in der Theorie der formalen Sprachen, beim Übersetzerbau, bei der Implementierung von Programmiersprachen, bei Multimedia Systemen und bei der Bildverarbeitung.

Das wohl grundlegendste Problem in der Textverarbeitung ist das Suchproblem (Pattern Matching), in dem es darum geht, zu entscheiden ob, wo und wie oft ein Muster in einem Text vorkommt.

In diesem Seminar werden verschiedene Algorithmen zur Lösung dieses Problems betrachtet, die Stärken in unterschiedlichen Anwendungen haben. Wir beginnen mit der einfachen linearen Suche, betrachten die Suche nach mehreren Mustern und die durch Vorverarbeitung des Textes (Indizierung) beschleunigte Suche. Anschließend betrachten wir noch Ansätze zur fehlertoleranten Suche, Textkompression und Suche in Bildern.

Es wird auf eine klare Darstellung der Probleme und Algorithmen Wert gelegt, wobei auch die Analyse (Korrektheit und Laufzeit) berücksichtigt werden soll.

Mögliche Themen

  1. Knuth-Morris-Pratt Algorithmus
  2. Boyer-Moore Algorithmus
  3. Karp-Rabin Fingerprint-Methode
  4. Aho-Corasick-Algorithmus (ggf. mit regulären Ausdrücken)
  5. Tries und PATRICIA Trees
  6. Suffix Trees (Algorithmus von Ukkonen)
  7. Directed Acyclic Word Graphs (DAWGs)
  8. Suffix Arrays (Einführung und Algorithmus von Manber und Myers)
  9. Suffix Arrays (Ein Algorithmus mit linearer Laufzeit von Kärkkäinen und Sanders)
  10. Edit-Distanz (Levenshtein-Distanz) und Longest Common Subsequence
  11. Globale Alignments, Needleman-Wunsch-Algorithmus
  12. Semiglobale und lokale Alignments, Allgemeine/Affine/Konkave Lückenstrafen
  13. Multiple Sequence Alignment, Fragment Assembly

Themenverteilung

  • 1. Termin (14.12.2016)
    • Knuth-Morris-Pratt Algorithmus
      Moschino Breuer
    • Boyer-Moore Algorithmus
      Arnold Bitner
    • Karp-Rabin Fingerprint-Methode
      Paul Kehnel
    • Aho-Corasick-Algorithmus (ggf. mit regulären Ausdrücken)
      Julian Litti
    • Tries und PATRICIA Trees, Directed Acyclic Word Graphs (DAWGs)
      Tobias Weber
    • Suffix Trees (Algorithmus von Weiner oder McCreight)
      Hans Rauer
  • 2. Termin (21.01.2017)
    • Suffix Trees (Algorithmus von Ukkonen)
      Christian Smutek
    • Suffix Arrays (Einführung und Algorithmus von Manber und Myers)
      Ethan Tatlow
    • Suffix Arrays (Ein Algorithmus mit linearer Laufzeit von Kärkkäinen und Sanders)
      Christian Backs
    • Edit-Distanz (Levenshtein-Distanz) und Longest Common Subsequence
      Anton Luckhardt
    • Globale Alignments, Needleman-Wunsch-Algorithmus
      Ke Shui

Literatur

  • Dan Gusfield:
    Algorithms on Strings, Trees, and Sequences (Computer Science and Computational Biology)
    Cambridge University Press, 1997.

Hinweise

Vorbereitung
Jeder Studierende wählt ein Thema, sucht sich relevante Literatur und verschafft sich einen Überblick über das Thema. Anschließend wird der Entwurf der Präsentation erstellt, dies beinhaltet beispielsweise das Erstellen der Folien und die Planung des Tafelbilds.
Vorbesprechung
Spätestens zwei Wochen vor dem Vortragstermin wird der Entwurf des Vortrags mit dem Betreuer besprochen. Dazu vereinbart jeder Studierende rechtzeitig einen Termin. Zu diesem Zeitpunkt muss auch mindestens die Gliederung der Ausarbeitung vorliegen.
Seminarvortrag
Der Seminarvortrag soll ca. 45(±5) Minuten dauern. Vortrag und Folien können auf deutsch oder englisch gehalten bzw. verfasst werden. Nach dem Vortrag hat das Publikum die Möglichkeit, Fragen zu stellen. Eine LaTeX-Vorlage für die Präsentation findet sich in diesem Ordner. Eine Powerpoint-Vorlage kann man auf der Seite vom TUM Corporate Design herunterladen (Login mit MyTUM-Kennung). Diese Vorlagen müssen nicht verwendet werden oder können bei Bedarf auch angepasst werden.
Seminararbeit
Die Seminararbeit ist mit Hilfe von LaTeX zu erstellen. Die Endfassung der Seminarbeit ist als PDF-Datei abzugeben. (Das PDF File kann z.B. mit pdflatex erstellt werden.) Der Umfang der Seminararbeit beträgt 6 ± 1 Seiten (ohne Abbildungen, Inhalts- und Literaturverzeichnis).


Anwesenheit
Jeder Studierende muss bei allen Vorträgen anwesend sein und sich aktiv an der Diskussion beteiligen.

Gute Vorträge

Hinweise zum Vorbereiten und Halten guter Präsentationen:
  • Hilfreiche Hinweise zur Vorbereitung, zum Erstellen der Folien und zum eigentlichen Vortrag geben Garr Reynolds' presentation tips.
  • Einige sehr wichtige Aspekte guter Vorträge sind auch im Beamer User Guide in Kapitel I.5 Guidelines for Creating Presentations beschrieben.
  • Die Fokussierung auf eine wichtige Nachricht wird in der kurzen Präsentation Rethinking Presentation Design betont.
  • Bei einigen Themen bietet es sich möglicherweise an, den Algorithmus in einer kurzen Live-Demonstration vorzuführen (z.B. per Java-Applet).
Lehrstuhl für Algorithmen und Komplexität
Prof. Dr. Susanne Albers

Boltzmannstr. 3
85748 Garching bei München

Tel +89.289.17706
Fax +89.289.17707

E-Mail