|
Vorlesung: Approximationsalgorithmen für NP-harte Probleme
(SS 2001)
Beschreibung:
Viele auch in der Praxis relevante Optimierungsprobleme gehören zur
Klasse der sog. NP-harten Probleme, d.h. man kennt bisher für keines
dieser Probleme einen Algorithmus, der in polynomieller Zeit eine optimale
Lösung berechnet. Eine Möglichkeit zur Behandlung NP-harter Optimierungsprobleme
ist der Verzicht auf eine optimale Lösung. In vielen Fällen können
Algorithmen konstruiert werden, die in polynomieller Zeit eine Näherungslösung
bestimmen, die nachweislich nahe der optimalen Lösung liegt. Die Vorlesung
soll in die Methoden dieses aktuellen Forschungsgebietes der Theoretischen
Informatik bzw. Disketen Mathematik einführen.
Bereich:
A/C
Termin:
Di, 8-10 und Do, 8-10
A207
Übungen:
nach Absprache
Literatur:
|