Lecturer: Dr. Mihyun Kang
Termine
Lecture begins on: 21.10.2004| VL | Thursday | 15:00 - 17:00 | (RUD 26, 1.308) |
|---|---|---|---|
| Friday | 09:00 - 11:00 | (RUD 26, 1.308) | |
| UE | Wednesday | 15:00 - 17:00 | (RUD 26, 1.308) Taral Seierstad |
| Office hour | Friday | 12:00 - 13:00 | (RUD 25, 3.417) |
| and by appointment | |||
Zuordnung
- Hauptstudium, Halbkurs
- Theoretische Informatik
Inhalte und Lernziele
Randomized algorithms and probabilistic analysis are important tools in algorithm design and complexity theory. Randomness used in algorithms often leads to much faster algorithms that are easier to analyze than determinsitic algorithms, and the probabilistic viewpoint is essential to understand some computational models. This course covers basic probability theory, random graphs, random walks and Markov chain Monte Carlo methods.
The participants will learn how to use randomness in designing efficient algorithms and to analyze randomized algorithms using probabilistic methods.
Voraussetzungen
The prerequisite is basic knowledge in discrete mathematics. The language of the course is English.
Empfohlene Literatur
- , The Probabilistic Method, Cambridge University Press, 1995.
- , Random Graphs, Cambridge University Press, 2002.
- , Probabilistic Analysis of Algorithms in Probabilistic Methods for Algorithmic Discrete Mathematics (M. Habib, C. McDiarmid, J. Ramirez-Alfonsin and B. Reed eds.), Algorithms and combinatorics 16, Springer, 1998.
- , Random Graphs, John Wiley & Sons, Inc., 2000.
- , Mathematical foundations of the Markov chain Monte Carlo method in Probabilistic Methods for Algorithmic Discrete Mathematics (M. Habib, C. McDiarmid, J. Ramirez-Alfonsin and B. Reed eds.), Algorithms and combinatorics 16, Springer, 1998.
- , The Probabilistic Method.
- , Randomized Algorithms, John Wiley & Sons, Inc., 1992.
English