Abschnittsübersicht
-
Umfang: 5 ECTS, 2+2 SWS [T:2,P:0] Zeit und Ort: V freitags, 10:15–11:45 Uhr, M2, ÜR 1
Ü dienstags, 10:15–11:45 Uhr, M2, SE 1 (ab dem 25.10.2022)
Die Veranstaltung entfällt an den folgenden Tagen:
V: 11.11., 9.12.
Ü: 2.11., 6.12.Mdl. Prüfungen: 14.02.2023, 9–15 Uhr, M4.00.001 Zielgruppe: Master Informatik, Master Mathematik, Master Computational Mathematics Dozent: Prof. Alexander Wolff Übung: Diana Sieper -
Inhalt
Die Aufgabe eine optimale Lösung für ein gegebenes Problem (Optimierungsproblem) zu ermitteln ist allgegenwärtig in der Informatik. Ein prominentes Beispiel ist das Problem des Handlungsreisenden, bei dem es darum geht eine kürzeste Rundreise zu finden, die eine vorgegebene Menge von Stationen besucht. Leider ist für eine Vielzahl solcher Probleme kein effizienter Algorithmus bekannt, der eine optimale Lösung ermittelt. In der Praxis verwendet man daher häufig Verfahren, die zwar nicht immer optimale aber dafür stets gute Lösungen liefern.
In dieser Vorlesung beschäftigen wir uns mit Entwurfs- und Analysetechniken für solche Algorithmen. Wir betrachten Verfahren, die eine nachweisbare Approximationsgüte besitzen. Unter Approximationsgüte versteht man das Verhältnis zwischen der Qualität einer approximativen Lösung und einer optimalen Lösung. Zum Beispiel garantiert ein Algorithmus mit Approximationsgüte 2 für das Problem des Handlungsreisenden für jede Eingabe eine Rundreise zu finden, die höchstens doppelt so lang ist wie die kürzeste Rundreise (die im Allgemeinen nachweislich schwer zu berechnen ist).
Bei Interesse der Teilnehmer*innen kann auch auf fortgeschrittene Techniken in diesem Themengebiet sowie die Grenzen von Approximierbarkeit eingegangen werden, welche anspruchsvollere mathematische Werkzeuge erfordern.
Lernziele
Am Ende dieses Kurses sollen die Teilnehmer*innen in der Lage sein, einfache Approximationsverfahren bezüglich ihrer Güte zu analysieren. Außerdem sollen sie grundlegende Entwurfstechniken, wie beispielsweise Greedy, lokale Suche, Skalierung, und LP-basierte Methoden, verstehen und anwenden können.
Literatur zur Vorlesung
Approximation Algorithms
Vijay V. Vazirani
Springer, 2003The Design of Approximation Algorithms
David P. Williamson, David B. Shmoys
Cambridge University Press, 2011
Kostenlose Online-Version -
- In der Tabelle unten liefert ein Klick aufs jeweilige Datum die Druckversion der Folien; ein Klick aufs Thema die Langversion.
- Die Videos sind von Joachim Spoerhase aus den Corona-Jahren.
-
Impressum | Datenschutzerklärung - WueCampus | Erklärung zur Barrierefreiheit | Bildnachweise
Navigationsleiste - Rechenzentrum: Data center icons created by Eucalyp - Flaticon
Navigationsleiste - Website Support: Consultant icons created by Vitaly Gorbachev - Flaticon
Navigationsleiste - Häufige Fragen: Files and folders icons created by Freepik - Flaticon
Navigationsleiste - Lehre Digital: Training icons created by vectorspoint - Flaticon
Navigationsleiste - Forschung Digital: Research icons created by Eucalyp - Flaticon
Navigationsleiste - Lecture: Video icons created by Freepik - Flaticon
Werbefeld 2 - WueLogin: Login icons created by Freepik - Flaticon
Werbefeld 3 - Upgrade WueCampus 4.4: Update icons created by Freepik - Flaticon