Fortgeschrittene Diskrete Optimierung WS 06/07

Aktuelle Informationen und Hinweise

Das elfte Übungsblatt ist da.
Am 22.12.06 findet keine große Übung statt.
Link zu einem Java-Applet, das den Push-Relabel-Algorithmus und den Ford-Fulkerson-Algorithmus ausführt (siehe Links).
Aufgrund der Ausfallempfehlung findet am Donnerstag (23.11.) die Vorlesung nicht statt.
Die Vorlesung am Dienstag ist in den SN 20.2 verlegt worden.
Der Semesterapparat ist zusammengestellt (siehe unten).
Die Scheinklausur findet statt am 16.02.07 um 15.00 in Raum ZI 24.1 (Grotrian).
Übungsblätter werden über diese Seite verfügbar sein - siehe unten.
Erste Vorlesung am 2. November; erste große Übung am 3. November; kleine Übungen am 21. November.
Literaturhinweise hängen unten.
Für diese Vorlesung gibt es eine eigene Mailingliste. (Die Liste aus dem Vorsemester wird fortgeführt!) Wer dort noch nicht angemeldet war: Das Anmeldeformular findet man hier. Nach der Anmeldung erhält man eine Mail an die eingegebene Adresse. Damit man sich nur selbst anmelden kann, muss man von dieser Adresse noch eine Bestätigung abschicken. Das klappt normalerweise ganz einfach, indem man "reply" drueckt und die Sache abschickt. Bei technischen Schwierigkeiten bitte eine Mail an mich!

Allgemeine technische Hinweise

Die Vorlesung wendet sich an Studierende im Hauptstudium. Kenntnisse aus der `` Einführung in die Optimierung'' und der Vorlesung
`` Konvexe und Diskrete Optimierung'' werden zwar vorausgesetzt, sind aber nur an einzelnen Stellen notwendig. In dieser Vorlesung wird der diskrete Teil der Veranstaltung ``Konvexe und Diskrete Optimierung'' wieder aufgegriffen und vertieft.
Die Scheinvergabe erfolgt aufgrund einer Klausur am Ende des Semesters und der auf den Hausaufgabenblättern erzielten Punkten.
Details zum Übungsbetrieb werden demnächst bekanntgegeben.
Falls es speziellere Fragen, individuelle Schwierigkeiten oder Unklarheiten gibt, so bitte ich ganz einfach um eine Nachfrage; das geht sehr gut per Mail, aber auch in Person nach der Vorlesung oder in meiner Sprechstunde. (Gerade Unklarheiten betreffen oft noch mehrere Teilnehmer, daher bin ich für Nachfragen durchaus dankbar!)

Inhaltliche Hinweise

Im Verlaufe des Semesters werden folgende Themen behandelt:

Netzwerkflüsse
Kostenminimale Flüsse
Matching
Kostenminimales Matching
Ggf. weitere Themen, z.B.: Matroide, Approximationsalgorithmen, Traveling Salesman, Steinerbäume, Anwendungen, aktuelle Forschungsthemen

Im Sommersemester '07 ist die Möglichkeit zur Seminarteilnahme sowie eine Spezialvorlesung geplant. Im Anschluss daran können u.U. Diplomarbeiten vergeben werden.

Termine

Vorlesung:	Dienstag	16.45 - 18.15 Uhr	SN 20.2	Sándor Fekete
	Donnerstag	09:45 - 11:15 Uhr	PK 4.1	Sándor Fekete
Große Übung:	Freitag	11:30 - 13:00 Uhr	PK 4.4	Nils Schweer
Kleine Übung:	Dienstag	08.00 - 09.30 Uhr	F 315	Martin Lorek
	Dienstag	11.30 - 13.00 Uhr	PK 4.4	Susanne Ruppert

Sprechstunden:

		Sprechstunde	Raum	Telefon	email
Dozent:	Sándor Fekete	Di 11:15 - 12:00 Uhr	F 524	391-7551	sandor.fekete AT tu-bs.de
Assistent:	Nils Schweer	Di 10.00 - 11.30 Uhr	F 523	391-7562	n.schweer AT tu-bs.de
Tutoren:	Susanne Ruppert	n.V.	n.V.		s.ruppert AT tu-bs.de
	Martin Lorek	n.V.	n.V.		martinlorek AT web.de

Übungsblätter

1. Übung [ Postscript , PDF ]

2. Übung [ Postscript, PDF ]

3. Übung [ Postscript , PDF ]

4. Übung [ Postscript, PDF ]

5. Übung [ Postscript, PDF ]

6. Übung [ Postscript, PDF ]

7. Übung [ Postscript, PDF ]

8. Übung [ Postscript, PDF ]

9. Übung [ Postscript, PDF ]

10. Übung [ Postscript, PDF ]

11. Übung [ Postscript, PDF ]

Literatur und Links

Skripte:

Verschiedene Skripte zur Optimierung

Links

Java-Applet zum Push-Relabel-Algorithmus und zum Ford-Fulkerson-Algorithmus.
(Zum Ausführen des Applets benötigt man das Java Runtime Environment.)
Hier findet man den Artikel zum Snow-Blower-Problem vom 7. Übungblatt.

Bücher:

Korte, Vygen: Combinatorial Optimization, Springer-Verlag, 2002. ( Im Semesterapparat der BMI)
Cook, Cunningham, Pulleyblank, Schrijver: Combinatorial Optimization, Wiley Interscience, 1998. ( Im Semesterapparat der BMI)
Lawler: Combinatorial Optimization, Dover 2001; Original von 1976.
Papdimitriou, Steiglitz: Combinatorial Optimization, Dover 1998; Original von 1988.
Schrijver: Combinatorial Optimization (3 Bände), Springer-Verlag, 2003.

Hauptsächlich werde ich mich auf das Buch von Korte und Vygen stützen.

Last update: Thu Feb 22 10:57:51 CET 2007

<sandor.fekete AT tu-bs.de>