Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2013/14 / Approximations-Algorithmen


Inhaltsbereich

Approximations-Algorithmen

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

Aktuelles

  • Eine Nachholklausur ist nicht geplant. Teilnehmer, die eine mündliche Wiederholungsprüfung benötigen, können dafür einen Termin in dem Zeitraum vom 24.03. bis 04.04. ausmachen.
  • Die Klausur ist korrigiert und die Ergebnisse wurden verschickt. Zur Klausureinsicht machen Sie bitte einen individuellen Termin in der Woche 24.-28.02. aus.

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 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 & Übung Di, 14-16 Uhr Raum A 119 (Geschw.-Scholl-Pl. 1)
Vorlesung Do, 16-18 Uhr Raum S 007 (Schellingstr. 3)

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.
  • B Gärtner, J. Matousek "Approximation Algorithms and Semidefinite Programming", Springer Verlag 2012, ISBN 978-3-642-22014-2


Übungen

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

Übungsblätter


Klausur

Die Klausur findet in der letzten Vorlesungsstunde am Donnerstag, den 6.2. statt.
Bitte melden Sie sich bis zum 6.1. bei UniWorx zur Klausur an.

 

 

Artikelaktionen


Funktionsleiste