LEA

Proseminar: Datenkompression

Zusammenfassung

Über die weltweite Vernetzung sind immer größerer Datenmengen (u.a. Text, Audio, Video) immer bequemer verfügbar. Dies verstärkt die Notwendigkeit, diese Daten in möglichst kompakter Form zu speichern und zu übermitteln. Das Proseminar behandelt grundlegende Techniken der Komprimierung von Daten, die in vielen Bereichen Anwendung finden.

Die Kompressionsverfahren kann man grundsätzlich einteilen in verlustfreie Komprimierung und verlustbehaftete Komprimierung. Bei der verlustfreien Komprimierung kann die ursprüngliche Information durch Dekomprimierung exakt wiederhergestellt werden, während bei der Komprimierung mit Verlust zugunsten höherer Kompressionsdichte gewisse Details verlorengehen, was zum Beipiel bei der Komprimierung von Bildern tolerierbar ist.

In diesem Proseminar sollen für verschiedene Kompressionsverfahren jeweils sowohl der theoretische Hintergrund als auch praktische Anwendungen betrachtet werden. Im Folgenden finden sich ein paar Themenvorschläge, wir sind aber auch für weitere Themen offen. Sie können sich also auch gerne selbst ein Thema überlegen und dies vorstellen (beispielsweise eine interessante praktische Anwendung).

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.

Themenliste

Compression
  • Grundlagen der Informationstheorie
  • Kolmogorov-Komplexität
  • Entropy-Kodierung (Huffman-Kodierung, Shannon-Fano-Kodierung, Arithmetische Kodierung, ...)
  • Universelle Codes (Elias-Delta-Kodierung, Fibonacci-Kodierung, Levenshtein-Kodierung, ...)
  • Wörterbuchbasierte Kompression (LZ78, LZW, ...)
  • Burrows-Wheeler-Transformation
  • Dateikompression: zip, gzip, bzip2, ...
  • Bildkompression: JPEG, GIF, PNG, ...
  • Audiokompression: MP3, OGG, ...
  • Videokompression: MPEG, AVI
  • Runlength-Kodierung (Beispiel-Anwendung: Bitmap-Index)
  • Rank/Select-Datenstrukturen
  • Quadtree, Octree
  • Biologischer Exkurs: Alternatives Spleißen
  • Auch weitere Themen sind möglich

Anmeldung

Falls Sie Interesse haben, meldet Sie sich bitte kurz bei Johannes Krugel, dann können wir die Teilnehmerzahl abschätzen.

Termine

Die Vorbesprechung findet am 20.10.2010 um 16:45 in 03.11.018 statt.
Das Seminar findet an folgenden Terminen statt:
  • Montag, 06.12.2010 14:00–17:00 in 03.11.018
  • Donnerstag, 09.12.2010 16:00–18:00 in 01.10.011
  • Mittwoch, 15.12.2010 16:00–17:00 in 03.19.011B

Hinweise

Vorbereitung
Jeder Studierende wählt ein Thema, sucht sich relevante Literatur und verschafft sich einen Überblick über das Thema. Dann vereinbart sie/er einen Termin mit dem Betreuer, um die verwendete Literatur und den Themenschwerpunkt abzusprechen (spätestens bis zum 12.11.2010).
Probevortrag
Vor dem Vortragstermin wird dann die Präsentation mit dem Betreuer durchgesprochen (spätestens bis zum 26.11.2010). Zu diesem Zeitpunkt muss auch mindestens das Inhaltsverzeichnis der Ausarbeitung vorliegen. Beim Probevortrag präsentiert jeder Studierende sein Thema einem Kommilitonen, der dann dazu konstruktive Kritik äußert (spätestens bis zum 03.12.2010).
Seminarvortrag
Der Seminarvortrag dauert 45 ± 5 Minuten. Nach dem Vortrag hat das Publikum die Möglichkeit, Fragen zu stellen (in der Woche 06.12.2010–10.12.2010).
Seminararbeit
Eine erste Version der Ausarbeitung wird einem Kommilitonen zur Verfügung gestellt (spätestens bis zum 23.12.2010), der dann eine kurze Kritiken schreibt (spätestens bis zum 07.01.2011). Die Endfassung der Seminarbeit ist als LaTeX-Datei und PDF-Datei abzugeben (spätestens bis zum 21.01.2011). Der Umfang der Seminararbeit beträgt 5 ± 1 Seiten (ohne Inhalts- und Literaturverzeichnis). Eine LaTeX-Vorlage für die Ausarbeitung findet sich in diesem Ordner.
Anwesenheit
Jeder Studierende muss bei allen Vorträgen anwesend sein und sich aktiv an der Diskussion beteiligen.