Wir befassen uns mit klassischen gutartigen Problemen der
kombinatorischen Optimierung, die auf graphentheoretischen Problemen
beruhen, nämlich Minimaler Aufspannender Baum, Kürzester Weg,
Maximaler Fluss, Kostenminimaler Fluss,
Bipartites Maximales Matching, Nicht-Bipartites Maximales
Matching und Gewichtetes Matching. Eine wichtige Rolle spielen dabei die
polyhedralen Beschreibungen der zulässigen Mengen der Probleme und
primal-duale Algorithmen. Deswegen werden wir schon den Greedy-Algorithmus
zur Bestimmung eines minimalen aufspannenden Baumes als primal-duales
Verfahren
interpretieren.
Als Basistext benutzen wir das Buch CATBox - An
Interactive Course in Combinatorial Optimization von
Winfried Hochstättler und Alexander Schliep. Darin enthalten sind auch
weiterführende
Literaturhinweise. Das Buch ist auf Englisch geschrieben.
Der Lehrtext animiert zur Verwendung einer Software, die von uns entwickelt
wurde und mit der man den Ablauf der Algorithmen an Beispielgraphen, die
man selber kreieren und verändern kann, beobachten und, ähnlich
wie mit
einem Debugger, kontrollieren kann.
In einem mathematischen Kurs kann die Bedeutung der
Übungen nicht hoch genug eingeschätzt werden. Die Fähigkeit zur
Lösung konkreter Probleme, oft mit ad-hoc Methoden, kann nur durch
Übung erlernt werden.