University of Konstanz
Algorithmik
Prof. Dr. Ulrik Brandes

Übungen zur Vorlesung „Zeichnen von Graphen“ (Sommersemester 2009)

+++ Aktuelles +++

09.07.2009: Am Dienstag, den 14.07.2009 fällt die Vorlesung aus

Grundlage für die effektive und effiziente Visualisierung von Netzwerken sind Algorithmen zur Bestimmung eines Layouts für den die Netzwerkstruktur beschreibenden Graphen.

Das automatische Zeichnen von Graphen hat daher wichtige Anwendungen in Kernbereichen der Informatik wie etwa Datenbanken, Software-Engineering, VLSI- und Netzwerk-Design und visuelle Benutzerschnittstellen. Anwendungen in anderen Bereichen betreffen alle Aspekte der visuellen Datenanalyse, z.B. in den Ingenieurwissenschaften, Chemie und Biologie oder Sozial- und Politikwissenschaft.

Dazu werden verschiedene algorithmische Prinzipien und Methoden wie z.B. kräftebasierte Verfahren und Flussmethoden besprochen.

Termine

Vorlesung (U. Brandes, S. Cornelsen) Di 08.30–10.00 (D 404)
Mi 08.30–10.00 (D 436)
Übung (M. Mader, C. Pich) Mo 14.00–16.00 (D 406)
mündliche Prüfungen nach Vereinbarung

Übungsblätter

Die theoretischen Aufgaben werden mittwochs als Übungsblätter in der Vorlesung ausgegeben, sind innerhalb einer Woche bis Freitagmorgen zu bearbeiten, und werden als schriftliche Ausarbeitungen im Treppenhaus vor dem Sekretariat des Lehrstuhls (Raum E 214) abgegeben.

Daneben gibt es praktische Aufgaben, in denen Algorithmen zum Zeichnen von Graphen entworfen und in Java implementiert und getestet werden. In vier dreiwöchigen Projekten werden Layoutprobleme aus verschiedenen Teilgebieten behandelt, für die Lösungen erarbeitet und an praktischen Beispielen erprobt werden.

Die Besprechung aller Aufgaben und die Rückgabe der korrigierten und mit Punkten bewerteten Abgaben erfolgt in der Übung. Das Erlangen von mindestens der Hälfte der möglichen Punkte und die aktive Teilnahme an den Übungen ist Voraussetzung für die Zulassung zur Prüfung.

Alle Aufgaben können und sollen in Zweiergruppen abgegeben werden.

Nr. Ausgabe Abgabe Besprechung Download
1 22.04.2009 30.04.2009 04.05.2009 PDF
2 29.04.2009 08.05.2009 11.05.2009 PDF
3 06.05.2009 15.05.2009 18.05.2009 PDF
4 13.05.2009 22.05.2009 25.05.2009 PDF
5 20.05.2009 29.05.2009 08.06.2009 PDF
6 27.05.2009 05.06.2009 08.06.2009 PDF
7 03.06.2009 12.06.2009 15.06.2009 PDF
8 10.06.2009 19.06.2009 22.06.2009 PDF
9 17.06.2009 26.06.2009 29.06.2009 PDF
10 24.06.2009 03.07.2009 06.07.2009 PDF
11 01.07.2009 08.07.2009 13.07.2009 PDF
12 09.07.2009 17.07.2009 20.07.2009 PDF

Hinweis: Einige Dokumente sind nur lokal lesbar.

Praktische Aufgaben

Für die praktischen Aufgaben wird die Bibliothek yFiles verwendet. Die Lösungen sind als Quellcode per Email zu versenden.

Nr. Ausgabe Abgabe Besprechung Download
1 22.04.2009 15.05.2009 18.05.2009 PDF, BinaryTreeGenerator.java
2 22.05.2009 12.06.2009 15.06.2009 PDF, yEd-Beispiel zu Optionsdialogen, st-Graph (Beispiel)
3 17.06.2009 10.07.2009 13.07.2009 PDF

Hinweis: Einige Dokumente sind nur lokal lesbar.

Skriptum

Grundlage ist das Skript der Veranstaltung im Sommersemester 2007. Dieses wird im Verlauf des Semesters ergänzt und überarbeitet. Für Anmerkungen und Hinweise auf Fehler sind wir dankbar.

Ergänzende Schriften:

Literatur

Weitere Informationen