Hochschule Darmstadt - Fb Informatik

Drucken| Layout| Design| Schriftgröße English|
Modulbeschreibung
Modul:Approximation Algorithms

Approximationsalgorithmen

Belegnummern:41.4966 [PVL 41.4967]
Sprache:deutsch
Zuordnung:CNAM - Masterzyklus
CNAM Master - Masterzyklus
Dualer Master 2013 - Katalog T: Theorieorientierte Module
JIM 2013 - Elective Catalogue T
Master 2013 - Katalog T: Theorieorientierte Module
Master 2006 - Katalog T: Theorieorientierte Module
MN Data Science 2016 - Katalog DS-I: Data Science - Informatik
Lehrform:V+Ü = Vorlesung+Übung
SWS:3+1
CP:6
Prüfung:Klausur
Anmeldung zur Prüfung:explizit und unabhängig von der Belegung
PVL (z.B. Praktikum):unbenotet (Erfolgreiche Teilnahme an den Übungen: Die Prüfungsvorleistung ist erbracht worden, wenn 50% der Übungsaufgaben bearbeitet wurden, korrekte Lösungen für zwei Übungsaufgaben im Rahmen der Übung vorgestellt wurden und eine korrekte Musterlösung für eine Übungsaufgabe ausgearbeitet und abgegeben wurde.)
Häufigkeit des Angebots:jährlich
Erforderliche Vorkenntnisse:Modul Algorithmik
Lernziele:Im Mittelpunkt stehen folgende Lernziele:
  • Verständnis ausgewählter Prinzipien zum Entwurf approximativer Algorithmen
  • Analysefähigkeit in Bezug auf die Schwere eines Optimierungsproblems
  • Kenntnis von approximativen Algorithmen für unterschiedliche Problembereiche
  • Fähigkeit, Algorithmen in Bezug auf die Güte der von ihnen bestimmten Lösungen und auf deren Laufzeit zu analysieren
Lehrinhalte:
  • Grundbegriffe
    • Approximationsalgorithmen
    • relative Approximationsgüte
  • Komplexitätstheoretische Grundlagen
    • Komplexitätsklassen P und NP
    • NP-vollständige Entscheidungsprobleme
    • NP-schwere und streng NP-schwere Optimierungsprobleme
  • Approximationsalgorithmen mit konstanter Güte für ausgewählte Optimierungsprobleme, u.a. aus den Bereichen
    • Graphentheorie
    • Prozessoptimierung
  • Approximationsschemata
    • einfache Approximationsschemata
    • vollständige Approximationsschemata
  • Approximationsalgorithmen nichtkonstanter Güte für ausgewählte graphentheoretische Optimierungsprobleme
  • Entwurfstechnik Lineare Programmierung
  • Entwurfstechnik Randomisierung
    • Randomisierte Algorithmen
    • Randomisierte Approximationsalgorithmen und deren Derandomisierung
  • Grenzen der Approximierbarkeit von Optimierungsproblemen
    • Probleme, für die es keine Approximationsalgorithmen konstanter Güte gibt
    • Probleme, für die es keine einfachen bzw. vollständigen Approximationsschemata gibt
Literatur:
  • Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization 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. Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008.
Arbeitsformen / Hilfsmittel:Ausführliches Vorlesungsskript (170 Seiten),Folien
Modulverantwortung:Steffen Lange
Freigabe ab:SS 2015
Angebot im SS 20:Lange
Fachliche Kompetenzen:
  • Formale, algorithmische, mathematische Kompetenzen: hoch
  • Analyse-, Design- und Realisierungskompetenzen: mittel
  • Befähigung zum Wissenschaftlichen Arbeiten: mittel
Überfachliche Kompetenzen:
  • Fachübergreifende Sachkompetenzen: Mathematische und naturwissenschaftliche Grundkompetenz

[Fachbereich Informatik] [Hochschule Darmstadt]
© 2008 - 2020 FBI OBS Team. Alle Rechte vorbehalten.