Forschungsinstitut für Diskrete Mathematik
Programmierpraktikum für das Grundstudium
Wintersemester 2006/07
Thema: Netzwerk-Simplex
Der Netzwerk-Simplex-Algorithmus ist eine Spezialisierung des
Simplex-Algorithmus auf die Berechnung von Flüssen minimaler Kosten.
Während für den Simplex-Algorithmus im allgemeinen keine polynomielle
Laufzeit bewiesen werden kann, läßt sich der
Netzwerk-Simplex-Algorithmus mit polynomieller Laufzeit implementieren. Ziel
dieses Praktikums ist eine Implementierung des Netzwerk-Simplex-Algorithmus.
Dabei ist auf Effizienz zu achten, da das Programm auch auf sehr großen
Instanzen, die beim Entwurf höchstintegrierter Chips auftreten (das Bild
unten zeigt zum Beispiel 1/10000 der Verdrahtung eines Chips), in
vertretbarer Zeit terminieren soll.
Vorbesprechung:
Montag, den 10. Juli 2006 um 14 Uhr c.t.
im Seminarraum des Institutes für Diskrete Mathematik, Lennéstraße 2
Studenten, die Interesse an einer Praktikumsteilnahme haben,
aber nicht an der Vorbesprechung zu dieser Veranstaltung teilnehmen
können, werden gebeten, sich vorab mit
Ulrich Brenner,
brenner (at) or.uni-bonn.de,
Tel. 0228 / 73 87 49
in Verbindung zu setzen.
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
U. Brenner