Graphen- und Netzwerkalgorithmen

(Sommersemester 1999)

PD Dr. Alexander Martin Ekkehard Köhler Georg Baier

Termine

Vorlesungen:	Dienstag	16-18 Uhr	MA 043	Alexander Martin
Vorlesungen:	Donnerstag	16-18 Uhr	MA 043	Alexander Martin
Übung:	Mittwoch	8-10 Uhr	MA 043	Ekkehard Köhler
Tutorium:	Montag	10-12 Uhr	MA 750	Georg Baier
Tutorium:	Freitag	10-12 Uhr	MA 848	Georg Baier

Sprechzeiten

Ansprechpartner	Raum	Zeit	Telefon	email
PD Dr. Alexander Martin		n.V.	841-85 211	martin@zib.de
Ekkehard Köhler	MA 613	n.V.	314-25 735	ekoehler@math.tu-berlin.de
Georg Baier	MA 613	n.V.	314-25 735	baier@math.tu-berlin.de
Sekretariat	MA 601	Mo, Di, Do, Fr 9:30-11:30 Uhr	314-25 728	marcus@math.tu-berlin.de

Rechnervorrangzeiten

(Unix-Pool MA 241)

Tag	Zeit
Dienstag	9-12 Uhr
Mittwoch	14-16 Uhr
Donnerstag	14-16 Uhr

Zu diesen Zeiten wird Teilnehmern der Lehrveranstaltung ein Rechnerplatz garantiert.

Literatur

Als Lektüre zur Vertiefung und Erweiterung des Vorlesungsstoffes verweisen wir auf folgende Bücher:

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. Corman, C.E. Leiserson, R.R. Rivest: "Introduction to Algorithms", The MIT Press, Cambridge, 1990

Darüber hinaus empfehlen wir jedem Teilnehmer der Vorlesung, weitere Literatur per Datenbankrecherche zu suchen. Eine komfortable Möglichkeit dazu bietet die MATH Database in Karlsruhe, die über WWW verfügbar ist. Eine Liste anderer interessanter Links zum Thema kann man hier finden.

The LEDA User Manual

Übungsblätter

Im Laufe des Semesters wird jede Woche an dieser Stelle ein Übungsblatt zur Verfügung gestellt. Insgesamt werden voraussichtlich 12 Übungsblätter zu bearbeiten sein. Die Bearbeitungszeit beträgt eine Woche. Die Abgabe erfolgt eine Woche nach der Ausgabe vor der Übung.

Hier sind die LaTeX-Files der Übungsblätter:

1. Übungsblatt (LaTeX, dvi, postscript)

2. Übungsblatt (LaTeX, dvi, postscript)

3. Übungsblatt (LaTeX, dvi, postscript)

4. Übungsblatt (LaTeX, dvi, postscript, Abbildung als eps Datei)

5. Übungsblatt (LaTeX, dvi, postscript, Abbildung 1. als eps Datei, Abbildung 2. als eps Datei)

6. Übungsblatt (LaTeX, dvi, postscript)

7. Übungsblatt (LaTeX, dvi, postscript, Abbildung als eps Datei)

8. Übungsblatt (LaTeX, dvi, postscript)

9. Übungsblatt (LaTeX, dvi, postscript, Abbildung als pstex Datei und pstex_t Datei)

10. Übungsblatt (LaTeX, dvi, postscript, Abbildung als eps Datei)

11. Übungsblatt (LaTeX, dvi, postscript)

12. Übungsblatt (LaTeX, dvi, postscript)

Hinweise zur Behandlung der LaTeX-Files.

Programmieraufgaben

Es wird 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.

Hier wird es Informationen zu den einzelnen Programmieraufgaben geben:

1. Programmieraufgabe

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 der Übung vorausgesetzt.

University | Department | Group | FTP

Last modified: Tue Apr 16 1999

Ekkehard Köhler <ekoehler@math.tu-berlin.de>