Illustrationsbild für den Virtuellen Studienplatz

Lehrveranstaltung 61414 (WiSe 24/25)

 
61414 Effiziente Graphenalgorithmen im Wintersemester 2024/2025
Hinweis Das Semester dieser Veranstaltung ist beendet.
grundlegende Überarbeitung: Wintersemester 2011/2012 Umfang: 10.0 ECTS
nächster geplanter Einsatz: Wintersemester 2025/2026 Autorinnen und Autoren
Teilnahmevoraussetzungen Beschreibung
Schließen
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
Hinweis 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.
Betreuung
Betreuende Liste der Campus Standorte bzw. Studienzentren

Irrtümer und nachträgliche Datenänderungen vorbehalten.


Seite erstellt in 0,1s  |  2.4.25,11:33 im Sommersemester 2025  |  realisiert durch das LVU-System
FernUni-Logo FernUniversität in Hagen, 58084 Hagen, Telefon: +49 2331 987-01, E-Mail: fernuni@fernuni-hagen.de