|
|
 |
|
Beschreibung |
KursbeschreibungIn diesem Kurs wollen wir die klassischen, gutartigen Graphenprobleme der kombinatorischen Optimierung mit ihren Algorithmen vorstellen und analysieren. Nach einer Einführung in Graphen und Algorithmen studieren wir zunächst minimale aufspannende Bäume. Ein Schwerpunkt des Kurses liegt auf den Bezügen der kombinatorischen Optimierung zur linearen Optimierung. Diese wollen wir jedoch nur als Werkzeug zum Algorithmendesign benutzen und nicht ihre allgemeinen Lösungsverfahren benutzen. Das zugrundeliegende Paradigma der primal-dualen Verfahren stellen wir am Beispiel des Kruskal-Algorithmus zur Berechnung minimaler aufspannender Bäume vor. Auch bei den folgenden Probleme, kürzeste Wege, maximale Flüsse, kostenminimale Flüsse, Kardinalitätsmatchings und gewichtete Matchings behalten wir immer polyhedrale und geometrische Aspekte im Auge.
Der Kurs ist als Alternative zum Kurs 01685 (Effiziente Graphenalgorithmen) gedacht und kann nicht zusammen mit diesem in einem Studiengang als Prüfungsfach gewählt werden. Es existieren
Berührungspunkte mit den Kursen Diskrete Mathematik und Lineare Optimierung, deren Kenntnis wird jedoch nicht vorausgesetzt.
Für den Kurs benutzen wir einen englischsprachigen Basistext, den wir zusammen mit Alexander Schliep in den letzten 10 Jahren geschrieben haben. Mittelfristig hoffen wir, diesen durch einen "echten" Kurstext ersetzen zu können.
|
|
|
