12329 - Approximationsalgorithmen Modulübersicht

Modulnummer: 12329
Modultitel:Approximationsalgorithmen
  Approximation Algorithms
Einrichtung: Fakultät 1 - MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik
Verantwortlich:
  • Prof. Dr. rer. nat. habil Meer, Klaus
Lehr- und Prüfungssprache:Deutsch
Dauer:1 Semester
Angebotsturnus: jedes Wintersemester ungerader Jahre
Leistungspunkte: 8
Lernziele:Die Studierenden sollen einen Einblick erhalten, ob und auf welche Weise man NP-schwere Optimierungsprobleme praktisch lösen kann, wenn man auf effizienten Algorithmen besteht, aber auf Exaktheit der berechneten Lösungen verzichtet. Wesentlich dabei ist einerseits, ein Verständnis für Methoden zu entwickeln, mit denen man zeigen kann, dass sich gewisse Probleme voraussichtlich auch dann nicht effizient lösen lassen, wenn man nur näherungsweise Lösungen verlangt. Andererseits werden für eine Klasse von schweren Problemen Techniken präsentiert, mit denen man gute Approximationsalgorithmen entwickeln kann.
Inhalte:
  • kombinatorische Optimierungsprobleme
  • Einführung verschiedener Komplexitätsklassen zur Charakterisierung diverser Approximationseigenschaften
  • Entwurf verschiedener Approximationsalgorithmen für Probleme wie Travelling Salesman, Bin Packing, Knapsack u.a.
  • negative Approximationsresultate, Gap-Technik
  • Probabilistically Checkable Proofs PCP, Charakterisierung der Klasse NP durch PCPs
  • Negative Approximationsresultate mittels des PCP-Satzes
Empfohlene Voraussetzungen:Elementare Kenntnisse über die Komplexitätsklassen P und NP sowie den Begriff der NP-Vollständigkeit sind hilfreich, werden aber zu Vorlesungsbeginn auch kurz behandelt.
Zum Beispiel Kenntnis des Inhalts von Modul
  • 11787 Theoretische Informatik
Zwingende Voraussetzungen:keine
Lehrformen und Arbeitsumfang:
  • Vorlesung / 4 SWS
  • Übung / 2 SWS
  • Selbststudium / 150 Stunden
Unterrichtsmaterialien und Literaturhinweise:Folgende Bücher behandeln Approximationsalgorithmen:
  • Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimizati on Problems and Their Approximability Properties. Springer 1999.
  • D. Hochbaum (Hrg.): Approximation Algorithms for NP-Hard Problems PWS Publishing Company, Boston, MA, 1997.
  • J. Hromkovic: Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation and Heuristics (Texts in Theoretical Computer Science), Springer 2001.
  • V. Vazirani: Approximation Algorithms. Springer 2001.
  • R. Wanka: Approximationsalgorithmen, Teubner 2006.
  • K. Jansen, M. Markgraf: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008.
Modulprüfung:Modulabschlussprüfung (MAP)
Prüfungsleistung/en für Modulprüfung:
  • mündliche Prüfung, 30-45 Minuten
Bewertung der Modulprüfung:Prüfungsleistung - benotet
Teilnehmerbeschränkung:keine
Zuordnung zu Studiengängen:
  • M.Sc. / Angewandte Mathematik (universitäres Profil) / Prüfungsordnung 2008
  • M.Sc. / Angewandte Mathematik (universitäres Profil) / Prüfungsordnung 2019
  • Abschluss im Ausland / Informatik / keine Prüfungsordnung
  • B.Sc. / Informatik (universitäres Profil) / Prüfungsordnung 2008
  • B.Sc. / Mathematik (universitäres Profil) / Prüfungsordnung 2019
  • B.Sc. / Wirtschaftsmathematik (universitäres Profil) / Prüfungsordnung 2007
  • B.Sc. / Wirtschaftsmathematik (universitäres Profil) / Prüfungsordnung 2019
Bemerkungen:
  • Studiengang Informatik B.Sc.: Wahlpflichtmodul in Komplex „Grundlagen der Informatik“ (Niveaustufe 300)
  • Studiengang Angewandte Mathematik M.Sc.: Wahlpflichtmodul im Komplex „Optimierung“
  • Studiengang Mathematik B.Sc.: Wahlpflichtmodul im Komplex „Vertiefung“, im begrenzten Umfang
  • Studiengang Wirtschaftsmathematik B.Sc.: Wahlpflichtmodul im Komplex „Vertiefung“, im begrenzten Umfang
Veranstaltungen zum Modul:
  • Vorlesung: Approximationsalgorithmen
  • Übung zur Vorlesung
  • Zugehörige Prüfung
Veranstaltungen im aktuellen Semester:
  • keine Zuordnung vorhanden

Unsere Webseite verwendet Cookies. Diese haben zwei Funktionen: Zum einen sind sie erforderlich für die grundlegende Funktionalität unserer Website. Zum anderen können wir mit Hilfe der Cookies unsere Inhalte für Sie immer weiter verbessern. Hierzu werden pseudonymisierte Daten von Website-Besuchern gesammelt und ausgewertet. Das Einverständnis in die Verwendung der technisch nicht notwendigen Cookies können Sie jeder Zeit wiederrufen. Weitere Informationen erhalten Sie auf unseren Seiten zum Datenschutz.

Erforderlich

Diese Cookies werden für eine reibungslose Funktion unserer Website benötigt.

Statistik

Für den Zweck der Statistik betreiben wir die Plattform Matomo, auf der mittels pseudonymisierter Daten von Websitenutzern der Nutzerfluss analysiert und beurteilt werden kann. Dies gibt uns die Möglichkeit Websiteinhalte zu optimieren.

Name Zweck Ablauf Typ Anbieter
_pk_id Wird verwendet, um ein paar Details über den Benutzer wie die eindeutige Besucher-ID zu speichern. 13 Monate HTML Matomo
_pk_ref Wird benutzt, um die Informationen der Herkunftswebsite des Benutzers zu speichern. 6 Monate HTML Matomo
_pk_ses Kurzzeitiges Cookie, um vorübergehende Daten des Besuchs zu speichern. 30 Minuten HTML Matomo