|
Graphen- und Netzwerkalgorithmen
(ADM I) |
|
|
Sommersemester 2009 |
|
LV-Nr.: 0230 L 148
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
- 1. Übungsblatt (pdf)
Übungsaufgabe 1 als Spiel!
- 2. Übungsblatt (pdf)
- 3. Übungsblatt (pdf)
- 4. Übungsblatt (pdf)
- 5. Übungsblatt (pdf)
- 6. Übungsblatt (pdf)
- 7. Übungsblatt (pdf)
- 8. Übungsblatt (pdf)
- 9. Übungsblatt (pdf)
- 10. Übungsblatt (pdf)
Die Graphen findet ihr nun weiter unten.
- 11. Übungsblatt (pdf)
- 12. Übungsblatt (pdf)
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.
Zuletzt aktualisiert: 28. Septermber 2009