Praktikum Algorithm Engineering - Algorithmen zum Zeichnen von Graphen

• Betreuung: Dr. Marcus Krug, Dr. Reinhard Bauer/, Prof. Dr. Dorothea Wagner
• Präsenztermine: freitags 9:45–11:15 Uhr, Seminarraum 301 (Informatikgebäude 50.34)
• Vorbesprechung: Die Vorbesprechung wird am Freitag, den 23.10.09, um 9:45 Uhr in Raum 301 stattfinden.
• Teilnahme: Die Teilnehmerzahl ist auf zwölf Personen begrenzt. Der Kurs kommt ab einer Mindestzahl von vier Teilnehmern zustande. Anmeldung per E-Mail an Marcus Krug oder Reinhard Bauer.

• Nähere Informationen werden noch bekanntgegeben.

Hypergraphen sind eine Verallgemeinerung von Graphen, bei denen Kanten aus einer beliebigen Menge von Knoten bestehen können. Mit ihrer Hilfe lassen sich auch komplexere Relationen zwischen Objekten modellieren. Hypergraphen tauchen typischerweise zum Beispiel im Kontext von Datenbanken auf.

Im Gegensatz zu klassischen Graphen gibt es für Hypergraphen kein einheitliches Zeichen-Paradigma, da sich Hyperkanten nicht auf einfache Weise darstellen lassen. Grundsätzlich gibt es sehr verschiedene Herangehensweisen an das Zeichnen von Hypergraphen. Um Hyperkanten direkt darstellen zu können, können Euler- und Venn-Diagramme verwendet werden. Daneben wird häufig versucht, das Zeichnen von Hypergraphen auf ein klassisches Graphzeichenproblem zu reduzieren, indem die Hypergraphen mithilfe von einfachen Graphen modelliert werden.

Im Praktikum werden wir Daten aus verschiedenen Anwendungen als Hypergraphen modellieren und zeichnen. Die Anwendungen umfassen große SAT-Instanzen, aber auch Warenkorb-Daten sowie Co-Autoren-Netzwerke. Ziel des Praktikums ist es die Daten so zu visualisieren, dass inhärente Strukturen möglichst gut dargestellt werden.

In einem ersten Präsenztermin wird zunächst eine theoretische Fundierung des Stoffes vermittelt werden; daneben wird Gelegenheit zur praktischen Einarbeitung in die Thematik und die verwendeten Bibliotheken an Hand einiger Aufwärmaufgaben gegeben sein. Im Anschluss daran werden in Teams von zwei bis drei Personen und individueller Betreuung durch Lehrstuhlmitarbeiter eine oder mehrere größere Aufgaben bearbeitet werden. Zusätzlich wird es einen Wettbewerb um die schönsten Bilder bzw. schnellsten Algorithmen geben. Jeweils etwa zu Semesterhalbzeit und -ende wird jede Gruppe in einer Präsentation ihre bisherige Arbeit vorstellen. Abschließend ist eine schriftliche Ausarbeitung der Ergebnisse in LaTeX zu erstellen.

Folien der Vorbesprechung

Übungsblatt 1

Übungsblatt 2

Voraussetzung für die Teilnahme am Praktikum sind Grundkenntnisse aus den Bereichen Algorithmentechnik und Graphentheorie sowie Grundkenntnisse in Java oder C++. Ein Besuch der Vorlesung Graphenzeichnen ist nicht erforderlich.