Randomisierte Algorithmen

Dozent:

Prof. Dr. Rolf Wanka

Modulbeschreibung:

Randomisierte Algorithmen

Umfang/Stunden:

V2 + Ü2, 7.5 ECTS

Zielgruppe:

• Informatik
• Mathematik
• Computational Engineering

Übungsleiter:

Matthias Kergaßner

Vorlesung:

• Erste Vorlesung: 16.04.2024
• Termin: Dienstags 14:15 – 15:45 Uhr
• Raum: 11302.02.134 (02.134-113 Übungsraum)

Übung:

• Erste Übung: 24.04.2024
• Termin: Mittwochs 16:15 – 17:45 Uhr
• Raum: 11501.01.019 (01.019 Seminarraum)

Anmeldung:

Bitte melden Sie sich in StudOn für den Kurs zur Vorlesung an. Die kursbegleitenden Materialien werden dort zur Verfügung gestellt.
Der StudOn-Kurs zur Übung wird für den Versand der Evaluations-TANs genutzt.

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

• R. Wanka. Approximationsalgorithmen – Eine Einführung Teubner, 2006.
  doi:10.1007/978-3-8351-9067-2
  insbesondere das Kapitel 8: Approximate Counting und die Monte-Carlo-Methode

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.