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.
Last update: IUUK (11.05.2015)
Aim of the course -
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.
Last update: IUUK (11.05.2015)
Course completion requirements -
To pass the tutorials it is required to get at least a half of total points for homeworks assigned during the semester conditioned on regular attendance. If the student does not attend the tutorials regularly, two thirds of total points will be required. Due to the requirements, additional attempts to pass the tutorial are not allowed.
The exam is oral. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam.
Last update: Sgall Jiří, prof. RNDr., DrSc. (22.06.2019)
Pro získání je zápočtu je nutné získat polovinu z celkového počtu bodů za domácí úkoly zadané během semestru za podmínky účasti studenta na cvičeních. Při neúčasti jsou potřeba dvě třetiny z celkového počtu bodů. Povaha kontroly studia neumožňuje opakování zápočtu.
Zkouška je ústní. Požadavky odpovídají sylabu v míře pokryté přednáškami. Zápočet je nutnou podmínkou účasti u zkoušky.
Last update: Sgall Jiří, prof. RNDr., DrSc. (26.02.2019)
Literature -
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.
Last update: IUUK (11.05.2015)
Requirements to the exam -
The exam is oral with time for written preparation. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam.
Last update: Sgall Jiří, prof. RNDr., DrSc. (22.06.2019)
Zkouška je ústní s písemnou přípravou. Požadavky odpovídají sylabu v míře pokryté přednáškami. Zápočet je nutnou podmínkou účasti u zkoušky.
Last update: Sgall Jiří, prof. RNDr., DrSc. (22.06.2019)
Syllabus -
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ů)