Navigation

Randomisierte Algorithmen

Dozent:

Prof. Dr. Rolf Wanka

Modulbeschreibung:

Randomisierte Algorithmen

Umfang/Stunden:

V2 + Ü2, 7.5 ECTS

Zielgruppe:

Studierende der Informatik, Mathematik und CE

Ort und Zeit der Vorlesung:

Dienstag, 14:15 – 15:45 Uhr, Raum 01.150-128

Ort und Zeit der Übungen:

Freitag, 12:15 – 13:45 Uhr, Raum 02.133-113 (Alexander Raß)
Die Übungen finden bis auf Weiteres als Zoom Meeting statt. Der Zugang wird rechtzeitig im StudOn-Kurs bekannt gegeben.

Termine:

  • 21. April 2020: Beginn der Vorlesungen
  • 8. Mai 2020: Beginn der Übungen
  • Die Vorlesung entfällt am 2. Juni 2020 (Dienstag nach Pfingsten – Bergdienstag).

Wegen der Corona-Einschränken wird die Lehrveranstaltung bis auf Weiteres „digital“ bzw. „online“ stattfinden. Bitte melden Sie sich bei StudOn an und Sie werden weitere Informationen zu gegebener Zeit per Email von uns erhalten.

Anmeldung:

Bitte melden Sie sich im StudOn für den Kurs zur Vorlesung an. Diese Anmeldung dient nicht der Prüfungsanmeldung sondern führt lediglich dazu, dass Sie in den Mailverteiler zu dieser Vorlesung aufgenommen werden.

Ziele:

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

Skript:

Ein vorläufiges Skript, welches im Laufe des Semesters vervollständigt wird finden Sie im StudOn-Kurs zur Vorlesung.

Übungsblätter

Die aktuellen Übungsblätter finden Sie im StudOn-Kurs zur Vorlesung.

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.