Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

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

Übungsblätter

Letzte Änderung am 25.01.2018 von T. Kesselheim