|
Instructors: Prof. Dr. Petra Berenbrink
Event type:
Lecture + practical course
Displayed in timetable as:
ARA - VL+Üb
Hours per week:
4
Language of instruction:
German/English
Min. | Max. participants:
- | 20
Comments/contents:
Why should computer scientists study and use randomness? Computers appear to behave far too unpredictably as it is! Nevertheless, from the highly theoretical notion of probabilistic theorem proving to the very practical design of PC Ethernet cards, randomness and probabilistic methods play a key role in modern computer science. In these and many other important applications, randomized algorithms are significantly more efficient than the best known deterministic solutions. Furthermore, in most acses the randomized algorithms are also simpler and easier to program. (see M. Mitzenmacher und E. Upfahl, "Probability and Computing", 2005)
In thsi course we will give an introduction to the analysis of randomized algorithms. We will first introduce probabilistic techniques and paradigms used in the developmen tof probabilistic algorithms and analyses. Then we will analyze randomized algorithms from various applications. We will cover the following topics:
- Introduction to stochastics
- Models for randomized algorithms
- Tail estimates
- Martingales
- Markov processes
- Random Walks
- Analysis of randomized algorithms from various applications
In WS 21/22 the class with be taught on-line.
Literature:
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.
|
