|
Graphen- und Netzwerkalgorithmen
(ADM I) |
|
|
Sommersemester 2003 |
|
LV-Nr.: 0230 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.
Zur Vertiefung der Themen aus der Vorlesung ``Graphen- und Netzwerkalgorithmen''
wird im Wintersemester 2003/2004 ein Seminar über
Matchings, Flüsse und Verallgemeinerungen
angeboten.
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
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
(2. Auflage, 2002)
A. Schrijver:
Combinatorial Optimization, Springer, 2003
Vorlesungsskriptum (aktualisierte Version vom 21. August 2003, Kapitel 1 - 12,
ps-File, pdf-File)
Kontakte
|
|
Sprechstunde
|
Raum |
Telefon |
email |
Dozent: |
Prof. Dr. Martin Grötschel |
n.V. |
MA 302 |
84185-210 |
groetschelzib.de |
Assistent: |
Dr. Frank Lutz |
Do 10:00 - 11:30 Uhr |
MA 624 |
314-25 751 |
lutzmath.tu-berlin.de |
Tutoren: |
Dr. Vanessa Kääb |
Do 13:30 - 15:00 Uhr |
MA 613 |
314-25 735 |
kaeaebmath.tu-berlin.de |
Daniel Schmidt |
s. Rechnerbetreuung |
|
|
schmidtpool.math.tu-berlin.de |
Sekretariat (TU): |
Elke Pose |
Mo - Do 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 |
14:15 - 15:45 |
MA 041 |
Übung: |
Do |
16:00 - 17:30 |
MA 043 |
Dr. Frank Lutz |
Tutorien: |
Mo |
12:15 - 13:45 |
MA 744 |
Daniel Schmidt |
Di |
10:05 - 11:35 |
MA 744 |
Dr. Vanessa Kääb |
Di |
12:15 - 13:45 |
MA 744 |
Rechnerbetreuung: |
Mo |
10:15 - 11:45 |
Unix Pool |
Daniel Schmidt |
Mo |
16:15 - 17:45 |
Unix-Pool |
Übungsblätter:
- 1. Übungsblatt vom 15.04.03 (ps, pdf) ---> Aufgabe 1 als Spiel!
- 2. Übungsblatt vom 22.04.03 (ps, pdf)
- 3. Übungsblatt vom 29.04.03 (ps, pdf)
- 4. Übungsblatt vom 06.05.03 (ps, pdf)
- 5. Übungsblatt vom 13.05.03 (ps, pdf)
- 6. Übungsblatt vom 20.05.03 (ps, pdf)
- 7. Übungsblatt vom 27.05.03 (ps, pdf)
- 8. Übungsblatt vom 03.06.03 (ps, pdf)
- 9. Übungsblatt vom 10.06.03 (ps, pdf)
- 10. Übungsblatt vom 17.06.03 (ps, pdf)
- 11. Übungsblatt vom 24.06.03 (ps, pdf)
- 12. Übungsblatt vom 01.07.03 (ps, pdf)
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
- Aufgabe 1: Zusammenhangsberechnung
- Aufgabe 2: Algorithmen von Kruskal und Prim
- Aufgabe 5, Teil 1: Maximale Flüsse
- Aufgabe 5, Teil 2: Kostenminimale Flüsse
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 aus der Übung und unter /net/gna/graphs gibt
es Beispielgraphen für die 1. Programmieraufgabe.
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.
Zuletzt aktualisiert: 26. Februar 2004