Zur Seite der TU

Graphen- und Netzwerkalgorithmen

(ADM I)

 Zur Seite des Instituts für Mathematik
 

Sommersemester 2006

  
LV-Nr.: 0230 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 Linear and Integer Programming im Rahmen des Projekts Berlin Mathematical School fortgesetzt.

Ferner bieten Prof. Grötschel und Dr. Ralf Borndörfer im Wintersemester 2006/2007 das Seminar Geometrische Varianten kombinatorischer Optimierungsprobleme an.

An dieser Stelle möchten wir auch auf die Vorlesung Approximationsalgorithmen hinweisen, die im kommenden Semester von Dr. Marco Lübbecke gehalten wird.

Literatur

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

D. Bertsimas, R. Weismantel:
Optimization over Integers, Dynamic Ideas, Belmont, Massachusetts, 2005 W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver:
Combinatorial Optimization, Wiley, 1998

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein:
Introduction to Algorithms, McGraw-Hill, 1990 (2. Auflage, 2001)

M. Grötschel:
P= NP?,
Elemente der Mathematik, 57 (2002) 96-102

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

M. Grötschel, M. Padberg:
Die optimierte Odyssee,
Spektrum der Wissenschaft, 4 (1999) 76-85

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

B. Korte, J. Vygen:
Combinatorial Optimization, Theory and Algorithms, Springer, 2000 (3. Auflage, 2006)

A. Schrijver:
Combinatorial Optimization: Polyhedra and Efficiency (3 volumes), Springer, 2003
(auch verfügbar auf CD-ROM)

Vorlesungsskriptum : Die aktualisierte Fassung des Skripts finden Sie hier.

Kontakte

   
Sprechstunde
 Raum Telefon email
Dozent: Prof. Dr. Martin Grötschel n.V. MA 302 84185-210 groetschelzib.de
Assistent: Rüdiger Stephan Mi   12:00 - 14:00 Uhr MA 241 314-28 323 stephanmath.tu-berlin.de
Tutor: Tosten Ueckerdt Mo   12:00 - 14:00 Uhr MA 241 ueckerdtmath.tu-berlin.de
Sekretariat (TU): Jeanette Dobrindt Mo - Do   9:30 - 11:30 Uhr MA 303 314-29 259 dobrindtmath.tu-berlin.de
Sekretariat (ZIB): Bettina Kasse n.V. 3025 84185-209 kassezib.de

Zeiten

Vorlesung: Do 10:15 - 11:45 MA 004 Prof. Dr. Martin Grötschel
Fr 10:15 - 11:45 MA 041
Übung: Di 10:15 - 11:45 H 0106 Rüdiger Stephan
Tutorien: Mo 08:15 - 09:45 MA 749 Torsten Ueckerdt
Do 12:15 - 13:45 MA 651 Torsten Ueckerdt

Übungsblätter:

Programmieraufgaben:

Die für diesen Kurs zu lösenden Programmieraufgaben sollen in Java unter Benutzung der Graphenklasse (jGABL) implementiert werden.


jGABL für Zuhause:   http://www.math.tu-berlin.de/jGABL.

Beispielgraphen

Beispielprogramme


Hinweise zur Benutzung von jGABL im Unix-Pool

Im Unix-Pool ist die Bibliothek jGABL.jar und die dazugehörende Dokumentation jGABL_doc.jar bereits im Verzeichnis /net/gna/jGABL installiert. Im Verzeichnis /net/gna/examples liegt das Beispielprogramm PrintAdjacencyList.java und unter /net/gna/graphs gibt es Beispielgraphen. Das Programm PrintAdjacencyList.java könnt ihr zum Testen bei euch in ein eigenes Verzeichnis schreiben und dort mit

javac -classpath /net/gna/jGABL/jGABL.jar:. PrintAdjacencyList.java

übersetzen und mit

java -classpath /net/gna/jGABL/jGABL.jar:. PrintAdjacencyList /net/gna/graphs/graph_comp.1.gml

z.B. für den Beispielgraphen graph_comp.1.gml ausführen.

Scheinkriterien

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

Informatikstudenten, die einen benoteten Übungsschein erwerben möchten, müssen ferner gegen Ende der Vorlesungszeit an einer Rücksprache bei Prof. Grötschel teilnehmen. Die Note setzt sich zu je 50% aus den Noten der Rücksprache und der schriftlichen Hausaufgaben zusammen.

Valid HTML 4.0! Zuletzt aktualisiert: 20. September 2006