Lehrende/r: Univ.-Prof. Dr. Ernst Althaus
Veranstaltungsart: Seminar
Anzeige im Stundenplan: 08.079.615
Semesterwochenstunden: 2
Credits: 4,0
Unterrichtssprache: Deutsch
Min. | Max. Teilnehmerzahl: - | -
Voraussetzungen / Organisatorisches: - Voraussetzungen: DSEA oder äquivalent
Inhalt: Wir untersuchen parametrisierte Algorithmen, d.h. wir analysieren die Laufzeit von Algorithmen nicht nur in Abhängigkeit der Eingabegröße n, sondern auch in einem anderen gewählten Parameter k, wie z.B. der größe der Lösung. Ein Problem erlaubt einen parametrisieten Agorithmus, wenn ein Algorithmus mit einer Laufzeit von f(k) p(n) existiert, wobei f eine berechenbare Funktion, k der Parameter, p ein beliebiges Polynom und n die Eingabelänge ist. Durch geschickte Wahl eines Parameters, der einerseits in einer realen Anwendung klein ist, anderseits einen parametrisierten Algorithmus zulässt, können oft NP-vollständige Probleme in diesen Anwendungen gelöst werden. In diesem Seminar werden unterschieliche parametrisierte Algorithmen vorgestellt werden.
Empfohlene Literatur: Wird in der Vorbesprechung bekannt gegeben.
Zusätzliche Informationen: Die Vorbesprechung findet am 29.7. um 14:00 Uhr statt. Der Raum wird den Teilnehmern noch bekannt gegeben. Wer verhindert ist, melde sich per Email bei Prof. Althaus
