Vorlesung (Hauptstudium)
Approximationsalgorithmen für NP-harte Probleme
Prof. Dr. Norbert Blum
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, d°ie 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. Diskreten Mathematik einführen.
| Zeit, Ort | Mi 9-11, HS 1 |
| Semesterwochenstunden | 2V + 1Ü |
| Übungen | n.Vereinb. (Prof. Dr. Norbert Blum u.M.) |
| Bereich (alte DPO) | A |
| Bereich (neue DPO) | A1 |
| Email-Kontakt | kretschm@cs.uni-bonn.de |
|
Übersicht: alle Semester
Selected Topics in Data Structures
Einführung in die Informations- und Lerntheorie