Zur
  Seite der TU

Graphen- und Netzwerkalgorithmen

(ADM I)

Zur Seite des Instituts für Mathematik
 

Sommersemester 2009

 
LV-Nr.: 0230 L 148
 

Prof. Dr. Dr. h.c. mult. Martin Grötschel
 


Aktuelles

(27.08.2009) Die letzte Überarbeitung des Vorlesungsskriptums ist erfolgt. Es ist fertig und wird ab jetzt nicht mehr geändert oder ergänzt.

(13.07.2009) Die Scheine werden in der letzten Übung (16.07.) gegen Vorlage eines Ausweises ausgehändigt. Danach kann man die Scheine bei Frau Ewel (MA 310) abholen. Bei Rückfragen wendet euch bitte an Rüdiger.

(05.06.2009) Prüfungstermine bietet Prof. Grötschel in der letzten Vorlesungswoche und ersten vorlesungsfreien Woche dieses Semesters und in der ersten Vorlesungswoche des nächsten Semesters an. Diejenigen, die sich prüfen lassen möchten, schicken bitte bis spätestens 30. Juni 2009 eine Email an Rüdiger (wenn möglich, mit Angabe eines Wunschtermins). Eine Festlegung der Prüfungstermine findet Anfang Juli statt.

(14.05.2009) Das Infoblatt und diese Webseite ist bzgl. der Scheinkriterien überarbeitet worden. Die Scheinkriterien werden für alle Studenten einheitlich gehandhabt.


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

Sehr zu empfehlen: Java oder C/C++


Geplante Fortsetzung

Diese Vorlesung ist die Einführungsveranstaltung 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 (ADM II) fortgesetzt.

Ferner möchten wir an dieser Stelle auf eine weitere Veranstaltung von Prof. Grötschel hinweisen, für die aber Kenntnisse der Linearen Programmierung erforderlich sind:


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 : Das Skript zur Veranstaltung finden Sie hier.


Kontakte

   
Sprechstunde
Raum Telefon email
Dozent: Prof. Dr. Dr. h.c. mult. Martin Grötschel n.V. MA 302 84185-210 groetschel 'at' zib.de
Assistent: Rüdiger Stephan n.V. MA 308 314-28 323 stephan 'at' math.tu-berlin.de
Tutorin: Janina Müttel MO, 12-14 MA 241 --- muettel 'at' math.tu-berlin.de
Sekretariat (TU): Claudia Ewel nV. MA 310 314-28 478 ewel 'at' math.tu-berlin.de
Sekretariat (ZIB): Bettina Kasse n.V. 3025 84185-209 kasse 'at' zib.de


Zeiten

Vorlesung: Di 12:15 - 13:45 MA 041 Prof. Dr. Dr. h.c. mult. Martin Grötschel
Fr 10:15 - 11:45 MA 041
Übung: Do 10:15 - 11:45 MA 041 Rüdiger Stephan
Tutorien: Mo 10:15 - 11:45 MA 851 Janina Müttel
Mi 10:15 - 11:45 MA 742
Rechnerbetreuung: Mo 12:00 - 14:00 MA 241 (Westsaal) Janina Müttel
Mo 14:00 - 16:00 MA 241 (Westsaal) Rüdiger Stephan
Do 14:15 - 15:45 MA 241 (Hauptsaal) Rüdiger Stephan
Rechnervorrangzeiten: Mo 12-18 MA 241 (Westsaal)
Do 14-16 MA 241 (Hauptsaal)


Übungsblätter


Programmieraufgaben

Die für diesen Kurs zu lösenden Programmieraufgaben sollen in Java oder C/C++ implementiert werden. Anfängern wird Java empfohlen.


Materialien zu den Programmieraufgaben


Sonstige Materialien


Scheinkriterien

Wer einen unbenoteten Schein erwerben möchte, hat folgende Kriterien zu erfüllen:

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.


Valid HTML 4.0! Zuletzt aktualisiert: 28. Septermber 2009