-
Zeit
und Ort
siehe folgende TUGonline-Links
Vorlesung
Übung
-
Beginn: 1.10.2020, 12:15-13:45, HS BE01, Steyrergasse 30, Erdgeschoss
-
Anmeldung
via TUGonline, für Vorlesung und Übung bis 31.10.2020.
-
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:
- Einführung und Motivation
- Aufspannende Branchings und Arboreszenzen: minimale/maximale aufspannende Branchings und Arboreszenzen (mit bestimmter Wurzel).
- 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
- Ganzzahlige Optimierung: die ganzzahlige Hülle eines Polyeders, vollständige duale Ganzzahligkeit, vollständige unimodulare Matrizen, Schnittebenen, Langrange-Relaxierung
-
Literatur
Die Hauptliteraturquelle ist
B. Korte und J. Vygen, Kombinatorische Optimierung: Theorie und Algorithmen, Springer, 2. Auflage 2012.
B. Korte und J. Vygen, Combinatorial Optimization: Theory and Algortithms , Springer, 6th edition, 2018.
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. Die Übung wird in Doppelstunden organisiert, sodass ungefähr in jeder zweiten Woche eine Doppelstunde Übung stattfindet. Beginn am 8.10.!
Klausurtermine:
- 1. Übungsklausur: Freitag, 27. November 2020
- 2. Übungsklausur: Freitag, 29. Jänner 2021
- Nachklausur: In der letzen Woche der Semesterferien oder in der ersten Woche des Sommersemesters 2021.
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 keine schriftlichen Unterlagen erlaubt; einzige Ausnahme ist ein A4 Blatt, das jeder Kandidat nach Wunsch individuell gestalten kann. Taschenrechner mit einer Ausgabenzeile sind erlaubt.
Die Verwendung von Notebooks, PDAs, Handhelds, Handys und anderen internetfähigen Geräten ist nicht gestattet.
Mitarbeit im Rahmen der Übungseinheiten:
Für ein positives Übungszeugnis muss jeder Studierender
mindestens drei Mal an der Tafel vorrechnen.
Am Anfang jeder Übungseinheit müssen die Studierenden bekannt geben, welche Übungsbeispiele sie gelöst haben. Unter allen Kandidatem, die
ein bestimmtes Beispiel gelöst haben, 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.
Durch das vorrechnen an der Tafel können maximal 8 Punkte erworben werden.
Die selbststädige Arbeit zur Lösung von Übungsbeispielen während des Semesters wird mit maximal 4 Punkten honoriert (der Anteil der gelösten Beispielen wird auf 4 Punkte skaliert).
Bei jeder Klausur können maximal 16 Punkte erworben werden.
Weiters kann die Übungsleiterin einen Bonuspunkt vergeben (für eine besonders schöne Lösung, eine besonders klare Präsentation, usw.).
Somit ergibt sich eine maximale Anzahl von 45 zu erreichenden Punkten.
Für ein positives Übungszeugnis müssen bei den Klausuren in Summe mindestens 14 Punkte erreicht werden.
Notenschlüssel für die Bewertung der Übung:
|
0 <= P< 22 | Nicht genügend |
|
22 <= P < 28 | Genügend |
|
28 <= P < 34 | Befriedigend |
|
34 <= P < 40 | Gut |
|
40 <= P | Sehr Gut.
|
- Algorithmen, Beispiele u.a.m. (pdf)
- Moore-Bellman-Ford Algorithmus für das Kürzeste-Wege-Problem mit einer fixen Quelle und allen Senken
- Floyd-Warshall Algorithmus für das Kürzeste-Wege-Problem mit allen Quelle-Senke-Paaren
- Algorithmus zur Bestimmung eines Kreises mit minimalem durchschnittlichen Gewicht in einem gerichteten Graphen
- Algorithmus zur Bestimmung eines Gomory-Hu-Baums in einem Graphen mit Kapazitäten auf den Kanten
- Algorithmus der sukzessiven kürzesten Wege zur Lösung des Minimalen-Kosten-Flussproblems für Instanzen mit ganzzahligem Input und konservativen Kantengewichten
- Kapazität-Skalierungs-Algorithmus zur Lösung des Minimalen-Kosten-Flussproblems für Instanzen mit ganzzahligem Input, konservativen Kantengewichten und unendlichen Kapazit\äten
cela@opt.math.tu-graz.ac.at.