Lehrver­anstaltung

KOGA - Kombinatorische Optimierung und Graphenalgorithmen


PDF Lehrveranstaltungsverzeichnis English Version: KOGA

Version: 1 | Letzte Änderung: 25.01.2020 18:25 | Entwurf: 0 | Status: vom verantwortlichen Dozent freigegeben

Langname Kombinatorische Optimierung und Graphenalgorithmen
Anerkennende LModule KOGA_MaTIN
Verantwortlich
Prof. Dr. Hubert Randerath
Professor Fakultät IME
Niveau Master
Semester im Jahr Wintersemester
Dauer Semester
Stunden im Selbststudium 78
ECTS 5
Dozenten
Prof. Dr. Hubert Randerath
Professor Fakultät IME
Voraussetzungen Grundlagenwissen Graphentheorie
Grundlagenwissen Algorithmik
Unterrichtssprache deutsch
separate Abschlussprüfung Ja
Literatur
keine/none
Abschlussprüfung
Details
Schriftliche Klausur. Bei geringer Anzahl von Teilnehmer ggf. auch mündliche Prüfung.
Mindeststandard
In der Regel reichen 50% aller erreichbaren Klausurpunkte zum Bestehen (mit Note 4,0)
Prüfungstyp
Schriftliche Klausur. Bei geringer Anzahl von Teilnehmer ggf. auch mündliche Prüfung.

Lernziele

Kenntnisse
- KOGA-Grundlagen: Grundbegriffe der Graphentheorie und der Kombinatorischen Optimierung
- Minimale aufspannende Bäume: Algorithmen von Kruskal, Prim und Tarjan, Greedy-Algorithmen, Matroide, Steinerbäume, Netzwerk-Design
- Lineare Programme: Struktur, Modellierung, Transformation in die Standardform, Simplex-Verfahren, Dualitätstheorie
- Gewichtete Matchings und das Chinesische Briefträger Problem: Gewichtete Matchings in bipartiten Graphen, Gewichtete Matchings in nicht-bipartiten Graphen, Algorithmus von Floyd-Warshall, Algorithmus von Fleury, Effizienter Algorithmus für das Chinesische Briefträ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
Aufwand Präsenzlehre
Typ Präsenzzeit (h/Wo.)
Vorlesung 2
Übungen (ganzer Kurs) 2
Übungen (geteilter Kurs) 0
Tutorium (freiwillig) 0
Besondere Literatur
keine/none
Besondere Voraussetzungen
keine
Begleitmaterial
- 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
Separate Prüfung
keine

© 2022 Technische Hochschule Köln