Sommersemester 2006
Der ausgefallene Vortrag "Kürzeste Wege in Graphen" wird am 27.06.06 nachgeholt.
Auf dieser Seite finden Sie verschiedene Informationen zum
Proseminar zu Algorithmen auf Graphen, das im Sommersemester 2006
von Prof. Dr. Rudolf Kruse und Frank Rügheimer an der
Otto-von-Guericke-Universität Magdeburg veranstaltet wird.
Diese Seite wird im Laufe des Semesters aktualisiert.
Graphen spielen in der Informatik in vielen Anwendungen eine
wichtige Rolle. Sie werden in der Ablaufplanung, in der Logistik,
beim Aufbau von Transport- und Rechnernetzen, aber auch beim
automatischen Schlußfolgern und der Modellierung unsicheren
Wissens (graphische Modelle wie Bayes-Netze und Markov-Netze)
eingesetzt. In diesem Proseminar werden verschiedene Algorithmen
auf Graphen behandelt, die in der Praxis Bedeutung haben.
Anmeldung: Leider können keine neuen Anmeldungen mehr berücksichtigt werden, da die maximale Teilnehmerzahl bereits erreicht worden ist.
Die Vortragsfolien sollten in der Woche vor dem Vortrag (am günstigsten als .PDF-Datei) eingesandt werden.
Vorbesprechung mit Themenvergabe am 11.04.2006.
- Optimale spannende Bäume
(z.B. Kruskal-Algorithmus, Prim-Algorithmus)
- Kürzeste Wege in Graphen
(z.B. Dijkstra-Algorithmus, Floyd-Algorithmus)
- Finden von Euler- und Hamiltonkreisen
(Problem des Handlungsreisenden)
- Finden von (starken) Zusammenhangskomponenten
und Erkennen von Brücken.
- Planare (plättbare) Graphen, Zeichnen von Graphen
- Färben der Knoten von Graphen
(speziell: Vierfarbenproblem)
- A*-Algorithmus (heuristische Suche)
- Maximaler Fluß und minimaler Schnitt.
- Triangulierung ungerichteter Graphen
(z.B. Algorithmus von Tarjan und Yannakakis,
aber auch geometrische Algorithmen)
- Finden (maximaler) Cliquen und Aufbau von Verbundbäumen
- Evidenzpropagation in Bayes-Netzen und Markov-Netzen
- Zufälliges Erzeugen von Graphen und Bayes-Netzen
- Zerlegung von (markierten) Graphen
Dies ist nur eine Liste einiger möglicher Themen.
Teilnehmer können weitere Themen vorschlagen.
Wochentag |
Zeit |
Raum |
Beginn |
Dienstag |
13:00 - 15:00 Uhr |
G05-313 |
11.04.2006 (Vorbesprechung) |
Programm
Termin |
Vortragender |
Thema |
02.05.2006 |
Jan Heidel |
Finden von Euler- und Hamiltonkreisen (Problem des Handlungsreisenden) (Folien) |
|
Martin Reyher |
Finden von (starken) Zusammenhangskomponenten und Erkennen von Brücken (Folien) |
09.05.2006 |
Maurice Duvigneau |
Kürzeste Wege in Graphen (entfallen, neuer Termin am 27.06.2005) |
|
Thomas Naumann |
A*-Algorithmus (Folien) |
16.05.2006 |
Sven Heinicke |
Färben der Knoten von Graphen (speziell: Vierfarbenproblem) (Folien) |
|
Ronny Harbich |
Optimale Spannende Bäume (z.B. Kruskal-Algorithmus, Prim-Algorithmus) (Folien) |
23.05.2006 |
Christoph Bösel |
Planare Graphen, Zeichnen von Graphen (Folien) |
|
Sebastian Thurm |
Maximaler Fluß und minimaler Schnitt (Folien) |
06.06.2006 |
Ronny Döppe |
Zerlegung von (markierten) Graphen (Folien) |
|
Steven Birr |
Matching (Paarungen) in Graphen (Folien) |
13.06.2006 |
Steffen Ernst |
Triangulierung ungerichteter Graphen (z.B. Algorithmus von Tarjan und Yanakakis, aber auch geometrische Algorithmen) (Folien) |
|
Norman Krell |
Finden maximaler Cliquen und Aufbau von Verbundbäumen (Folien) |
20.06.2006 |
Thomas Thüm |
Evidenzpropagation in Bayes-Netzen und Markov-Netzen (Folien) |
|
Björn Schapitz |
Zufälliges Erzeugen von Graphen und Bayes-Netzen (Folien) |
27.06.2006 |
Maurice Duvigneau |
Kürzeste Wege in Graphen (Folien) |
Wenn Sie Fragen zum Proseminar haben, wenden Sie sich bitte (wenn
möglich, per E-mail) an eine der unten aufgeführten Personen.
© 2003-2005
Christian Borgelt,
2006
Frank Rügheimer