Logo Fachbereich Mathematik Fachbereich Mathematik
   01216 Kombinatorische Optimierung - Effiziente Graphenalgorithmen

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".

Studientag Studientag am So, 30.01.2022
Kurssoftware CATBox-Software

   Aktuelles im Wintersemester 2020/2021

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 1
Kurseinheit 2
Kurseinheit 3
Kurseinheit 4
Kurseinheit 5

Vorab-Anschreiben

Begrüßungsschreiben

Studientagseinladung


zu KE 1:
EA1.alg
EA1.pro
EA2a.alg
EA2a.pro
EA2aa.alg
EA2aa.pro
EA2b.alg
EA2b.pro
EA2c.alg
EA2c.pro
topsort1.py
arbitrage.cat
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
EA2c.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.