Lehrveranstaltungshandbuch 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 |
| Gültig ab | Wintersemester 2020/21 |
| 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
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 | Klausur |
Lernziele
| Zieltyp | Beschreibung |
|---|---|
| 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 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 | Nein |
Bei Fehlern, bitte Mitteilung an die
Webredaktion der Fakultät IME
Webredaktion der Fakultät IME
© 2022 Technische Hochschule Köln