LTI
LTI

Seminar: String Matching

  • Leitung:
    PD Dr. Hanjo Täubig
  • Modul: IN0014, IN2107
  • Bereich:
    2 SWS Seminar im Bereich Informatik III (Theoretische Informatik)
  • Anmeldung:
    Die Anmeldung erfolgt über das Matching Tool.
  • Zeit:
    Das Seminar wird als Blockveranstaltung abgehalten:
    • Samstag ??.??.2020 10-16 Uhr (MI 03.11.018)
    • Samstag ??.??.2020 10-16 Uhr (MI 03.11.018)
    Aufgrund der aktuellen Beschränkungen durch die COVID-19-Pandemie wird es keine Vorbesprechung geben. Die entsprechenden Informationen über die weitere Durchführung des Seminars werden in Kürze per eMail an alle (über das Matching Tool zugeordneten) Teilnehmer versandt.
  • Schein:
    Einen Seminarschein erhält, wer einen Vortrag gehalten, eine Ausarbeitung geschrieben und regelmäßig aktiv am Seminar teilgenommen hat.
  • Hörerkreis:
    Studierende im Bachelorstudiengang Informatik
    Studierende im Masterstudiengang Informatik
  • Voraussetzungen:
    Voraussetzung für die Teilnahme am Seminar sind neben Interesse an Algorithmen, auch Englischkenntnisse, die ausreichend für die Bearbeitung der überwiegend englischsprachigen Literatur sein müssen.

Zusammenfassung

Das Ziel eines Seminar ist einerseits die vertiefte inhaltliche Auseinandersetzung mit einem Thema. Andererseits dient ein Seminar aber auch dazu, die Fähigkeiten im Ausarbeiten und Halten von Vorträgen zu verbessern. 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 evt. noch Ansätze zur fehlertoleranten Suche oder Textkompression.

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, Boyer-Moore Algorithmus
  2. Aho-Corasick-Algorithmus (ggf. mit regulären Ausdrücken)
  3. Suffix Trees (Algorithmus von Ukkonen)
  4. Directed Acyclic Word Graphs (DAWGs)
  5. Suffix Arrays (Einführung und Algorithmus von Manber und Myers, Alg. von Ko und Aluru)
  6. Suffix Arrays (Ein Algorithmus mit linearer Laufzeit von Kärkkäinen und Sanders)
  7. Edit-Distanz (Levenshtein-Distanz), Longest Common Subsequence, Globale Alignments, Needleman-Wunsch-Algorithmus
  8. Semiglobale und lokale Alignments, Allgemeine/Affine/Konkave Lückenstrafen
  9. Multiple Sequence Alignment, Fragment Assembly
  10. Text Indexing with Errors
  11. Enhanced Suffix Arrays and Extended Suffix Arrays
  12. Compressed Indexing Structures / Burrows-Wheeler-Transformation und FM-Index
  13. Repeats

Themenverteilung

  • 1. Termin (??.??.2020)
    • Knuth-Morris-Pratt Algorithmus, Boyer-Moore Algorithmus
    • Aho-Corasick-Algorithmus (ggf. mit regulären Ausdrücken)
    • Suffix Trees (Algorithmus von Ukkonen)
    • Directed Acyclic Word Graphs (DAWGs)
    • Suffix Arrays (Einführung und Algorithmus von Manber und Myers, Alg. von Ko und Aluru)
    • Suffix Arrays (Linearzeit-Algorithmus von Kärkkäinen und Sanders)
  • 2. Termin (??.??.2020)
    • Text Indexing With Errors
    • Compressed Indexing Structures
    • Edit-Distanz (Levenshtein-Distanz), Longest Common Subsequence, Globale Alignments, Needleman-Wunsch-Algorithmus
    • Semiglobale und lokale Alignments, Allgemeine/Affine/Konkave Lückenstrafen
    • Multiple Sequence Alignment
    • Fragment Assembly

Literatur

Es wird erwartet, dass alle Teilnehmer/-innen eigenständig geeignete Literatur (Bücher, Journal-Artikel, Konferenzbeiträge, Manuskripte / Technische Berichte, Vorlesungsunterlagen, etc.) recherchieren. Folgende Bücher könnten dabei z.B. als Grundlage dienen:
  • 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. 60(±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 10 ± 2 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