64-364 Vorlesung Randomisierte Algorithmen
Lehrende:
Prof. Dr. Petra Berenbrink
Zeit/Ort:
Di, 08:15 bis 11:45, G-228
Kommentare/ Inhalte:
Warum sollten Informatiker Randomisieung untersuchen und verwenden? Verhalten sich moderne Computersysteme nicht ohnehin schon oft sehr unvorhersagbar? Ist es nicht auch ohne randomisierung schon schwierig genug, Computer effizient zu benutzen? Dennoch: Randomisierung und probabilistische Methoden spielen in der modernen Computerwissenschaft eine zentrale Rolle. In vielen Anwendungsbereichen, von klassischen Ethernet-Netzwerkkarten bis hin zu Primzahlentests in der Kryptographie, sind randomisierte Algorithmen effizienter als die besten bekannten deterministischen Lösungen. Zudem sind sie oftmals einfacher und leicht zu implementieren. (Frei nach M. Mitzenmacher und E. Upfahl, "Probability and Computing", 2005)
In dieser Vorlesung behandeln wir die Grundlagen der Analyse randomisierter Algorithmen. Diese Vorlesung vermittelt wichtige Grundlagen insbesonders für Vertiefungsgebiete wie Machine Learning und Algorithmen für grosse Datenmengen. In beiden Bereichen wird sehr oft auf Randomisierung zurueckgegriffen!
Dabei führen wir zuerst die für Design und Analyse randomisierter Algorithmen notwendigen probabilistischen Techniken und Paradigmen ein. Anschließend analysieren wir randomisierte Algorithmen aus verschiedensten Anwendungsbereichen. Die Inhalte umfassen unter anderem die folgenden Punkte.
Grundlagen der Stochastik
Modelle randomisierter Algorithmen
Tail Estimates
Martingales
Markov Prozesse
Random Walks
Coupling Techniken
Analyse randomisierter Algorithmen aus den verschiedensten Anwendungsbereichen
Literatur:
Michael Mitzenmacher and Eli Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
Rajeev Motwani and Prabhakar Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
Devdatt P. Dubhashi and Alessandro Panconesi: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009.