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

TagZeitRaumPeriode
Montag11:15-13:00BE01 7. Oktober 2013 - 20. Jänner 2014
Donnerstag12:15-14:00BE01 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:

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:
Das folgende Buch gibt einen umfassenden Einblick in das Gebiet der Netzwerkflußpprobleme, eines Teilgebietes der kombinatorischen Optimierung. Ferner sollten an dieser Stelle auch noch die beiden folgenden klassischen, allerdings schon etwas älteren Bücher genannt werden:

Bibliographien

Die folgenden beiden annotierten Bibliographien enthalten viele weitere Literaturreferenzen zur kombinatorischen Optimierung:



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:


    Last update: January 16, 2014
    Bettina Klinz (klinz@opt.math.tu-graz.ac.at)