Kombinatorische Optimierung 1 (502.636/502.637)
Wintersemester 2013/14
Bettina Klinz
Termine der Lehrveranstaltung
Sprechstunden/Betreuung
Inhalt und Ziel der Lehrveranstaltung
Literatur
On-Line Materialien
Übungsbeispiele
Hausübungsbeispiele
Prüfung/Zeugnisse
Termine der Lehrveranstaltung
Tag | Zeit | Raum | Periode |
Montag | 11:15-13:00 | BE01 |
7. Oktober 2013 - 20. Jänner 2014 |
Donnerstag | 12:15-14:00 | BE01 |
3. Oktober 2013 - 23. Jännner 2014 |
Die teilweise Verlängerung der Vortragszeiten um 15 Minuten
soll ausfallende Einheiten ausgleichen sowie der Tatsache gerecht werden, dass nur 14 Montage zur Verfügung stehen.
Achtung: Vorlesung und Übung sind nicht strikt getrennt, die
Übungen werden je nach Bedarf in die Lehrveranstaltung eingebunden.
Sprechstunden
Um den Bedürfnissen unterschiedlicher Gruppen von Studierenden
möglist gut entgegenzukommen, habe ich
keine fixen Sprechstunden. Wenn Sie Fragen haben,
so sprechen Sie mich bitte entweder im Anschluß an die
Lehrveranstaltung an, oder senden Sie mir eine e-mail an
klinz@opt.math.tu-graz.ac.at,
oder kommen Sie in meinem Büro vorbei (Gefahr, daß ich gerade
keine Zeit habe oder nicht hier bin), oder vereinbaren Sie einen Termin
(angeraten für umfangreichere Fragen).
Inhalt und Ziel der Lehrveranstaltung
Die Lehrveranstaltung soll eine Einführung in das Gebiet der
kombinatorischen Optimierung geben.Der Schwerpunkt liegt auf polynomiell
lösbaren kombinatorischen Optimierungsproblemen (NP-schwere kombinatorische Optimierungsprobleme werden schwerpunktsmäßig in der neuen LV
kombinatorische Optimierung 2 behandelt). Die Lehrveranstaltung
kombinatorische Optimierung 1 entspricht
der alten LV kombinatorische Optimierung des Diplomstudiums technische
Mathematik.
Geplant ist die Behandlung der folgenden Themengebiete:
- Einführende Beispiele
- Kurzeinführung in für die Vorlesung benötigte Begriffe
der Komplexitätstheorie
- Minimale spannende Baumprobleme und verwandte Problemstellungen
- Arboreszenzen mit minimalen Gewicht
- Kürzeste Wegeprobleme
- Maximale Flußprobleme
- Minimale Kostenflußprobleme
- Matchingprobleme
Literatur
Der Lehrveranstaltung liegt weder ein Lehrbuch noch ein Skriptum zugrunde.
Im Laufe der Vorlesung werden Hinweise zu relevanter Literatur und
zu Begleitmaterialien und zu Software gegeben.
Lehrbücher und Monographien
Einen guten Überblick über das Gebiet der kombinatorischen
Optimierung geben die folgenden 4 Bücher:
-
W.J. Cook, W.H. Cunningham, W.H. Pulleyblank, A. Schrijver,
Combinatorial Optimization,
Wiley-Interscience, John Wiley & Sons, New York, 1998, 355 pages,
ISBN 0-471-55894-X.
(Leicht lesbares, und dennoch modernes Lehrbuch,
deckt weniger Gebiete ab als das Buch von Korte und Vygen.)
-
B. Korte, J. Vygen, Combinatorial Optimization,
Springer Verlag, Berlin, Heidelberg, New York, 2nd edition, 2002, 530 pages,
ISBN 3-540-43154-3.
(Sehr umfassende Monographie)
- A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency,
Springer Verlag, Berlin, Heidelberg, New York, 2003, 3 volumes (Volume A: 648 pages, Volume B: 570 pages, Volume C: 664 pages),
ISBN: 3-540-44389-4.
(Extrem umfassendes Werk zur kombinatorischen Optimierung, besonderer Schwerpunkt auf polyedrischen Resultaten und effizienten Algorithmen, über 400 Referenzen, fast 2000 Seiten - ein Lebenswerk)
Das folgende Buch gibt einen umfassenden Einblick in das Gebiet der
Netzwerkflußpprobleme, eines Teilgebietes der kombinatorischen
Optimierung.
-
R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications,
Prentice Hall, Englewood-Cliffs, New Jersey, 1993, 864 pages,
ISBN 0-13-617549-X.
Ferner sollten an dieser Stelle auch noch die beiden folgenden
klassischen, allerdings schon etwas älteren
Bücher genannt werden:
-
C. Papadimitriou, K. Steiglitz, Combinatorial
Optimization: Algorithms and Complexity,
Dover Publications, Inc, 1988, 496 pages, ISBN
0-486-40258-4.
(Corrected, unabridged republication of the original edition
that was published in 1982 by Prentice Hall, Englewood Cliffs, New Jersey
and has been out of print for several years.)
Bibliographien
Die folgenden beiden annotierten Bibliographien enthalten viele
weitere Literaturreferenzen zur kombinatorischen Optimierung:
-
M.O'hEigeartaigh, J.K. Lenstra, A.H.G. Rinnooy Kan (eds.),
Combinatorial Optimization: Annotated Bibliographies,
Wiley, New York, 1985.
-
M. Dell'Amico, F. Maffioli, S. Martello (eds),
Annotated Bibliographies in Combinatorial Optimization,
Wiley-Interscience, John Wiley & Sons, New York, 1997,
495 pages, ISBN 0-471-96574-X.
(deckt ca. den Zeitraum 1985-1997 ab).
On-Line Materialien
Einige weitere Links im weiteren Umfeld der kombinatorischen
Optimierung finden sich auch
unter den Links auf meiner im Aufbau befindlichen
Linkliste zur mathematischen Optimierung.
Übungsbeispiele
Im Laufe der Vorlesung werden Übungsblätter mit
Übungsbeispielen ausgegeben bzw. auf dieser WWW-Seite zur
Verfügung gestellt. Die Studierenden sollten den Versuch
unternehmen diese Aufgaben selbständig zu lösen, um
ein besseres Durchdringen und Verstehen des Lehrstoffes zu erzielen.
Eine Auswahl der Beispiele wird in den Übungsstunden behandelt.
Aktive Beteiligung der Studierenden an der Lösung der Aufgaben
ist erwünscht.
Übungsblätter
Übungsaufgaben Teil 1 (Seiten 1-4)
PostScript file
Adobe pdf file
(Ausgeteilt am 14.10. 2013)
Übungsaufgaben Teil 2 (Seiten 5-8)
PostScript file
Adobe pdf file
(Ausgeteilt am 28.10. 2013)
Übungsaufgaben Teil 3 (Seiten 9-12)
PostScript file
Adobe pdf file
(Ausgeteilt am 14.11. 2013)
Übungsaufgaben Teil 4 (Seiten 13-16)
PostScript file
Adobe pdf file
(Ausgeteilt am 25.11. 2013)
Übungsaufgaben Teil 5 (Seiten 17-20)
PostScript file
Adobe pdf file
(Ausgeteilt am 16.12. 2013)
Übungsaufgaben Teil 6 (Seiten 21-24)
PostScript file
Adobe pdf file
(Ausgeteilt am 16.1. 2014)
Anmerkungen zu den Übungsblättern
Es werden nicht alle Aufgaben auf den Übungsblättern in
den Übungen behandelt. Die nicht behandelteten Aufgaben
sollen Sie ermutigen,
sich in weiterführender Weise selbständig mit dem
Stoff der Lehrveranstaltung auseinanderzusetzen bzw. Ihnen die
Möglichkeit geben, zu überprüfen, ob Sie den
Stoff verstanden haben.
Bei Fragen zu nicht behandelten Aufgaben, wenden Sie sich bitte an
mich (per e-mail oder
persönlich).
Hausübungsbeispiele
Die Bearbeitung
der Hausaufgaben ist verpflichtend für den Erwerb eines
Übungszeugnisses. Die Aufgaben sollen eigenständig bearbeitet
werden. Weitere Details siehe Angabeblatt.
Hausübungsaufgaben
PostScript file
Adobe pdf file
(Ausgeteilt am 20.1. 2014)
Prüfung/Zeugnisse
Form der Prüfung
Die Prüfung ist zweiteilig und besteht aus einem schriftlichen und
einem mündlichen Teil. Das Ergebnis der schriftlichen Prüfung
wird in die Ermittlung der Vorlesungsnote und der Übungsnote einbezogen.
Das Ergebnis der mündlichen Prüfung zählt nur für die
Vorlesungsnote.
Anmerkungen zur schriftlichen Prüfung
Die schriftliche Prüfung wird sich im
Schwierigkeitsgrad an den Übungsaufgaben mittlerer Schwierigkeit.
Rechnen Sie mit einer Verständnisfrage, die aus mehreren Behauptungen
besteht, deren Wahr- bzw. Falschheit zur Diskussion steht (es ist
ein Beweis oder ein Gegenbeispiel anzugeben). Solche Aufgaben werden
auch in den Übungen behandelt werden.
Es wird kein Wert auf mechanisches Rechnen gelegt.
Der zur Verfügung gestellte Zeitrahmen für die
schriftliche Prüfung ist großzügig bemessen.
Bei der schriftlichen Prüfung sind sämtliche schriftlichen
Unterlagen zugelassen, aber keine Notebooks (um Chancengleichheit zu
gewährleisten).
Anmerkungen zur mündlichen Prüfung
Im Rahmen der mündlichen Prüfung möchte ich Ihr
Verständnis überprüfen. Es ist nicht sinnvoll, wenn
Sie Teile Ihrer Mitschrift stur auswendig lernen.
Der Schwerpunkt meiner Fragen wird auf Verständnisfragen liegen.
Zentrale, wichtige Ergebnisse (wie den maximalen Fluß minimalen
Schnitt Satz)
müssen Sie im Kopf haben, ebenso die Beweisskizzen zentraler Ergebnisse
(aber nicht die vollständigen Beweise, wenn diese umfangreich und
kompliziert sind).
Termine für die mündliche Prüfung können individuell
mit mir (im Normalfall auch kurzfristig) vereinbart werden.
Vorraussetzungen für ein Zeugnis über die Übungen
Folgende Voraussetzungen sind zu erfüllen, um ein Übungszeugnis
zu erlangen:
- Mindestens zweimaliges (bevorzugt dreimaliges) Vorrechnen eines
Übungsbeispieles an der
Tafel. Hierbei ist der gewählte Ansatz ausreichend zu begründen (Abschreiben von Lösungen von einem Zettel reicht nicht).
Ausnahmen in speziell begründeten Sonderfällen können
nur gemacht werden, wenn sie zu Semesterbeginn mit mir abgesprochen werden.
- Abgabe der Ausarbeitung der Hausübungsbeispiele (spätester Termin bei Ablegung der mündlichen Prüfung).
- Praktische Aufgabe:
Wahlweise ist ein von mir vorgebenener
Algorithmus zu implementieren oder ein von mir zugeteilter Fachartikel
zu lesen und zusammenzufassen. Es gibt keinen festen
Abgabetermin für die praktische Aufgabe.
Die Aufgabe ist Voraussetzung für den
Erhalt eines Übungszeugnisses, nicht aber für die
Möglichkeit zur Prüfung anzutreten. Die Studierenden
werden gebeten gegen Ende der Lehrveranstaltung mit mir Kontakt
betreff Zuteilung einer Artikels
oder eines zu implementierenden Algorithmus aufzunehmen.
-
Ablegung einer schriflichen Prüfund (gemeinsam mit Vorlesungsprüfung oder in Form einer Ersatzklausur, wenn nur ein
Übungszeugnis und kein Vorlesungszeugnis gewünscht wird).
Last update: January 16, 2014
Bettina Klinz
(klinz@opt.math.tu-graz.ac.at)