Ausgewählte Kapitel der Algorithmik:
Algorithmen und Unsicherheit
im Wintersemester 2017/18
Veranstalter: | Jun.-Prof. Dr. Thomas Kesselheim |
Termine: | Vorlesung | Donnerstag | 14:15-16:00 Uhr | OH14-304 |
| Übung | Mittwoch | 14:15-16:00 Uhr | OH16-205 |
Beginn: | Donnerstag, den 12.10.2017 |
Aktuelles
- Anmerkungen zur Prüfung: Ein sehr wichtiges Lernziel ist es, Konzepte kennenzulernen. Deshalb ist es auch wichtig, die Definitionen gut zu kennen, und erklären zu können. Wichtig ist weiterhin, welche Zusammenhänge es gibt, welche Sätze wir gezeigt haben, und wie wir dabei vorgegangen sind. Einige Beweise bestehen aus längeren Rechnungen (ganz besonders zum Beispiel in Vorlesung 3). Diese Rechnungen müssen in der Prüfung nicht wiedergegeben werden können, wohl aber die Idee, wo sie anfängt, aufhört, was sie benutzt.
Wie bei jeder mündlichen Prüfung ist es sehr sinnvoll, sich mit Kommiliton*innen gemeinsam vorzubereiten. Gerade Studierende, die sich lieber alleine vorbereiten, sollten üben, Konzepte zu erklären. Es hilft, typische Fragen laut gesprochen zu beantworten — auch wenn niemand dabei zuhört.
- Zur Erinnerung: Die Lösungen zum letzten Übungsblatt, Übungsblatt 12, werden in der Übung am 31. Januar abgegeben. Besprochen werden sie in einer Übung am 1. Februar zum Vorlesungstermin.
- Die mündlichen Prüfungen finden im Februar und März statt. Zur Auswahl stehen folgende Termine, weitere Termine nach Absprache möglich: 6., 15., 20., 27. Februar, 13. und 20. März. Bitte meldet euch bei Thomas zur Terminvereinbarung.
Zusammenfassung
In vielen praktischen Anwendungsszenarien müssen Algorithmen Entscheidungen treffen auf Basis von unsicheren oder unvollständigen Eingaben.
Ein Navigationssystem muss eine Route berechnen, ohne die genaue Verkehrslage zu kennen. Eine Fluggesellschaft plant Flüge und verkauft Tickets, ohne genauen Bedarf zu kennen.
In dieser Veranstaltung lernen wir verschiedene Arten kennen, Unsicherheiten zu modellieren und Algorithmen zu entwerfen, die mit ihnen umgehen können. Beispielsweise:
- Online-Algorithmen
- Online-Lern-Algorithmen
- Markowsche Entscheidungsprozesse
- Mehrphasenoptimierung
Alle Ergebnisse werden formal bewiesen werden. Voraussetzung sind grundlegende Kenntnisse in Algorithmentheorie und Wahrscheinlichkeitsrechnung.
Materialien
- Vorlesungsskript 12.10.2017, Online Matching
- Vorlesungsskript 19.10.2017, Online Paging
- Vorlesungsskript 26.10.2017, Fractional Set Cover
Alternativversion, die auf LP-Notation verzichtet
- Vorlesungsskript 02.11.2017, Set Cover via Randomized Rounding
- Vorlesungsskript 09.11.2017, Yao's Principle
- Vorlesungsskript 16.11.2017, Secretary Problem
- Vorlesungsskript 23.11.2017, Secretary Matching
- Vorlesungsskript 28.11.2017, No-Regret Learning: Experts
- Vorlesungsskript 30.11.2017, No-Regret Learning: Bandits (Fehler aus der Vorlesung ist korrigiert.)
- Vorlesungsskript 19.12.2017, Markov Decision Processes
- Vorlesungsskript 21.12.2017, Gittins Index Theorem
- Vorlesungsskript 10.01.2018, Stochastic Vertex Cover/Stochastic Set Cover
- Vorlesungsskript 11.01.2018, Stochastic Steiner Tree
- Vorlesungsskript 18.01.2018, PAC Learning
- Vorlesungsskript 25.01.2018, VC Dimension
Übungsblätter
- Übungsblatt 1, Abgabe am 19.10.2017
- Übungsblatt 2, Abgabe am 26.10.2017
- Übungsblatt 3, Abgabe am 02.11.2017
- Übungsblatt 4, Abgabe am 09.11.2017
- Übungsblatt 5, Abgabe am 16.11.2017
- Übungsblatt 6, Abgabe am 23.11.2017
- Übungsblatt 7, Abgabe am 28.11.2017
- Übungsblatt 8, Abgabe am 19.12.2017
- Übungsblatt 9, Abgabe am 11.01.2018
- Übungsblatt 10, Abgabe am 18.01.2018
- Übungsblatt 11, Abgabe am 25.01.2018
- Übungsblatt 12, Abgabe am 31.01.2018
Letzte Änderung am 25.01.2018 von T. Kesselheim