Angelika Steger: Katalogdaten im Herbstsemester 2020 |  |
| Name | Frau Prof. Dr. Angelika Steger |
| Lehrgebiet | Informatik (Theoretische Informatik) |
| Adresse | Inst. f. Theoretische Informatik ETH Zürich, OAT Z 27 Andreasstrasse 5 8092 Zürich SWITZERLAND |
| steger@inf.ethz.ch | |
| URL | http://www.cadmo.ethz.ch/as/people/professor/asteger/index |
| Departement | Informatik |
| Beziehung | Ordentliche Professorin |
| Nummer | Titel | ECTS | Umfang | Dozierende | |
|---|---|---|---|---|---|
| 252-0417-00L | Randomized Algorithms and Probabilistic Methods Findet dieses Semester nicht statt. | 10 KP | 3V + 2U + 4A | A. Steger | |
| Kurzbeschreibung | Las Vegas & Monte Carlo algorithms; inequalities of Markov, Chebyshev, Chernoff; negative correlation; Markov chains: convergence, rapidly mixing; generating functions; Examples include: min cut, median, balls and bins, routing in hypercubes, 3SAT, card shuffling, random walks | ||||
| Lernziel | After this course students will know fundamental techniques from probabilistic combinatorics for designing randomized algorithms and will be able to apply them to solve typical problems in these areas. | ||||
| Inhalt | Randomized Algorithms are algorithms that "flip coins" to take certain decisions. This concept extends the classical model of deterministic algorithms and has become very popular and useful within the last twenty years. In many cases, randomized algorithms are faster, simpler or just more elegant than deterministic ones. In the course, we will discuss basic principles and techniques and derive from them a number of randomized methods for problems in different areas. | ||||
| Skript | Yes. | ||||
| Literatur | - Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press (1995) - Probability and Computing, Michael Mitzenmacher and Eli Upfal, Cambridge University Press (2005) | ||||