Lehrveranstaltungshandbuch Kombinatorische Optimierung und Graphenalgorithmen

---

Verantwortlich: Prof. Dr. Hubert Randerath

Lehrveranstaltung

Befriedigt Modul (MID)

• aktuelle
  • Ma TIN2012 KOGA

Organisation

Version erstellt 2013-04-29 VID 2 gültig ab WS 2013/14 gültig bis

Bezeichnung Lang 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

• Prof. Dr. Hubert Randerath

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 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

Fertigkeiten

• Die Studierenden sind in der Lage Verfahren und Konzepte der Graphentheorie und der Kombinatorischen Optimierung zur Beschreibung und algorithmischen Lösung von Problemstellungen der Informatik, der Technik und des täglichen Lebens anzuwenden.
• Sie haben die Fertigkeit Verfahren und Konzepte der Graphentheorie und der Kombinatorischen Optimierung zur Beschreibung und algorithmischen Lösung von Problemstellungen der Informatik, der Technik und des täglichen Lebens anzupassen.
• Sie können algorithmische Denk- und Arbeitweisen wie Komplexität von Problemklassen, Effizienz von Algorithmen und Approximation, die sie induktiv an Optimierungsaufgaben in Netzwerken und gewichteten Graphen erlernt haben, anwenden.

Begleitmaterial

• elektronische Vortragsfolien zur Vorlesung
• elektronische Übungsaufgabensammlung

Besondere Voraussetzungen

• keine

Besondere Literatur

• keine

Besonderer Kompetenznachweis

Form
bÜA	Präsenzübung

Beitrag zum LV-Ergebnis
bÜA	unbenotet

Intervall: 1/Jahr