|
|
|
61414 Effiziente Graphenalgorithmen im Wintersemester 2024/2025 |
|
grundlegende Überarbeitung: Wintersemester 2011/2012 |
Umfang: 10.0 ECTS |
|
nächster geplanter Einsatz: Wintersemester 2025/2026 |
Versionen |
|
Autorinnen und Autoren |
Teilnahmevoraussetzungen |
|
Beschreibung |
|
|
 |
|
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.
|
|
|
|
|
Termine |
|
Veranstaltungsbeginn: 01.10.2024 |
|
Versand |
|
|
Material |
 |
Diese Lehrveranstaltung beinhaltet zugriffsgeschütztes Material, das nur nach dem Einloggen und bei vorhandener Belegung der Lehrveranstaltung eingesehen werden kann. Studierende der FernUniversität sollten sich einloggen. |
|
|
Zusatzmaterial |
|
|
Einsendeaufgaben |
|
Diese Veranstaltung wird auch mit Einsendearbeiten im Online-Übungssystem durchgeführt. Diese werden in diesem öffentlichen Portal nicht angezeigt. Wenn Sie einen Zugang zum LVU-System besitzen, loggen Sie sich bitte ein.
|
|
|
|
|
|
FernUniversität in Hagen, 58084 Hagen, Telefon: +49 2331 987-01, E-Mail: fernuni@fernuni-hagen.de