Randomisierte Algorithmik

  • Typ: Vorlesung / Übung (VÜ)
  • Ort:

    50.34 Raum 236

  • Zeit:

    Di 09:45 - 11:15, 14-täglich (erstmals am 22.10., siehe unten!)
    Do 11:30 - 13:00, wöchentlich (erstmals am 24.10.)

  • Dozent:

    Dr. Stefan Walzer

  • SWS: 3
  • LVNr.: 2400153
  • Hinweis: Präsenz
Inhalt

Randomisierte Algorithmen und Datenstrukturen machen ihr Vorgehen von Zufallsexperimenten abhängig. Während der Entwurf deterministischer Algorithmen oft von einer pessimistischen Sicht auf Worst-Case Verhalten getrieben ist, greifen randomisierte Algorithmen auf Ansätze zurück, die zwar gelegentlich versagen aber meistens wesentlich besser abschneiden.

Die Laufzeit solcher Algorithmen sowie die Lösungsqualität (im Falle von Optimierungsproblemen) und manchmal auch die Korrektheit (im Falle von Berechnungsproblemen) sind dann dem Zufall unterworfen. Eine formale Analyse nimmt daher Erwartungswerte und Erfolgswahrscheinlichkeiten in den Blick. Wir werden uns sowohl klassischen Beispielen als auch aktuellen Forschungsthemen aus dem Bereich Hashing und der Graphentheorie widmen. Hierbei kommen spezifische Entwurfsmethoden (wie Probability Amplification) und fortgeschrittene Analysewerkzeuge der Wahrscheinlichkeitstheorie (etwa Coupling, Poissonisierung und Konzentrationsschranken) zur Anwendung. Oft wird sich zeigen, dass randomisierte Ansätze effizienter oder einfacher sind als alle (oder zumindest alle bekannten) deterministischen Ansätze.

Kurz werden wir zudem auf theoretischer Seite betrachten, wie sich randomisierte Komplexitätsklassen zu bekannten Klassen wie P und NP verhalten, und auf praktischer Seite klären, wie man randomisierte Algorithmen auf gängigen (im Wesentlichen deterministisch arbeitenden) Computern mit Pseudozufall implementieren kann.

Vortragssprache Deutsch mit Englischen Folien

Material zu Vorlesung und Übung

Wichtig: Die Übung am 22.10. findet statt. Dort werden einige Grundbegriffe der Stochastik und einfache Rechenregeln behandelt (siehe Lecture 0 unten). Wer eine Einführungsvorlesung in die Stochastik besucht hat, wird vieles schon kennen. Bitte entscheide selbst, ob du von einer solchen Auffrischung profitierst und erscheine zur Übung – oder eben auch nicht.

Lecture 0: Basic Notions and Notation / Exercises