Technische Universität Ilmenau

Approximationsalgorithmen - Interaktive Studienpläne der TU Ilmenau

Die Interaktiven Studienpläne sind ein Informationsangebot zu den Studiengängen der TU Ilmenau.

Die rechtsverbindlichen Studienpläne entnehmen Sie bitte den jeweiligen Studien- und Prüfungsordnungen (Anlage Studienplan).

Alle Angaben zu geplanten Lehrveranstaltungen finden Sie im elektronischen Vorlesungsverzeichnis.

Bitte beachten Sie, dass auf dieser Seite keine Aktualisierungen mehr vorgenommen werden. Alle Module und Studienpläne ab der PO-Version 2021 (Bachelor- und Master-Studiengänge) sind ab sofort im Campus-Portal erreichbar.

Modulinformationen zu Approximationsalgorithmen im Studiengang Master Informatik 2013
ACHTUNG: wird nicht mehr angeboten!
Modulnummer200077
Prüfungsnummer2200731
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2242 (Algorithmik)
Modulverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
Turnusganzjährig
SpracheDeutsch
Leistungspunkte5
Präsenzstudium (h)67
Selbststudium (h)83
VerpflichtungWahlmodul
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss
Link zum Moodle-Kurs
LehrendeDietzfelbinger
Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Vorkenntnisse

Berechenbarkeit und Komplexitätstheorie

Effiziente Algorithmen

Lernergebnisse und erworbene Kompetenzen

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.

Sozialkompetenz: Selbst in der Vorlesung ist Interaktion stets möglich, dazu sind die Studierenden befähigt. Die Studierenden haben die Erfahrung gemacht, dass Fragen unmittelbar geklärt werden, dass Diskussionen auf Augenhöhe stattfinden und Beiträge wertschätzend aufgenommen werden. In der Übung konnten sich die Studierenden in Präsentationen üben. Sie haben wertvolle Erfahrung in der Rolle des Präsentierenden. 


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 und technische Anforderungen bei Lehr- und Abschlussleistungen in elektronischer Form

 zum Moodle-Kurs

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