Graphen- und Netzwerkalgorithmen (SS04)

	Graphen- und Netzwerkalgorithmen (ADM I)
	Sommersemester 2004

LV-Nr.: 0230 L 148

Prof. Dr. Stefan Hougardy

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

Vorlesung:	Di	16:15 - 17:45	MA 042	Prof. Dr. Stefan Hougardy
Vorlesung:	Fr	10:15 - 11:45	MA 042	Prof. Dr. Stefan Hougardy
Übung:	Fr	14:15 - 15:45	MA 041	Patrick Baier
Tutorien:	Mi	16:15 - 17:45	MA 651	Patrick Baier
	Do	10:15 - 11:45	MA 848	Prof. Dr. Stefan Hougardy

Ü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.

Dokumentation zu jGABL
Dokumentation zu Java im Unix-Pool (unter Programmiersprachen)
Java 1.2 Dokumentation
Anfängern sei zudem das Java Tutorial empfohlen (bzw. außerhalb des TU-Netzes direkt von Sun).

jGABL für Zuhause: http://www.math.tu-berlin.de/jGABL.

Beispielprogramme

PrintAdjacencyList.java

AnimatedDFS.java

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.

$Valid HTML 4.0!$ Zuletzt aktualisiert: 22. Juli 2004

Graphen- und Netzwerkalgorithmen

(ADM I)

Sommersemester 2004