Kombinatorische Optimierung
WS 2012-2013, 3 VO/1 UE
(502.366 / 502.637)

E. Dragoti-Cela

• Zeit und Ort
Vorlesung:
Do, 12:15-14:00, und Fr., 10:15-12:00 alle zwei Wochen, HS BE01, Steyrergasse 30, Erdgeschoss.
Durch ausgefallene Termine wegen Feiertagen entstehen einige Unregelmäigkeiten; siehe TUGonline für die genauen Termine


Übung:
Fr., 10:15-12:00, alle zwei Wochen
HS BE01, Steyrergasse 30, Erdgeschoss.
Durch ausgefallene Termine wegen Feiertagen entstehen einige Unregelmäigkeiten; siehe TUGonlinefür die genauen Termine,


• Beginn: Do., 4. Oktober 2012, Vorlesung, 12:15-14:00, HS BE01, Steyrergasse 30, Erdgeschoss
• Anmeldung
via TUGonline, für die Vorlesung bis 10.10.2012,
für die Übung bis 12.10.2012.
• Vorlesungsinhalt

Diese Lehrveranstaltung befasst sich mit grundlegenden kombinatorischen Optimierungsproblemen. In der Regel sind das polynomial lösbare Optimierungsprobleme für die sowohl strukturelle Eigenschaften als auch Lösungsansätze besprochen werden. Das Ziel ist, einerseits die Studierenden mit prominenten, sowohl theoretisch als auch praktisch relevanten Problemen der Kombinatorischen Optimierung vertraut zu machen, und anderseits eine Handvoll an Lösungsansätzen und algorithmischen Paradigmen als praktisch relevantes Wissen zu vermitteln.


Die Kapitelüberschriften und Stichwörter sind:

• Aufspannende Bäume und Arboreszenzen: minimale aufspannende Bäume, Arboreszenzen mit minimalem Gewicht, das Spannbaum Polytop.
• Kürzeste Wegeprobleme: Kürzeste Wege von einer Quelle aus (Dijkstras Algorithmus, Moore-Bellman-Ford-Algorithmus), Kürzeste Wege zwischen allen Knotenpaaren (Floyd-Warschall-Algorithmus), Kreise mit minimalem durchschnittlichem Kantengewicht.
• Netzwerkflüsse: das Max-Flow-Min-Cut-Theorem, der Satz von Menger, Edmonds-Karp-Algorithmus, Fijishiges Algorithmus, Goldberg-Tarjan-Algorithmus, Gomory-Hu-Bäume.
• Flüsse mit minimalen Kosten: ein Optimalitätskriterium, der Minimum-Mean-Cycle-Cancelling-Algorithmus, der sukzessive-Kürzeste-Wege-Algorithmus, Orlins-Algorithmus.
• Matching-Probleme:: das Maximale-Matching-Problem in bipartiten Graphen, das Maximale-Matching-Problem in beliebigen Graphen, das Gewichtete-Matching-Problem in bipartiten Graphen und das lineare Zuordnungsproblem, das Matching-Polytop.
• Matroide: Definition, der Greedy-Algorithmus, der Schnitt von zwei-Matroiden
• Literatur

Die Hauptliteraturquelle ist


B. Korte und J. Vygen, Kombinatorische Optimierung: Theorie und Algorithmen, Springer, 2008.
Auch als ebook am Campus der TUGraz vorhanden.

Weitere Titel sind:

• R. Ahuja, T. Magnanti und J. Orlin, Network flows: Theory, Algorithms and Applications, Prentice Hall, 1993.
• W. Cook, W. Cunningham, W. Pulleyblank und A. Schrijver, Combinatorial Optimization, Wiley, 1998.
• W. Hochstättler und A. Schliep, CATBox: An Interactive Course in Combinatorial Optimization, Springer, 2010.
• S. Krumke und H. Noltemeier, Graphentheoretische Konzepte und Algorithmen , Teubner B.G. GmbH, 2005.
• A. Schrijver, Combinatorial Optimization, Volume A, Springer, 2003.

Prüfungsmodus

Die Vorlesung wird anhand einer mündlichen Prüfung benotet. Die Prüfungstermine werden je nach Bedarf mit der Vortragenden vereinbart.

Die einstündige Übung hat einen immanenten Charakter und wird anhand von zwei Klausuren und der Mitarbeit der Studierenden in den Übungsstunden mit Hilfe eines Punktesystems benotet.


Klausurtermine:

• 1. Übungsklausur: Freitag, 30. November 2012
• 2. Übungsklausur: Donnerstag, 31. Jänner 2013
• Nachklausur: In der letzen Woche der Semesterferien oder in der ersten Woche des Sommersemesters.

Aufgrund des immanenten Charakters der Lehrveranstaltung gibt es genau eine Nachklausur. Beim Antreten zur Nachklausur ist zu entscheiden, ob die erste oder die zweite Klausur wiederholt werden soll. Durch den Antritt werden die Punkte aus der wiederholten Klausur gelöscht.


Die Klausuren werden (rechtzeitig) im Prüfungssystem des TUGonline erfasst, inkl. Angaben über Ort ud Zeit;
die Anmeldung zu den Klausuren erfolgt via TUGonline.


Bei den Übungsklausuren sind alle schriftlichen Unterlagen sowie Taschenrechner erlaubt. Dennoch sind alle Zwischenschritte anzugeben. Die Verwendung von Notebooks, PDAs, Handhelds, Handys etc. ist nicht gestattet.


Mitarbeit im Rahmen der Übungseinheiten:
Für ein positives Übungszeugnis muss jeder Studierender mindestens zwei Mal an der Tafel vorrechnen. Unter allen Kandidatem, die ein bestimmtes Beispiel vorrechnen möchten, wird der/die Übungsleiter/in, unter Berücksichtigung der Anzhal der bereits getätigten Tafelmeldungen, eine Kandidatin bzw. einen Kandidaten aussuchen. Jede Tafelmeldung ist maximal 2 Punkte Wert. Bei der Bewertung der Tafelmeldungen wird neben der mathematischen Korrektheit auch auf die Qualität der Präsentation Wert gelegt.


Bei jeder Klausur können maximal 16 Punkte erworben werden.
Somit ergibt sich eine maximale Anzahl von 36 zu erreichenden Punkten.
Für ein positives Übungszeugnis müssen bei den Klausuren in Summe mindestens 14 Punkte erreicht werden.


Es gibt auch die Möglichkeit Bonuspunkte zu erwerben: wenn für das Vorrechnen eines Beispiels keine Kandidatin/keinen Kandidaten gibt, die/der weniger als zweimal an der Tafel war, dann dürfen andere Freiwillige das Beispiel vorrechnen und maximal einen Punkt pro vorgerechnetem Beispiel erwerben. Es können maximal 2 Bonuspunkte erworben werden.


Notenschlüssel für die Bewertung der Übung:

0 <= P <= 18	Nicht genügend
18 < P <= 23	Genügend
23 < P <= 27	Befriedigend
27 < P <= 31	Gut
31 < P	Sehr Gut.



• Übungsblätter (pdf)
  • 1. Übungsblatt; zu besprechen am Fr., 12.10. und Do., 25.10.
  • 2. Übungsblatt; zu besprechen am Fr., 9.11.
  • 3. Übungsblatt; zu besprechen am Fr., 23.11.
  • 4. Übungsblatt; zu besprechen am Fr., 7.12.
  • 5. Übungsblatt; zu besprechen am Fr., 11.1.
  • 6. Übungsblatt; zu besprechen am Fr., 25.1.

Back to my homepage

Letzte Änderung: Jänner 2013