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

Dienstag, 28. 10. 2003

Vorbesprechung

Dienstag, 25. 11. 2003: entfällt wegen Streik

erste Präsentationen der Projektvorhaben

Dienstag, 2. 12. 2003: entfällt wegen Streik

weitere Projektpräsentationen

Dienstag, 9. 12. 2003: erste Präsentationen der Praktikumsprojekte

Fabian Stehn, Bastian Voigt: Visualisierung eines Algorithmus von Shih und Hsu zum Planaritätstest

Dienstag, 16. 12. 2003: weitere Präsentationen der Praktikumsprojekte

Rasmus Krause: Optimalität oder Nichtoptimalität von Präfix-Codes
Sabine Bender: Zerlegung in zweifach-zusammenhängende Komponenten und Ohrenzerlegung

Dienstag, 6. 1. 2004: weitere Präsentationen der Praktikumsprojekte

Michael Zilske: Zerlegung in dreifach-zusammenhängende Komponenten

Dienstag, 13. 1. 2004: kein Treffen
Dienstag, 20. 1. 2004: kein Treffen
Dienstag, 27. 1. 2004:

Fabian Stehn, Bastian Voigt: erster Zwischenbericht

Erweiterung des Visualisierungsrahmenprogramms um ein Fenster für Pseudocode.
Als Beispiel: Tiefensuche mit Postfixnotation

Dienstag, 3. 2. 2004:

Dienstag, 10. 2. 2004:

Alexander Schliep (Max-Planck-Institut für molekulare Genetik) wird Gato/Catbox vorstellen und für Fragen zur Verfügung stehen.

Dienstag, 17. 2. 2004:

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

Karel Culik II and J. Kari, Image Compression Using Weighted Finite Automata, Computer and Graphics 17, No. 3 (1993), 305-313.
Karel Culik II and J. Kari, Efficient Inference Algorithm for Weighted Finite Automata, in "Fractal Image Compression", ed. Yuval Fisher, Springer Verlag.
Karel Culik II and J. Kari, Computational Fractal Geometry with WFA, Acta Informatica 34 (2), 151-166 (1997).
siehe GFA creator

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:

das System GATO (Graph Animation Toolbox), das auf der Programmiersprache Python aufsetzt.
die Animationsschnittstelle von Cinderella, bei der die Algorithmen in Java implementiert werden. Dieses System unterstützt allerdings nicht die Anzeige des Programmablaufs im Quellcode.

Neue Algorithmen zum Planaritätstest

(vergeben an Fabian Stehn und Bastian Voigt)

W.-K. Shih und W.-L. Hsu: A new planarity test, Theoretical Computer Science, vol. 223, no, 1-2, pp. 179-191, 1999
R. Thomas: Planarity in linear time, class notes
Kerstin Brümann, Planaritätstest, Seminarausarbeitung, SS 2003.

Planare Zeichnungen und kanonische Ordnungen, Schnyder-Wälder

Kapitel 2 in M. Kaufmann und D. Wagner (Hrsg.): Drawing Graphs, Methods and Models, Springer 2001.
Originalliteratur von de Fraysseix/Pach/Pollack, Walter Schnyder, Goos Kant, Stefan Felsner.

Blockzerlegung (Zerlegung in zweifach-zusammenhängende Komponenten)

(vergeben an Sabine Bender und Jan Willems)

Lehrbücher
eventuell mit Ohrenzerlegung

Zerlegung in dreifach-zusammenhängende Komponenten

(vergenen an Michael Zilske)

John E. Hopcroft and Robert E. Tarjan. Dividing a graph into triconnected components. SIAM Journal on Computing 2 (3), 135-158, 1973.
Keim-Phong Vo, Finding triconnected components of graphs, Linear and Multilinear Algebra 13 (1983), 143-165.
Pascal-Programm zum Testen von dreifachem (und zweifachem) Zusammenhang
unvollständiges Manuskript von mir.

Günter Rote, 27. 1. 2004