|
Graphen- und Netzwerkalgorithmen
(ADM I)
|
|
|
Sommersemester 2004
|
|
LV-Nr.: 0230 L 148
Inhalt
Algorithmen für grundlegende graphentheoretisch formulierbare
Probleme, Netzwerkflussalgorithmen, Modellierung, Anwendungen.
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
S. Hougardy:
Algorithmische Diskrete Mathematik I
Vorlesungsskript 2004
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
Algorithmische
Diskrete Mathematik 1
Vorlesungsskript 2003
S. Hougardy, H.J.Prömel
Graphen
und Algorithmen 1
Vorlesungsskript 2003
D. Jungnickel:
Graphen, Netzwerke und Algorithmen, BI 1994
B. Korte, J. Vygen:
Combinatorial Optimization, Theory and Algorithms, Springer, 2000 (2.
Auflage, 2002)
A. Schrijver:
Combinatorial Optimization, Springer, 2003
Kontakte
|
|
Sprechstunde
|
Raum |
Telefon |
email |
Dozent: |
Prof. Dr.
Stefan Hougardy |
n.V. |
MA 620 |
314-25748 |
hougardymath.TU-Berlin.de |
Assistent: |
Patrick
Baier |
n.V. |
MA 652 |
314-29386 |
baierpkmath.tu-berlin.de |
Tutor: |
Anton Telle |
n.V. |
|
|
antonjustmail.de |
Sekretariat: |
Elke Pose |
Mo - Do 9:30 - 11:30 Uhr |
MA 627 |
314-23354 |
posemath.tu-berlin.de |
Zeiten
Übungsblätter
1. Übungsblatt (20.04.04)
[ps]
2. Übungsblatt (27.04.04)
[ps]
3. Übungsblatt (04.05.04)
[ps]
4. Übungsblatt (11.05.04)
[ps]
5. Übungsblatt (18.05.04)
[ps]
6. Übungsblatt (25.05.04)
[ps]
7. Übungsblatt (01.06.04)
[ps]
8. Übungsblatt (08.06.04)
[ps]
9. Übungsblatt (15.06.04)
[ps]
10. Übungsblatt (22.06.04)
[ps]
11. Übungsblatt (29.06.04)
[ps]
12. Übungsblatt (06.07.04)
[ps]
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.
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.
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: 22. Juli 2004