Lehrveranstaltungshandbuch Kombinatorische Optimierung und Graphenalgorithmen

---

Verantwortlich: Prof. Dr. 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

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.

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