Přenáška o použití náhodnosti v algoritmech a protokolech. Náhodnost umožňuje řešit některé úlohy, které jsou bez jejího použití neřešitelné nebo řešitelné méně efektivně.
Probereme metody pro návrh a analýzu takových algoritmů a protokolů, ilustrované na konkrétních problémech. Předpokládá se znalost na úrovni předmětů NDMI084 Úvod do
aproximačních a pravděpodobnostních algoritmů a NTIN022 Pravděpodobnostní techniky.
Poslední úprava: IUUK (11.05.2015)
The course covers the use of randomness in design of efficient algorithms. Use of randomness allows to solve
problems more efficiently or even to solve problems that are otherwise intractable. The course covers techniques
for design of randomized algorithm, demonstrated on concrete problems. We assume knowledge on the level of
the courses NDMI084 Introduction to approximation and randomized algorithms and NTIN022 Probabilistic
Techniques.
Cíl předmětu -
Poslední úprava: IUUK (11.05.2015)
Získat přehled o metodách použití náhodnosti v algoritmech a schopnost takové algoritmy analyzovat.
Poslední úprava: IUUK (11.05.2015)
Teach the students selected techniques of use of randomness in algorithms and of analysis of such algorithms.
Literatura -
Poslední úprava: IUUK (11.05.2015)
M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge Univ. Press, 2005.
R. Motwani, P. Raghavan: Randomized algorithms. Cambridge Univ. Press, 1995.
Poslední úprava: IUUK (11.05.2015)
M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge Univ. Press, 2005.
R. Motwani, P. Raghavan: Randomized algorithms. Cambridge Univ. Press, 1995.
Sylabus -
Poslední úprava: IUUK (11.05.2015)
Příklady pravděpodobnostních algoritmů a protokolů
Třídy pravděpodobnostních algoritmů a jejich vztahy
Věty o minimaxu (von Neumann, Yao)
Techniky pro omezení počtu náhodných bitů: po dvou nezávislé proměnné, expandery
Markovovy řetězce a jejich použití: náhodné procházky a testování souvislosti grafů, algoritmy pro splnitelnost, přibližné počítání (splňující ohodnocení, párování v hustých grafech), coupling (počítání obarvení grafů)
Classes of languages defined by randomized algorithms and their relations
Minimax theorems (von Neumann, Yao)
Methods of derandomization: pairwise independent variables, expanders
Markov chains and their applications: random walks and connectivity, satisfiability algorithms, approximate counting (satisfying assignments, matchings in dense graphs), coupling (counting of graph colorings)
Introduction into queuing theory
Streaming algorithms
Randomized protocols and verification: linearity testing, PCP theorem (the proof of the exponential version)