Randomisierte Algorithmen

Dozent:

Prof. Dr. Rolf Wanka

Modulbeschreibung:

Randomisierte Algorithmen

Umfang/Stunden:

V2 + Ü2, 7.5 ECTS

Zielgruppe:

  • Informatik
  • Mathematik
  • Computational Engineering

Ort und Zeit der Vorlesung:

Dienstag, 08:15 – 09:45 Uhr

Ort und Zeit der Übung:

Mittwoch, 14:15 – 15:45 Uhr

Termine:

  • 13. April 2021: Beginn der Vorlesungen
  • 21. April 2021: Beginn der Übungen

Aufgrund der Corona-Einschränkungen findet die Lehrveranstaltung bis auf Weiteres „digital“ bzw. „online“ statt. Bitte melden Sie sich bei StudOn an um dort die zugehörigen Zoom-Links zu gegebener Zeit zu erhalten.

Anmeldung:

Bitte melden Sie sich in StudOn für den Kurs zur Vorlesung an. Die kursbegleitenden Materialien werden dort zur Verfügung gestellt.

Ziele:

Vorstellung grundlegender Techniken beim Entwurf und der Analyse zufallsbasierter, d.h. randomisierter Algorithmen

Beschreibung:

Bei der Lösung kombinatorischer oder zahlentheoretischer Probleme ist es oft möglich, durch Würfeln schnell und einfach mit hoher Wahrscheinklichkeit oder im Durchschnitt zu hervorragenden Lösungen zu kommen. In dieser Vorlesung lernen wir Konzepte wie die Probabilistische Methode, Irrläufe (Random Walks) und Varianzanalysen von Zufallsprozessen kennen und wenden sie auf graphentheoretische Probleme und effiziente Datenstrukturen an.

Inhalte:

  • Schnelle Wiederholung wahrscheinlichkeitstheoretischer Begriffe und Resultate
  • Zwei einführende Beispiele: Quicksort und Min-CUT
  • Die Probabilistische Methode und ihre Anwendung auf die Berechnung maximaler Schnitte und unabhängiger Mengen
  • Random Walks und ihre Anwendung auf das Erfüllbarkeitsproblem
  • Approximate Counting: Die Markov-Chain-Monte-Carlo-Methode

Unterlagen:

Die Folien zum Erfüllbarkeitsproblem finden Sie hier.

Literatur:

Speziell zu Randomisierten Algorithmen:

  • R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
  • M. Mitzenmacher, E. Upfal. Probability and Computing – Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2nd ed., 2017.
  • J. Hromkovic. Randomisierte Algorithmen. Teubner, 2004.

Zum letzten Kapitel der Vorlesung über Approximate Counting

Zur Wahrscheinlichkeitsrechnung:

  • W. Feller. An Introduction to Probability Theory and Its Applications. Wiley, 3rd Ed. 1970.
  • T. Schickinger, A. Steger. Diskrete Strukturen – Band 2: Wahrscheinlichkeitstheorie und Statistik. Springer, 2002.