 |
Randomisierte Algorithmen
| Dozent |
Rolf Wanka |
Modulbeschreibung
|
Randomisierte Algorithmen |
| Umfang |
V2 + Ü2,
Studierende der Informatik und CE
|
Ort
und Zeit der Vorlesung
|
Do. 8:15-9:45, 0.031
|
Ort
und Zeit der Übung
|
Fr. 8:30-10:00, E1.11
|
Beginn der Vorlesung am 5. Mai 2011,
der Übungen am 13. Mai.
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
- Die Probabilistische Methode und ihre Anwendung auf die
Berechnung maximaler Schnitte und unabhängiger Mengen
-
Random Walks und ihre Anwendung auf das Erfüllbarkeitsproblem
-
Universelles Hashing und seine Anwendung beim Routing in
Computer-Netzwerken und dem Aufbau von Peer-to-Peer-Netzwerken
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, 2005.
- J. Hromkovic.
Randomisierte Algorithmen.
Teubner, 2004.
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.
Übungsblätter:
|
|
