LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München
english

Data Compression (WS 99/00)


* Dozent:
Prof. Dr. Sami Khuri

* Bereich:
3 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Sonstige prüfbare Vorlesung im Gebiet Algorithmen

* Zeit und Ort:
Di 13h c.t. - 15:00, Hörsaal S1128
Do 13h c.t. - 14:00, Hörsaal S1128

* Keine Übung.

* Hörerkreis:
Studierende im Hauptstudium der Informatik

* Voraussetzungen:
Stoff des Informatik Grundstudiums
Die Vorlesung wird auf Englisch gehalten.

* Empfehlenswert für:
Erweiterte Kenntnisse im Bereich Algorithmen

* Inhalt:
  1. Introduction to Data Compression
    • What is Data Compression?
    • Why is it important?
  2. Lossless Data Compression
    • Statistical Methods
    • Huffman Coding
    • Shannon-Fano Coding
    • First Elias Code
    • Second Elias Code
    • Fibonacci Code
    • Adaptive Huffman Coding
    • Arithmetic Coding
    • Dictionary-Based Codes
    • LZ77, LZ78 and LZW
    • Burrows-Wheeler Algorithm
    • Run-Length Encoding
    • Facsimile Encoding
    • Quadtree Compression
    • Space-Filling Curves
    • Delta Encoding
    • Linear Predictive Coding
  3. Lossy Data Compression
    • Dynamic Window-Based RLE
    • Block Truncation Coding
    • Scalar Quantization
    • Vector Quantization
    • Differential Encoding
    • Transform Coding
    • Introduction to Color Spaces
    • JPEG

Die Vorlesung wird in Englisch gehalten. Mehr zum Inhalt finden Sie auf der englischen Seite!

* Weiterführende bzw. verwandte Vorlesungen:
Effiziente Algorithmen und Datenstrukturen I
Effiziente Algorithmen und Datenstrukturen II

* Beispiele:
Burrows-Wheeler Algorithm
Burrows-Wheeler Encoding of "mississippi"

* Übungen:
Übung 1 (Postscript).
Übung 2 (Postscript).

* Literatur:
David Salomon:
Data Compression. The Complete Reference
Springer Verlag, 1998
Khalid Sayood:
Introduction to Data Compression
Morgan Kaufmann Publishers, Inc. San Francisco, California, 1996.
Jerry Gibson, Toby Berger, Tom Lookabaugh, Dave Lindbergh, Richard Baker:
Digital Compression for Multimedia. Principles and Standards
Morgan Kaufmann Publishers, Inc., San Francisco, California, 1998.

* Sprechstunde:
siehe hier


khuri@in.tum.de