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.
Poslední úprava: IUUK (11.05.2015)
Cíl předmětu -
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.
Poslední úprava: IUUK (11.05.2015)
Podmínky zakončení předmětu -
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.
Poslední úprava: Sgall Jiří, prof. RNDr., DrSc. (26.02.2019)
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.
Poslední úprava: Sgall Jiří, prof. RNDr., DrSc. (22.06.2019)
Literatura -
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.
Poslední úprava: IUUK (11.05.2015)
Požadavky ke zkoušce -
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.
Poslední úprava: Sgall Jiří, prof. RNDr., DrSc. (22.06.2019)
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.
Poslední úprava: Sgall Jiří, prof. RNDr., DrSc. (22.06.2019)
Sylabus -
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)
