Kombinatorische Optimierung und Graphenalgorithmen
Englisch
Combinatorial Optimization and Graph Algorithms
LVID
F07_KOGA
LVPID (Prüfungsnummer)
Semesterplan (SWS)
Vorlesung
2
Übung (ganzer Kurs)
2
Übung (geteilter Kurs)
Praktikum
Projekt
Seminar
Tutorium (freiwillig)
Präsenzzeiten
Vorlesung
30
Übung (ganzer Kurs)
30
Übung (geteilter Kurs)
Praktikum
Projekt
Seminar
Tutorium (freiwillig)
max. Teilnehmerzahl
Übung (ganzer Kurs)
30
Übung (geteilter Kurs)
Praktikum
Projekt
Seminar
Gesamtaufwand: 150
Unterrichtssprache
Deutsch
Niveau
Master
Notwendige Voraussetzungen
Grundlagenwissen Graphentheorie
Grundlagenwissen Algorithmik
Literatur
Lineare und Netzwerk-Optimierung, H.W. Hamacher, Vieweg-Verlag
CATBOX - An Interactive Course in Combinatorial Optimization, W. Hochstättler, A. Schliep, Springer-Verlag
Graphentheoretische Konzepte und Algorithmen, S. O. Krumke, H. Noltemeier, Teubner-Verlag
Combinatorial Optimization - Polyhedra and Efficiency, A. Schrijver, Springer-Verlag
Dozenten
Wissenschaftliche Mitarbeiter
tba
Zeugnistext
Kombinatorische Optimierung und Graphenalgorithmen
Kompetenznachweis
Form
sK
Regelfall (bei geringer Prüfungsanzahl: sMP)
Aufwand [h]
sK
10
Intervall: 3/Jahr
Lehrveranstaltungselemente
Vorlesung / Übung
Lernziele
Lerninhalte (Kenntnisse)
KOGA-Grundlagen: Grundbegriffe der Graphentheorie und derKombinatorischen Optimierung
Minimale aufspannende Bäume: Algorithmen von Kruskal, Prim undTarjan, Greedy-Algorithmen, Matroide, Steinerbäume, Netzwerk-Design
Lineare Programme: Struktur, Modellierung, Transformation in dieStandardform, Simplex-Verfahren, Dualitätstheorie
Gewichtete Matchings und das Chinesische Briefträger Problem:Gewichtete Matchings in bipartiten Graphen, Gewichtete Matchingsin nicht-bipartiten Graphen, Algorithmus von Floyd-Warshall,Algorithmus von Fleury, Effizienter Algorithmus für das ChinesischeBriefträger Problem
Flüsse in Netzwerken: Grundlagen der Netzwerktheorie,Algorithmus von Dinic, Kostenminimale Flüsse
Spezielle Diskrete und Kombinatorische Optimierungsprobleme:Travelling Salesman Problem, das Frequenzzuweisungsproblem,Scheduling-Probleme, Routing-Probleme
Fertigkeiten
Die Studierenden sind in der Lage Verfahren und Konzepte derGraphentheorie und der Kombinatorischen Optimierung zurBeschreibung und algorithmischen Lösung von Problemstellungender Informatik, der Technik und des täglichen Lebens anzuwenden.
Sie haben die Fertigkeit Verfahren und Konzepte der Graphentheorieund der Kombinatorischen Optimierung zur Beschreibung undalgorithmischen Lösung von Problemstellungen der Informatik,der Technik und des täglichen Lebens anzupassen.
Sie können algorithmische Denk- und Arbeitweisen wie Komplexitätvon Problemklassen, Effizienz von Algorithmen und Approximation,die sie induktiv an Optimierungsaufgaben in Netzwerken undgewichteten Graphen erlernt haben, anwenden.