Einführung in die Optimierung SS '04

Aktuelle Informationen und Hinweise

Es lohnt sich, diese Seite im Auge zu behalten!
Die Klausurergebnisse sind unten eingehängt. Die Klausur selber ist ebenfalls verfügbar.
Drei alte Klausuren hängen unten. (Man beachte, dass zwei davon zur Linearen Optimierung gehören, also zu der Vorlesung des kommenden Semesters. Sie sollten aber zum Teil trotzdem eine Vorstellung geben, wie die Sache ungefähr aussehen könnte!)
Literaturhinweise hängen unten.
Für diese Vorlesung gibt es eine eigene Mailingliste. Das Anmeldeformular finden Sie 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 Bestaetigung abschicken. Das klappt normalerweise ganz einfach, indem man "reply" drueckt und die Sache abschickt. Bei technischen Schwierigkeiten bitte eine Mail an mich!
Es ist vorgesehen, für diese Vorlesung drei Kleingruppen anzubieten, die alle mittwochs stattfinden werden.
Die Klausur findet statt am 24.07., 12:00-15:00 im Audimax. Anschließend gibt es die traditionelle Grillfete der Optimierung, an der neben den Teilnehmern verschiedener Vorlesungen (Einführung in die Optimierung, Diskrete Optimierung, Online Algorithms) auch die Diplomanden, Hilfskräfte, Mitarbeiter und Professoren in ungezwungener Atmosphäre dabei sind.

Allgemeine technische Hinweise

Die Vorlesung wendet sich an Studierende ab dem vierten Semester. Kenntnisse der Analysis I und II sowie der Linearen Algebra werden vorausgesetzt.
Scheinvoraussetzung ist die erfolgreiche Teilnahme am Übungsbetrieb der Vorlesung. Dieser Erfolg wird durch Bestehen einer Klausur am Ende des Semesters nachgewiesen. Ausreichende Übungspunkte sind dafür erfahrungsgemäß unerläßlich.
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 mehr Teilnehmer, daher bin ich für Nachfragen durchaus dankbar!)

Inhaltliche Hinweise

Im Verlaufe des Semesters werden Themen aus folgenden Bereichen behandelt:

Diskrete Optimierung
Lineare Optimierung
Nichtlineare Optimierung

Da es sich um eine Einführung handelt, werden alle drei genannten Gebiete nur angerissen. Für Interessenten besteht in den darauffolgenden Semestern die Möglichkeit, sich in den weitergehenden Vorlesungen Optimierung I und II tiefer in die Materie einzuarbeiten. Daran anschließend können nach erfolgreichem Absolvieren eines Seminars auch Diplomarbeitsthemen vergeben werden.

Termine

Vorlesung:	Dienstag	09:45 - 11:15 Uhr	PK 11.2	Sándor Fekete
	Donnerstag	09:45 - 11:15 Uhr	PK 4.1	Prof. Dr. Sándor Fekete
Große Übung	Donnerstag	15:00 - 16:30 Uhr	PK 2.2	Dr. Laura Heinrich-Litan
Übungsgruppen	Mittwoch	09:45 - 11:15 Uhr	PK 14.3	Inga Hafemann
	Mittwoch	11:30 - 13:00 Uhr	PK 3.1	Nils Schweer
	Mittwoch	13:15 - 14:45 Uhr	SN 23.2	Ulla Neumann

Sprechstunden:

		Sprechstunde	Raum	Telefon	email
Dozent:	Prof. Dr. Sándor Fekete	Di 11:15 - 12:00 Uhr	F 524	391-7551	sandor.fekete AT tu-bs.de
Assistentin:	Dr. Laura Heinrich-Litan	n.V.	F 302	391-7561	litan AT tu-bs.de
Korrektoren:	Inga Hafemann	per Mail	n.V.	-	i.hafemann AT tu-bs.de
	Ulla Neumann	per Mail	n.V.	-	u.neumann.de AT tu-bs.de
	Nils Schweer	per Mail	n.V.	-	n.schweer AT tu-bs.de

Übungsblätter

1. Übung [ Postscript, Postscript (gzipped), PDF ]

Das Städtebild in groß.

2. Übung [ Postscript, Postscript (gzipped), PDF ]

3. Übung [ Postscript, Postscript (gzipped), PDF ]

4. Übung [ Postscript, Postscript (gzipped), PDF ]

5. Übung [ Postscript, Postscript (gzipped), PDF ]

6. Übung [ Postscript, Postscript (gzipped), PDF ]

7. Übung [ Postscript, Postscript (gzipped), PDF ]

8. Übung [ Postscript, Postscript (gzipped), PDF

9. Übung [ Postscript, Postscript (gzipped), PDF ]

10. Übung [ Postscript, Postscript (gzipped), PDF ]

11. Übung [ Postscript, Postscript (gzipped), PDF ]

12. Übung [ Postscript, Postscript (gzipped), PDF ]

13. Übung [ Postscript, Postscript (gzipped), PDF ]

Klausur ``Einführung in die Optimierung'', SS 2004; [ Postscript, Postscript (gzipped), PDF ]

Klausurergebnis: [ Postscript, Postscript (gzipped), PDF ]

Alte Klausuren:

Klausur ``Einführung in die Optimierung'', SS 2002; [ Postscript, Postscript (gzipped), PDF ]

Klausur ``Lineare Optimierung'', WS 2002/03; [ Postscript, Postscript (gzipped), PDF ]

Klausur ``Lineare Optimierung'', WS 2003/04; [ Postscript, Postscript (gzipped), PDF ]

Literatur und Links

Wird laufend ergänzt!

Verschiedene Skripten zur Optimierung

Eine Textdatei CPLEX-Einführung

Eine Beispieldatei

Bücher:

B. Korte, J. Vygen Combinatorial Optimization, Springer-Verlag, 2003.
V. Chvatal, Linear Programming, Freeman, New York, 1983.
G.B. Dantzig, Linear Programming and Extensions, Princeton U. Press, Princeton, 1963.
M. Padberg, Linear Optimization and Extensions, Springer-Verlag, Berlin, 1995.
A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, New York, 1986.
D.G. Luenberger, Linear and Nonlinear Programming, Addison-Wesley, Reading, 1984.

Als Erzählbuch zum kurzweiligen Lesen (Niveau ist eher Oberstufe/Studienanfang):
P. Gritzmann, R. Brandenberg, Das Geheimnis des kürzesten Weges, Springer-Verlag, Berlin, 2002.
Eine sehr schöne Sammlung von Links zum Buch, übersichtlich gegliedert nach Themen

Ein schönes elektronisches Skript aus Wien. Die Seiten zur linearen Optimierung geben einen ganz guten Überblick mit vielen Bildern.

Eine interaktive Visualisierung des Dijkstra-Algorithmus.

Für die besonders Wissbegierigen: Eine gut strukturierte Darstellung von Fibonacci Heaps, der raffinierten Datenstruktur, mit der man Dijkstras Algorithmus auf eine Laufzeit von O(n log n + m) drücken kann.

Der Originalartikel von Fredman und Tarjan von 1987.

Der Originalartikel von Chazelle zu Minimum Spanning Trees von 2000.

Die Homepage von Bernard Chazelle.

Eine Seite über Alan Turing.

Was ist eine Turing-Maschine?.

Virtuelle Turing-Maschine.

Ein ausführlicher Lexikon-Eintrag zu NP-Vollständigkeit.

Ein Lexikoneintrag zu George Dantzig.

Eine Anwortliste zu Linearer Optimierung. (Englisch, sehr viele Details zu Software, Litereatur etc.)

Die entsprechende Liste zu Nichtlinearer Optimierung.

Eine Linksammlung zu Polytopen und Polyedern.

Beweise für die Euler-Formel.