University of Konstanz
Algorithmik
Prof. Dr. Ulrik Brandes

Übungen zur Vorlesung "Zeichnen von Graphen" (Sommersemester 2007)

+++ Aktuelles +++

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) Di 8:30-10:00 (D 406)
Do 8:30-10:00 (D 406)
Übung (M. Badent, K. Boitmanis) Mo 14:15-15:45 (D 406)
Prüfungen 1. Termin: 19. Juli 2007
2. Termin: 17. Oktober 2007

Übungsblätter

Übungsblätter werden donnerstags in der Vorlesung ausgegeben.

Die Aufgaben sind innerhalb einer Woche zu bearbeiten, und werden als schriftliche Ausarbeitungen im Treppenhaus vor dem Sekretariat des Lehrstuhls (Raum E 214) abgegeben. Die Besprechung der 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 19.04.2007 26.04.2007 30.04.2007 PDF, Quellcode
2 26.04.2007 03.05.2007 07.05.2007 PDF
3 03.05.2007 10.05.2007 14.05.2007 PDF
4 10.05.2007 16.05.2007 21.05.2007 PDF
5 16.05.2007 24.05.2007 04.06.2007 PDF, Quellcode
6 24.05.2007 31.05.2007 04.06.2007 PDF
7 31.05.2007 06.06.2007 11.06.2007 PDF
8 06.06.2007 14.06.2007 18.06.2007 PDF
9 14.06.2007 21.06.2007 25.06.2007 PDF
P 14.06.2007 05.07.2007 09.07.2007 Praxisaufgabe
10 21.06.2007 28.06.2007 02.07.2007 PDF
11 28.06.2007 05.07.2007 09.07.2007 PDF
12 05.07.2007 12.07.2007 16.07.2007 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 oder der Abgabe als Papierversion beizufügen.

Skriptum

Grundlage ist das Skript der Veranstaltung im Sommersemester 2004. Dieses wird im Verlauf des Semesters ergänzt und überarbeitet. Die nachfolgenden Dateien sind nur von Rechnern der Universität Konstanz aus zugreifbar.

  • Prolog
  • Einführung
  • Teile und Herrsche
  • Inkrementelle Konstruktion
  • Kombinatorische Optimierung
  • Lagen-Layouts (Artikel und Folien zur Koordinatenzuweisung)
  • Globale Optimierung
  • Für Anmerkungen und Hinweise auf Fehler sind wir dankbar.

    Literatur

    Weitere Informationen