|
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: | -
Master (universitär) /
Angewandte Mathematik /
PO 2008
-
Master (universitär) /
Angewandte Mathematik /
PO 2019
-
Abschluss im Ausland /
Informatik /
keine PO
-
Bachelor (universitär) /
Informatik /
PO 2008
-
Bachelor (universitär) /
Künstliche Intelligenz /
PO 2022
-
Bachelor (universitär) /
Künstliche Intelligenz Technologie /
PO 2022
-
Bachelor (universitär) /
Mathematik /
PO 2019
-
Bachelor (universitär) /
Mathematik /
PO 2023
-
Bachelor (universitär) - Duales Studium, praxisintegrierend /
Mathematik - dual /
PO 2023
-
Bachelor (universitär) /
Wirtschaftsmathematik /
PO 2007
-
Bachelor (universitär) /
Wirtschaftsmathematik /
PO 2023
-
Bachelor (universitär) - Duales Studium, praxisintegrierend /
Wirtschaftsmathematik - dual /
PO 2023
|
| Bemerkungen: | - Studiengang Informatik B.Sc.: Wahlpflichtmodul in Komplex „Grundlagen der Informatik“ (Niveaustufe 300)
- Studiengang Künstliche Intelligenz B.Sc.: Wahlpflichtmodul im Komplex „Methodische Grundlagen“
- Studiengang Künstliche Intelligenz Technologie B.Sc.: Wahlpflichtmodul imKomplex „Software-basierte Systeme“
- Studiengang Angewandte Mathematik M.Sc.: Wahlpflichtmodul im Komplex „Optimierung“ und im Komplex „Anwendungen“, Bereich „Informatik“
- 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: | |
