Prüfung
BTU-Vorlesungsverzeichnis ↗- Sonntag—01:00 bis 02:30
← Zurück zur Übersicht
12329Fakultät 1 – MINT – Mathematik, Informatik, Physik, Elektro- und Informationstechnik
Approximationsalgorithmen
Titel auf Englisch: Approximation Algorithms
Lernergebnisse
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
Voraussetzungen
Verpflichtende Voraussetzungen
Keine
Empfohlene Voraussetzungen
Prüfungsmodalitäten
Mündliche Prüfung, 30-45 Minuten
Termine im WiSe 26/27
Die einzigen Termine im WiSe 26/27 sind Prüfungstermine – gelehrt wird das Modul in diesem Semester nicht.
Angeboten in
- Angewandte MathematikM.Sc.
Wahlpflichtkomplex: Anwendungen
- Angewandte MathematikM.Sc.
Wahlpflichtkomplex: Informatik
- Angewandte MathematikM.Sc.
Wahlpflichtkomplex: Optimierung
| Studiengang | Abschluss | Wahlpflichtkomplex |
|---|---|---|
| Angewandte Mathematik | M.Sc. | Anwendungen |
| Angewandte Mathematik | M.Sc. | Informatik |
| Angewandte Mathematik | M.Sc. | Optimierung |
Literatur und Materialien
- 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.
Bewertungen von Studierenden
Was Studierende über dieses Modul sagen. Die BTU hat damit nichts zu tun — hier schreiben nur Studierende, und jede Bewertung ist die Meinung einer einzelnen Person.