FoPra (WS 96/97)
Dynamische Graphenalgorithmen
Zweck der Veranstaltung:
Die dynamischen Graphenalgorithmen sind ein junges Forschungsgebiet.
Diese Algorithmen verwalten Informationen über Graphen, die
sich im Laufe der Zeit verändern, d.h., neue Knoten bzw. Kanten
werden zugefügt oder gelöscht. Die Herausforderung besteht darin,
die gewünschte Information in kürzerer Zeit als in der von der
trivialen Methode erforderten Zeit zu verwalten. Triviale
Methode heisst, nach jeder
Veränderung wird ein statischer Algorithmus aufgerufen, der diese
Information vom Anfang an wiederberechnet. Die dynamischen Graphenalgorithmen
haben viele Anwendungen, u.a. incremental compilation, Datenbanken,
VLSI, Netzwerkanalyse, und Verkehrssimulation.
Zweck des FoPras ist es, dynamische Graphenalgorithmen
mithilfe der LEDA Bibliothek für kombinatorisches und geometrisches
Rechnen zu implementieren. Die Teilnehmer sollen Erfahrung mit praktischen
Problemen, die während der Implementierung auftauchen,
bekommen. Ferner soll die LEDA Bibliothek um nützliche und korrekte
Software fürs Lösen von dynamischen Graphenproblemen
erweitert werden.
Behandelter Stoff:
Algorithmen für grundlegende Graphen- und Netzwerkoptimierungsprobleme
werden implementiert mit Schwerpunkt auf: shortest paths,
reachability/transitive closure, graph connectivity.
Vermittelte Fähigkeiten:
Programmiererfahrung; selbständige Implementierung von
praxistauglichen/fortgeschrittenen algorithmischen Methoden.
Literatur zur Veranstaltung: Aktuelle Originalarbeiten.
Voraussetzung für Scheinvergabe: Erfolgreiche Programmierung.
Fortsetzungsveranstaltung: Diplomarbeit.
Weitere Informationen: Anfragen bei
Christos D. Zaroliagis,
Gebäude 46.1, R. 316, Email: zaro@mpi-sb.mpg.de,
Tel: 9325116.