|
Graphen- und Netzwerkalgorithmen |
|
|
Sommersemester 2000 |
|
LV-Nr.: 0350 L 148
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
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:
- 1. Übungsblatt vom 18.04.00 (ps, pdf)
- 2. Übungsblatt vom 25.04.00 (ps, pdf)
- 3. Übungsblatt vom 02.05.00 (ps, pdf)
- 4. Übungsblatt vom 09.05.00 (ps, pdf)
- 5. Übungsblatt vom 16.05.00 (ps, pdf)
- 6. Übungsblatt vom 23.05.00 (ps, pdf)
- 7. Übungsblatt vom 30.05.00 (ps, pdf)
- 8. Übungsblatt vom 06.06.00 (ps, pdf)
- 9. Übungsblatt vom 13.06.00 (ps, pdf)
- 10. Übungsblatt vom 20.06.00 (ps, pdf)
- 11. Übungsblatt vom 27.06.00 (ps, pdf)
- 12. Übungsblatt vom 04.07.00 (ps, pdf)
- 13. Übungsblatt vom 11.07.00 (ps, pdf)
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.
Zuletzt aktualisiert: 13. Juli 2000