Textalgorithmen
Fachbereich Angewandte Informatik	Vorlesung im SS 2002
	Dozent: Peter Becker

Die Vorlesung findet um 10:45 Uhr im C175 statt!

Vorlesungsankündigung

Unterlagen zur Vorlesung

• Folien zu den Kapitel:

  Vorbemerkungen (vierseitig)

  1. Suche von Mustern
     • Algorithmus von Knuth, Morris und Pratt (vierseitig)
     • Algorithmus von Boyer und Moore (vierseitig)
     • Analyse Boyer/Moore (vierseitig)

     • Animation der Algorithmen von Knuth, Morris und Pratt und von Boyer und Moore:
       • lokal
       • Original von Dieter Bühler (Universität Tübingen)

  2. Suffix-Bäume
     • Positionsbäume (vierseitig)
     • Konstruktion von Positionsbäumen (vierseitig)
     • Suffix-Bäume (vierseitig)

  3. Reguläre Ausdrücke und approximative Mustersuche
     • Matching regulärer Ausdrücke (vierseitig)
     • Approximatives Matching (vierseitig)

  4. Lexikalische Analyse und Parsing
     • Lexikalische Analyse (vierseitig)
     • Parsing (vierseitig)

  5. XML und Analyse von XML-Dokumenten
     • XML, Parsing von XML-Dokumenten (vierseitig)

  6. Textkompression
     • Verfahren zur Textkompression (vierseitig)

• Skript komplett (vierseitg)

• Übungen
  • Blatt 1 (15.04.2002)
  • Blatt 2 (29.04.2002)
    • RFC 1421
    • Zufälliger Text
    • Berechnung der Shift-Tabelle: C, Java

  • Blatt 3 (16.05.2002) Java-Programm zum Matching von String-Permutationen in linearer Zeit
  • Blatt 4 (03.06.2002)
  • Blatt 5 (11.06.2002)
  • Blatt 6 (19.06.2002)

  • Selbsttest NEU!

Literatur

Software

Sonstiges