Algorithmische Fragestellungen für komprimierte Daten (SS 2006)

Organisatorisches

• Dozent: Dr. Markus Lohrey (Raum 211, Email, Sprechstunde nach Vereinbarung)
• Termine:
  • Vorlesung:
    Mi 8:15-9:45 in SR 1.29
    Mi 10:15-11:00 in SR 1.29
  • Übungen:
    Mi 11:00-11:45 in SR 1.29

Vorlesungsthemen

1. Lempel-Ziv 78 Kompression, Entropie
   
   • G. Hansel, D. Perrin, I. Simon: Compression and Entropy,
   • Kapitel 5.4 in [B3].
2. Lempel-Ziv 77 Kompression, Konstruktion von Suffix-Bämen in Linearzeit
   • Material zu Suffix-Bämen: Kapitel 5, 6.1 und 7.17 in [B2], Kapitel 4 in [B4]
   • Material zu LZ77: Kapitel 5.4 in [B3]
3. Grammatik-basierte Kompression
   • W. Rytter: Application of Lempel-Ziv Factorization to the Approximation of Grammar-Based Compression
   • M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, A. Shelat: The smallest grammar problem
4. Pattern-Matching auf komprimierten Wörtern
   • Y. Lifshits: Solving Classical String Problems on Compressed Texts
5. Kompression von DNA
   • Xin Chen, Sam Kwong, Ming Li: A compression algorithm for DNA sequences and its applications in genome comparison

Übungsblätter

• Blatt 1 PS / PDF
• Blatt 2 PS / PDF
• Blatt 3 PS / PDF
• Blatt 4 PS / PDF
• Blatt 5 PS / PDF
• Blatt 6 PS / PDF
• Blatt 7 PS / PDF
• Blatt 8 PS / PDF
• Blatt 9 PS / PDF
• Blatt 10 PS / PDF

Einge Bücher