Praktikum über Datenkompression und Algorithmen-Visualisierung (Nr. 19604)

Wintersemester 2003/2004, 3-stündig, ECTS-Punkte (Credits): 6
Dozenten:
Prof. Dr. Günter Rote, Dipl.-Inform. Tobias Lenz
Veranstaltungszeitraum:
Vorbesprechung: Dienstag, 28.10.2003, 16 Uhr (um eine Woche verschoben wegen der Einführungsveranstaltung ins Hauptstudium am 21.10.)

DI: 16:00 - 19:00 Institut für Informatik, Seminarraum 046

Inhalt:
In Gruppen sollen (a) Verfahren aus dem Gebiet der Datenkompression implementiert und damit experimentiert werden (b) Graphenalgorithmen visualisiert werden. Eine Ausweitung der Projekte in Studien- oder Diplomarbeiten ist möglich.
Zielgruppe:
Studenten des Hauptstudiums Informatik oder Mathematik

Termine

Ablauf

Nach einer Projektfindungs- und -definitionsphase soll Ihr Projektvorhaben zu Beginn auf ca. 1/2 Seite zusammengefasst werden und vor der Gruppe kurz präsentiert werden, damit wir eine Messlatte haben, worin die geplante Projektarbeit besteht und wann das Praktikum vollendet ist. Natürlich bestehe ich nicht auf den buchstäblichen Erfüllung des Projektvorhabens, wenn sich zwischendurch unerwartete Schwierigkeiten ergeben oder sich lohnendere Alternativwege auftun.
In der Mitte des Semesters gibt es eine Präsentation der Zwischenergebnisse, und am Ende eine Abschlusspräsentation. Zusätzlich erwarte ich einen schriftlichen Praktikumsbericht (etwa 3 Seiten, kann auch mehr sein), der die Ziele und Ergebnisse des Praktikums beschreibt, aber auch den Weg dorthin, einschließlich der aufgetretenen Schwierigkeiten und "Abweichungen vom Plan". Die verwendete Literatur oder Software soll angegeben werden, und die Software, die als Ergebnis der Praktikums entsteht, soll dokumentiert sein.

Vergebene Projekte

Fabian Stehn, Bastian Voigt
Visualisierung: Planaritätstest
Arash Sarhoki, Rasmus Krause Optimalität von Präfix-Codes
Sabine Bender, Jan Willems
Zerlegung in zweifach-zusammenhängende Komponenten
Michael Zilske
Zerlegung in dreifach-zusammenhängende Komponenten
Alexander Rakovski Optimale Codes durch lokale Verbesserung

Projekte zur Datenkompression

Präfix-Codes sind nicht optimal beim Morse-Alphabet?

(vergeben an Rasmus Krause und Arash Sarhoki)

Bei Alphabeten, wo alle Symbole gleichwertig sind, sind Präfixcodes optimal, und optimale Codes können mit dem Huffman-Algorithmus gefunden werden. Bei Alphabeten mit verschieden langen Symbolen, wie zum Beispiel dem Morsealphabet mit ".", "-", und "Pause" funktioniert der Huffman-Algorithmus nicht, und es ist nicht einmal klar, ob Präfixcodes ausreichen.

Peter W. Shor. A counterexample to the triangle conjecture. J. Combinatorial Theory. Ser. A. 38 (1983), 110-112.

Optimale Codes durch lokale Verbesserung

(vergeben an Alexander Rakovski)

Der Huffman-Algorithmus ist sehr einfach, aber die Abhängigkeit des Ergebnisses von den Daten ist nicht sehr durchsichtig, und "dynamische" Huffman-Algorithmen bemühen sich im Wesentlichen, die Änderungen im Huffman-Algorithmus nachzuvollziehen. Hier sollen einfache Algorithmen betrachtet werden, die nur die Tiefenfolge des Codes betrachten und lokale Veränderungen vornehmen, bis der Kode nicht mehr verbessert werden kann. [Optimalitätsbeweis, (li-1,li,li+1) += (1,-3,2)] Sprünge in der Gradfolge, unter welchen Bedingungen.?]

Optimale Codes für natürliche Zahlen

siehe  M. Golin und K. K. Ma, Algorithms for Infinite Huffman-Codes, erscheint in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'04). 2004.

Bildkompression mit gewichteten endlichen Automaten

Geometrische Kompression

Es gibt dazu einen Überblicksartikel von Gotsman, Gumhold und Kobbelt. Mögliches Projekt: verschiedene (verbesserte) Möglichkeiten der Vorhersage der Position der Punkte.
siehe auch Video und Demo-Programm zum Face-Fixer-Verfahren zur Kodierung der Netzstruktur.

Projekte zur Visualisierung von Graphenalgorithmen

Für die Visualisierung kommen zwei Systeme in Frage:

Neue Algorithmen zum Planaritätstest

(vergeben an Fabian Stehn und Bastian Voigt)

Planare Zeichnungen und kanonische Ordnungen, Schnyder-Wälder

Blockzerlegung (Zerlegung in zweifach-zusammenhängende Komponenten)

(vergeben an Sabine Bender und Jan Willems)

Zerlegung in dreifach-zusammenhängende Komponenten

(vergenen an Michael Zilske)

Günter Rote, 27. 1. 2004