Seiteninterne Suche

Lehre

Randomisierte Algorithmen

Dozent:

Prof. Dr. rer. nat. 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, 10:15 – 11:45 Uhr, Raum 02.133-113

Ort und Zeit der Übungen:

Dienstag. 14:00 – 15:30 Uhr, Raum 02.133-113 (Alexander Raß)

Termine:

  • Die Vorlesung beginnt am 25. April.
  • Der Übungsbetrieb beginnt am 2. Mai.
  • Die Vorlesung und die Übung entfallen am 6. Juni (Dienstag nach Pfingsten – Bergdienstag).

Anmeldung:

Bitte melden Sie sich im EST für die Vorlesung an. Benutzen Sie im EST die Veranstaltungsanmeldung. Dort können Sie die Veranstaltung Randomisierte Algorithmen (SS 17) auswählen. Das Anmeldepasswort erhalten Sie in der Vorlesung und in der Übung. Als Bestätigung für die erfolgreiche Anmeldung erhalten Sie eine Email. 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

Übungsblätter

Blatt 1 Blatt 2 Blatt 3
Blatt 4 Blatt 5 Blatt 6
Blatt 7 Blatt 8 Blatt 9
Blatt 10

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 und den Nachweis der Existenz von Expander-Graphen
  • 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.

Die Ausarbeitung zu den Konzentratoren 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, 2005.
  • 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.