Algorithmen und Datenstrukturen
in der Stringverarbeitung,
CIS, Universität München, SS 2004

Hans Leiß, Johannes Goller

1  Vorlesung

  1. Literatur, Inhalt (Plan)
  2. Maschinenmodell, Speicher
  3. Suffix-Trie eines Texts
  4. Suffixbaum eines Texts (wird noch vervollständigt)
  5. Funktionale (verzögerte) Suffixbaumkonstruktion
  6. Der Wortgraph eines Texts (voräufig)
  7. Programmdokumentation zum Wortgraphen
  8. Lempel-Ziv-77- und Lempel-Ziv-78-Kompression
  9. Lempel-Ziv-Welch-Kompression
  10. Suche in LZ-78-komprimierten Zeichenreihen
  11. Multiset Discrimination (für Objekte vom Grundtyp)
  12. Multiset Discrimination (für Paare, Listen, Adressen)
  13. Bag/Set-Trennung, Schwaches Sortieren, Progamme

2  Literatur

Lehrbücher sind auf den ersten Vorlesungsfolien angegeben.
Spezialliteratur zu einzelnen Algorithmen folgt hier. (Leider ist das eine leere Ankündigung geblieben; manche Angaben sind auf den Folien.)
Zur Unterscheidung von Multimengen:
  1. F.Henglein's Seite dazu: http://www.plan-x.org/msd/
  2. Meine Darstellung/Programm: H.L.: Unterscheidung von Multimengen

3  Seminar (Implementierung)

3.1  Aufgaben

  1. Aufgabe 1 (Datentyp Trie und Suchfunktionen)
  2. Aufgabe 2 (Trie-Implementierung und Durchlaufen)
  3. Aufgabe 3 (Graphikausgabe der Konstruktion eines Suffixtries)
  4. Aufgabe 4 (Anwendungen und Varianten von Suffixtries)
  5. Beispiel zum Compilation-Manager von SML
  6. wordgraph.nw Programm+Doku(Anhang!) (LaTeX s. Kommentar in masterfile.tex)

3.2  Diskussionsforum

http://www.die-informatiker.net/viewforum.php?f=56

File translated from TEX by TTH, version 3.70.
On 29 Apr 2008, 14:32.