WiSe 19/20: Approximationsalgorithmen
Wolfgang Mulzer
Zusätzl. Angaben / Voraussetzungen
Zielgruppe
Informatiker_innen und Mathematiker_innen im fortgeschrittenen Bachelorstudium oder im Masterstudium.
Empfohlene Vorkennntnisse
"Höhere Algorithmik" oder eine andere Vorlesung ähnlichen Inhalts.
SchließenKommentar
Inhalt:
Diese Veranstaltung ist eine Fortsetzung der Vorlesung Höhere Algorithmik. Viele fundamentale, insbesondere auch für Anwendungen wichtige Optimierungsprobleme, sind NP-schwer, d.h. sie lassen sich in der Praxis nicht exakt lösen (sofern P ungleich NP ist). Daher stellt sich die Frage, wie gut sich optimale Lösungen approximieren lassen.
Es zeigt sich, daß sich für viele Probleme tatsächlich Lösungen effizient berechnen lassen, die dicht am Optimum liegen, während andere Probleme beweisbar jedem Approximationsversuch widerstehen.
In dieser Vorlesung beschäftigen wir uns mit dem Gebiet der Approximationsalgorithmen, auf dem sich in letzter Zeit viel getan hat. Einerseits behandeln wir den Entwurf und die Analyse solcher Algorithmen. Andererseits lernen wir die Grenzen kennen, die jedem Näherungsverfahren gesetzt sind.
SchließenLiteraturhinweise
Wird noch bekannt gegeben.
32 Termine
Regelmäßige Termine der Lehrveranstaltung
Inhalt:
Diese Veranstaltung ist eine Fortsetzung der Vorlesung Höhere Algorithmik. Viele fundamentale, insbesondere auch für Anwendungen wichtige ... Lesen Sie weiter