Technische Universität Ilmenau

Approximationsalgorithmen - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu unseren Studiengängen. Rechtlich verbindliche Angaben zum Verlauf des Studiums entnehmen Sie bitte dem jeweiligen Studienplan (Anlage zur Studienordnung). Bitte beachten Sie diesen rechtlichen Hinweis. Angaben zum Raum und Zeitpunkt der einzelnen Lehrveranstaltungen entnehmen Sie bitte dem aktuellen Vorlesungsverzeichnis.

Fachinformationen zu Approximationsalgorithmen im Studiengang Master Informatik 2009
Fachnummer230
Prüfungsnummer2200078
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2242 (Komplexitätstheorie und Effiziente Algorithmen)
Fachverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
Turnusganzjährig
SpracheDeutsch
Leistungspunkte4
Präsenzstudium (h)34
Selbststudium (h)86
VerpflichtungWahlpflicht
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss

Findet statt im: SS 2014, WS 2015/2016

max. Teilnehmerzahl
Vorkenntnisse

Berechenbarkeit und Komplexitätstheorie, Effiziente Algorithmen

Lernergebnisse

Fachkompetenz: Die Studierenden kennen die grundlegenden Konzepte des Bereichs der Approximationsalgorithmen, insbesondere die Definition von Optimierungsaufgaben und die Qualitätsstufen von Approximationsalgorithmen (absolute, relative Approximationsgüte, [voll] polynomielle Approximationsschemata, inputabhängige Approximation). Sie kennen die Wirkungsweise der relevanten Entwurfsprinzipien. Sie kennen die relevanten Analysetechniken. Die Studierenden kennen die zentralen Beispielprobleme, für die Approximationsalgorithmen entwickelt wurden, ihre Performanzparameter und die Analysemethode.

Methodenkompetenz: Die Studierenden können die Entwurfsprinzipien auf verwandte Problemstellungen anwenden. Sie können Algorithmen und Probleme in die relevanten Klassen APX, PTAS, FPTAS usw. einsortieren. Sie können die zentralen Algorithmen beschreiben und die Analyse durchführen.

Inhalt

Grundbegriffe. Einführende Beispiele. Greedy Set Cover. Absolute Approximation: Färbung von planaren Graphen, Kantenfärbungen. Relative Approximation. Greedy-Verfahren und ihre Analyse.  MAX-SAT, Metrisches TSP. Asymptotische relative Approximation. Inputabhängige Approximation: Graphfärbungen. Polynomielle Approximationsschemata: Rucksackproblem. Asymptotisches Approximationsschema: Binpacking. Weitere Techniken: Lineare Programmierung und Randomisiertes Runden am Beispiel von MAX-SAT. Derandomisierung. Semidefinite Programmierung am Beispiel von Max-Cut. Approximate Counting und die Monte-Carlo-Methode.

Medienformen

Folien, Tafel, Übungsblätter

Literatur

* R. Wanka, Approximationsalgorithmen, Teubner 2006 

* K. Jansen, M. Margraf, Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter 2008

 * G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation, Springer-Verlag 1999

* D. P. Williamson, D. P. Shmoys, The Design of Approximation Algorithms, Cambridge University Press 2011

* D.-Z. Du, K.-I Ko, X. Hu, Design and Analysis of Approximation Algorithms, Springer 2012.

Lehrevaluation

Pflichtevaluation:

Freiwillige Evaluation:

WS 2009/10 (Übung)

Hospitation:

Informationen und Handreichungen zur Pflege von Modul- und Fachbeschreibungen durch den Modul- oder Fachverantwortlichen finden Sie auf den Infoseiten zum Modulkatalog.