Lehrveranstaltungshandbuch Kombinatorische Optimierung und Graphenalgorithmen


Verantwortlich: Prof. Dr. Hubert Randerath

Lehrveranstaltung

Befriedigt Modul (MID)

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

Diese Seite läuft auf FoswikiDas Urheberrecht © liegt bei den mitwirkenden Autoren. Alle Inhalte dieser Kollaborations-Plattform sind Eigentum der Autoren.
Ideen, Anfragen oder Probleme bezüglich Foswiki? Feedback senden