Zur
  Seite der TU

Graphen- und Netzwerkalgorithmen

Zur Seite des Fachbereichs 3
 

Sommersemester 2000

 
LV-Nr.: 0350 L 148
 

Prof. Dr. Martin Grötschel
 


Inhalt

Viele praxisrelevante Fragestellungen in Wirtschaft, Technik und in anderen Wissenschaften können als Optimierungsprobleme in Graphen modelliert werden. Beispiele, die in der Vorlesung angesprochen werden, kommen aus den Bereichen Telekommunikation, Produktions- und Verkehrsplanung, Informatik, Biologie und Physik.

In dieser Vorlesung werden grundlegende Algorithmen zur Lösung von Problemen in Graphen behandelt. Unter anderem werden Algorithmen vorgestellt und analysiert, die folgende Fragen beantworten: Wie komme ich möglichst schnell von A nach B, wie pumpe ich möglichst viel Wasser durch ein bestehendes Leitungssystem, wie löse ich das Heiratsproblem?

Es werden dabei relevante Teile der Graphentheorie eingeführt sowie wichtige algorithmische Suchtechniken und Grundprinzipien wie Greedy- oder Augmentierungsverfahren. Mit diesen Methoden können die oben genannten Probleme effizient gelöst werden.

Es gibt (natürlich) auch Graphenprobleme, für die noch keine effektiven Lösungsverfahren bekannt sind. Beispiele hierfür sind das Travelling-Salesman und das Stabile-Mengen-Problem. Aber auch die Aufgabe, ein ausfallsicheres Kommunikationsnetzwerk zu entwerfen, gehört dazu. In der Vorlesung wird gezeigt, wie man mit sogenannten primalen und dualen Heuristiken "gute" Lösungen für derartige Probleme finden kann.

Voraussetzungen:

keine

Geplante Fortsetzung:

Diese Vorlesung ist die Einführungsveranstaltung und Grundvorlesung für den Schwerpunkt "Algorithmische Diskrete Mathematik" in den Studiengängen Mathematik und Techno- und Wirtschaftsmathematik. Im nächsten Semester wird die Reihe durch die Vorlesung  Lineare Optimierung  fortgesetzt.


Literatur

R.K. Ahuja, T.L. Magnanti, J.B. Orlin:
Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993

W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver:
Combinatorial Optimization, Wiley, 1998

M. Grötschel, L. Lovasz:
Combinatorial Optimization,
in R. L. Graham, M. Grötschel, L. Lovasz: "Handbook of Combinatorics." Vol. 2.
Amsterdam, North-Holland, 1541-1597, 1995

Jungnickel, Dieter
Graphs, Networks and Algorithms, Springer, 1999
(englische Übersetzung der deutschen Version aus dem Jahre 1994)

Vorlesungsskript (vorläufige Version vom 16.6.2000, Kapitel 1 - 8, PS-File)


Kontakte

   
Sprechstunde
Raum Telefon email
Dozent: Prof. Dr. Martin Grötschel n.V. MA 602 84185-210 groetschelzib.de
Assistent: Dr. Frank Lutz Do   10:00 - 11:30 Uhr MA 624 314-25 751 lutzmath.tu-berlin.de
Tutoren: Georg Baier Mi   14:15 - 15:45 Uhr MA 613 314-25 735 baiermath.tu-berlin.de
Dr. Christian Haase Fr   12:15 - 13:45 Uhr MA 706 314-25 758 haasemath.tu-berlin.de
Sekretariat (TU): Elke Pose Mo, Di, Do, Fr   9:30 - 11:30 Uhr MA 627 314-23 354 posemath.tu-berlin.de
Sekretariat (ZIB): Bettina Kasse n.V. 3025 84185-209 kassezib.de


Zeiten

Vorlesung: Di 16:00 - 17:30 MA 041 Prof. Dr. Martin Grötschel
Mi 16:00 - 17:30 MA 041
Übung: Mi 14:15 - 13:45 MA 043 Dr. Frank Lutz
Tutorien: Do 16:00 - 17:30 MA 742 Georg Baier/Dr. Christian Haase
Fr 8:30 - 10:00 MA 742 Georg Baier/Dr. Christian Haase


Programmieraufgaben

Im Laufe des Semesters wird es mehrere Programmieraufgaben geben, bei denen Algorithmen in der Programmiersprache C++ unter Verwendung von LEDA zu implementieren und an vorgegebenen Beispielen zu testen sind. Programmieraufgaben werden nicht korrigiert, sondern bei einer Programmvorführung abgenommen. Die Vorführungen finden im Unix-Pool MA 241 auf den IBM-Rechnern statt, Termine werden in den Übungen vereinbart.

The LEDA User Manual

Hinweise zur Benutzung von LEDA


Rechnervorrangzeiten
(Unix-Pool MA 241)

Tag Zeit
Montag 12-18 Uhr
Donnerstag 12-14, 16-18 Uhr
Freitag 9-14 Uhr


Zu diesen Zeiten sind für Teilnehmerinnen und Teilnehmer der Lehrveranstaltung jeweils 20 Rechnerplätze reserviert.


Übungsblätter:


Scheinkriterien

50% der Punkte aus den Übungsblättern 1 bis 6 und 50% der Punkte aus den Übungsblättern 7 bis 13 sowie die erfolgreiche Bearbeitung aller Programmieraufgaben. Außerdem wird die aktive Mitarbeit in den Tutorien vorausgesetzt.


Valid HTML 4.0! Zuletzt aktualisiert: 13. Juli 2000