The aim: randomized algorithms and methods are becoming one of the key
tools for an effective solution of a variety of problems in
informatics
and its aplications practically in all theoretical and aplication
areas.
After finishing the lecture student will be able:
To manage basic techniques to design randomized algorithms;
to understand differences concerning power of deterministic and randomized algorithms;
to manage basic tools for analysis of randomized algorithms;
to work with tail inequalities;
to understand power and use of the probabilistic method;
to understand power of random walks;
to understand power of randomized proofs;
to understand basic principles of randomized cryptographic protocols.
Osnova
Náhodnostní algoritmy a metody.
Příklady náhodnostních algoritmů.
Základní typy náhodnostních algoritmů.
Náhodnostní třídy složitosti.
Metody teorie her.
Chernoffovy odhady.
Momenty a deviace.
Pravděpodobnostní metody.
Markovovy řetězce a náhodné cesty.
Algebraické metody.
Aplikace
Lineární programování.
Paralelní a distribuované algoritmy.
Náhodnostní metody v kryptografii.
Náhodnostní metody v teorii čísel.
Literatura
GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997. xv, 716 s. ISBN 1-85032-243-0. info
MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995. xiv, 476. ISBN 0521474655. info