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.

Lernziele:

Die Studierenden

- verstehen, wann und warum Randomisierung zur Lösung eines algorithmischen Problems nützlich oder notwendig ist,

- können zentrale Entwurfsmethoden und Analysewerkzeuge der randomisierten Algorithmik erklären,

- können einfache randomisierte Algorithmen und Datenstrukturen zur Lösung eines Problems entwerfen und erklären,

- können entscheiden, welche Werkzeuge sich für die Analyse gegebener randomisierter Algorithmen und Datenstrukturen eignen und diese anwenden.

Arbeitsaufwand:

Vorlesung mit Übung mit 3 SWS, 5 LP

1. 45h Besuch der Vorlesung und Übung
2. 30h Vor- und Nachbereitung
3. 45h Bearbeitung der Übungsblätter

ca. 30h Prüfungsvorbereitung

Empfehlungen:

Grundkenntnisse über Algorithmen und Datenstrukturen (z.B. aus den Vorlesungen Algorithmen 1 + 2) sowie Grundlagen aus der Wahrscheinlichkeitstheorie (bspw. aus der Vorlesung Einführung in die Stochastik) sind hilfreich.