Randomisierte Algorithmen (Vorlesung)

Randomisierte Algorithmen verwenden Zufallsschritte, um eine Entscheidung zu fällen. Diese Zufallsschritte werden benutzt, um eine Entscheidung möglichst korrekt zu treffen oder die Laufzeit einer Berechnung zu verbessern. Als kleine Beispiele sollen dienen:

  • Mehrheitsbestimmung
    Eine Urne enthält rote und blaue Kugeln. Ziehen Sie eine Kugel, und mit hoher Wahrscheinlichkeit ist die gezogene Kugel von der mehrheitlich vorkommenden Farbe. Um die Entscheidung sicherer zu treffen, wiederholen Sie das Experiment, und mit jeder neuen Kugel erhöht sich die Sicherheit. Es gilt allerdings: Solange Kugeln in der Urne verbleiben, gibt es keine Sicherheit über das richtige Ergebnis.
  • Mittelwertbestimmung
    In einer unsortierten Folge von Zahlen wollen Sie den Median bestimmen, also diejenige Zahl, die in der sortierten Folge in der Mitte steht. Sie können die Folge sortieren und in der sortierten Folge das entsprechende Element abzählen. Sie können aber auch zufällig den Median raten und durch Aufteilen der Folge in größere und kleine Zahlen die Korrektheit verifizieren. Sind die beiden Mengen ungleich groß, wird die Prozedur wiederholt durch Wahl einer Zahl aus der größeren Menge.

Die beiden Beispielprobleme beschreiben typische randomisierte Algorithmen und die Verwendung des Zufalls: Bei der Mehrheitsbestimmung ist das Ergebnis nur mit hoher Wahrscheinlichkeit korrekt, wobei die Korrektheitswahrscheinlichkeit durch Wiederholung beliebig verbessert werden kann, und bei der Mittelwertbestimmung nutzt der Zufall der Laufzeit, das Ergebnis ist aber in jedem Fall korrekt. Die Verwendung von Zufallsschritten kann also zu schnellen und einfachen Algorithmen führen.

Vorlesungsinhalt

Die Vorlesung bietet einen Einstieg in das Thema. Behandelt werden Grundtechniken zum Entwurf und zur Analyse randomisierter Algorithmen. Diese Techniken werden anhand von ausgewählten Problemen aus verschiedenen Anwendungsfeldern untersucht. Neben diesen konkreten Untersuchungen werden grundsätzliche Fragestellungen untersucht, nämlich, welche Probleme sich überhaupt durch randomisierte Algorithmen (sinnvoll) lösen lassen und wie sich Problemklassen für verschiedene algorithmische Ansätze zueinander verhalten.

Teilnahmevoraussetzungen

Die Teilnehmer sollten Grundkenntnisse aus der Theoretischen Informatik, insbesondere in den Bereichen der Algorithmenanalyse (Korrektheit und Laufzeit), und der Wahrscheinlichkeitsrechnung besitzen.

Termine

Vorlesungfreitags, 14 Uhr s.t.H 7
ÜbungvierzehntäglichH 405

Dozent

Daniel Meister