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.
Last update: IUUK (11.05.2015)
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.
Aim of the course -
Last update: IUUK (11.05.2015)
Teach the students selected techniques of use of randomness in algorithms and of analysis of such algorithms.
Last update: IUUK (11.05.2015)
Získat přehled o metodách použití náhodnosti v algoritmech a schopnost takové algoritmy analyzovat.
Literature -
Last update: 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.
Last update: 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.
Syllabus -
Last update: IUUK (11.05.2015)
Examples of randomized algorithms and protocols
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)
Last update: 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ů)
