186.102 Approximation Algorithms
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2018W, VU, 2.0h, 3.0EC, wird geblockt abgehalten

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung

Ziele der Lehrveranstaltung

- Verständnis für die Begriffe von exakten und approximativen Lösungen
- Fähigkeit zur eigenständigen Analyse von Approximationsgüten
- Kenntnis von klassischen Approximationsresultaten für diskrete Optimierungsprobleme
- Fähigkeit Publikationen über Approximationsalgorithmen zu verstehen

Inhalt der Lehrveranstaltung

- Qualitätsmaße von Approximationsalgorithmen
- Schemata von Heuristiken und Methoden der Approximationsabschätzung
- Heuristiken und ihre Analyse für Bin Packing, Scheduling, Knapsack, TSP, Vertex Cover und Set Cover Probleme

Weitere Informationen

ECTS-Breakdown:

21h   Vorlesung
20h   Vorbereitung der Übungsbeispiele
  6h   Präsentation der Übungsbeispiele
25h   Prüfungsvorbereitung
  3h   Prüfung
-----
75h   total 


Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Do.15:00 - 18:0018.10.2018Seminarraum FAV 05 (Seminarraum 186) Approximationsalgorithmen
Fr.15:00 - 18:0019.10.2018Seminarraum FAV 05 (Seminarraum 186) Approximation algorithms
Mi.15:00 - 17:0031.10.2018 Seminarraum 183/2Approximationsalgorithmen
Do.15:00 - 18:0008.11.2018Seminarraum FAV 05 (Seminarraum 186) Approximationsalgorithmen
Do.14:30 - 17:0015.11.2018Seminarraum FAV 05 (Seminarraum 186) Apprximation Algorithms
Do.16:00 - 19:0022.11.2018Seminarraum FAV 01 A (Seminarraum 183/2) Approximationsalgorithmen
Fr.15:00 - 18:0023.11.2018Seminarraum FAV 05 (Seminarraum 186) Approximationsalgorithmen
Mo.15:00 - 17:0026.11.2018 Seminarraum 183/2Approximationsalgorithmen
Mo.15:00 - 17:0003.12.2018 Seminarraum 183/2Approximationsalgorithmen
Mo.15:00 - 17:0010.12.2018Seminarraum FAV 01 A (Seminarraum 183/2) Approximationsalgorithmen
Mo.15:00 - 17:0017.12.2018Seminarraum FAV 01 A (Seminarraum 183/2) Klausur
LVA wird geblockt abgehalten

Leistungsnachweis

- Drei Übungsblätter mit Kreuzelliste
- aktive Mitarbeiter in der LV
- mündliche Prüfung (ca. 20 Minuten) nach Abschluss der LV.

LVA-Anmeldung

Von Bis Abmeldung bis
01.10.2018 00:00 16.10.2018 23:59

Curricula

Literatur

K.  Jansen, M.  Margraf, Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008.

R. Wanka, Approximationsalgorithmen: Eine Einführung, Teubner, 2006.

D.S. Hochbaum,  Approximation algorithms for NP-hard problems, PWS Publishing Company, 1997.

V.V. Vazirani,  Approximation Algorithms,  Springer, 2001.

G. Ausiello et al., Complexity & Approximation, Springer, 1999.

Vorkenntnisse

Kenntnisse über grundlegende Algorithmen und Datenstrukturen, einfache Beweistechniken

Begleitende Lehrveranstaltungen

Sprache

Deutsch