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.

Allgemeine Informationen

Kursautoren	W. Hochstättler, A. Schliep
Betreuung	Prof. Dr. W. Hochstättler (E-Mail: ) Sophia Keip (E-Mail: )
Newsgroup	feu.mathematik.kurs.1216 WWW-Zugang zur Newsgroup Informationen zum Zugang in der Broschüre "News-HowTo: So richte ich mir ein News-Konto ein".
Moodle	Link zur Moodleseite des Kurses
Studientag	Studientag am Sa, 28.01.2023, 9:30 Uhr, voraussichtlich in Hagen
Kurssoftware	CATBox-Software

Aktuelles im Wintersemester 2022/2023

Einsendeaufgaben	Lösungsvorschläge (2 Tage nach Einsendetermin zugänglich)	Anschreiben und Zusatzmaterial	Softwarebeispiele	Graphenbeispiele
Kurseinheit 1 Kurseinheit 2 Kurseinheit 3 Kurseinheit 4 Kurseinheit 5 Kurseinheit 6 Kurseinheit 7 Errata zum Buch	Kurseinheit 1 Kurseinheit 2 Kurseinheit 3 Kurseinheit 4 Kurseinheit 5 Kurseinheit 6 Kurseinheit 7	Vorab-Anschreiben Begrüßungsschreiben Studientagseinladung Annotierte Studientagsfolien	zu KE 1: EA3a.alg EA3a.pro EA3aa.alg EA3aa.pro EA3b.alg EA3b.pro EA3c.alg EA3c.pro topsort1.py zu KE 4: FordFulkersonDFS.alg FordFulkersonDFS.pro Die Softwarebeispiele werden zusammen mit den entsprechenden Lösungsvorschlägen freigeschaltet.	3Components.cat BFS.cat DoubleSquare.cat DoubleTriangle.cat EA3c.cat ExampleA.cat ExampleA2.cat K10-10.cat K3-3.cat K4.cat K4-5.cat K5.cat K5-5.cat romjerusalem.cat Sample.cat FordFulkersonDFSWC.cat FordFulkersonDFSWC2.cat Die Graphenbeispiele sind ab sofort freigeschaltet.