Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2011/12 / Approximationsverfahren für Optimierungsprobleme


Inhaltsbereich

Approximationsverfahren für Optimierungsprobleme

Vorlesung mit Übung, 3+1-std., Di 16-18 Uhr, Do, 16-18 Uhr, Johannsen

Aktuelles

 


Inhalt

Zahlreiche für die Theorie und Praxis der Informatik wichtige algorithmische Probleme sind Optimierungsprobleme, d.h. zu jedem Input gibt es mehrere potentielle Lösungen, die mit einem Kosten- bzw. Nutzenmaß versehen sind. Gesucht sind Lösungen, bei denen dieses Maß minimal bzw. maximal wird. Die meisten dieser Probleme sind NP-schwer, effiziente Algorithmen, die stets eine optimale Lösung finden, können also nur existieren, falls P=NP gilt.

Daher betrachtet man Approximationsalgorithmen für solche Probleme, die Lösungen berechnen, die nur um einen (a priori abzuschätzenden) kleinen Fehlerbetrag vom Optimum abweichen. NP-schwere Optimierungsprobleme können sich bzgl. ihrer Approximierbarkeit sehr verschieden verhalten:

  • für einige gibt es beliebig gute Approximationsverfahren;
  • andere erlauben effiziente Approximationsverfahren bis zu einer gewissen Güte, aber keine besseren;
  • für einige besonders hartnäckige Probleme kann es überhaupt kein effizientes Approximationsverfahren geben.

In der Vorlesung sollen Prinzipien zum Entwurf von Approximationsverfahren vorgestellt, sowie die theoretischen Grundlagen zur Untersuchung der Unterschiede im Approximierbarkeitsverhalten von Optimierungsproblemen gelegt werden. Dabei lehnt sie sich stark an das unten genannte Lehrbuch, speziell die Kapitel 1–5, an.


Organisation

  • Umfang: 3+1 Semesterwochenstunden
  • Vorkenntnisse: Algorithmen und Datenstrukturen und Formale Sprachen und Komplexität bzw. Theoretische Informatik für Medieninformatiker
  • Vorlesung & Übung: Dr. Jan Johannsen

 

Die Vorlesung wird anerkannt:
  • für Studierende im Studiengang Informatik Diplom im Prüfungsfach Programmierung und Grundlagen, Teilbereich Theoretische Informatik
  • für Studierende im Studiengang Informatik Master für das Modul Algorithmik und Komplexität
  • für Studierende im Studiengang Medieninformatik Master für das Modul Vertiefende Themen der Informatik für Master
  • für Studierende in den Studiengängen Informatik und Medieninformatik Bachelor für das Modul Vertiefende Themen der (Medien-) Informatik
  • für Studierende mit Nebenfach Informatik nach Vereinbarung

Zeit und Ort

Vorlesung
Di, 16-18 Uhr Raum 106 (Amalienstr. 73a) 18.10.2011
Vorlesung & Übung
Do, 16-18 Uhr
Raum D Z005 (Hauptgebäude)
 20.10.2011

Material zur Vorlesung

Vorlesungsfolien

Literatur:

  • G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela und M. Protasi "Complexity and Approximation. Combinatorial optimization problems and their approximability properties", Springer Verlag 1999, ISBN 3-540-65431-3.
    Das Buch ist als Ansichtsexemplar in der Institutsbibliothek vorhanden, Signatur 1602 / THE 20 Aus 1.
    Es gibt auch eine WWW-Seite zu dem Buch.
  • V. Vazirani "Approximation Algorithms", Springer Verlag 2001, ISBN 3-540-65367-8.


Übungen

Die Übungen finden 14-tägig zum Vorlesungstermin am Donnerstag statt, zuerst am 27. Oktober.

Übungsblätter


Klausur

Die Klausur findet in der letzten Übung am 9. Februar um 16 Uhr statt.

 

Artikelaktionen


Funktionsleiste