Probabilistic techniques are a major tool of discrete mathematics,
they are also frequently used in design and analysis of algorithms and
other areas of computer science. The lecture introduces basic
notions, methods, and estimates and illustrates them on examples from
computer science and discrete mathematics.
Last update: IUUK (04.05.2015)
Pravděpodobnostní techniky patří k nejdůležitějším nástrojům diskrétní matematiky, stále častěji se také objevují v
návrhu a analýze algoritmů a v dalších odvětvích informatiky. Přednáška pokrývá základní pojmy, metody a
odhady a ilustruje je na příkladech z informatiky i z diskrétní matematiky.
Last update: IUUK (04.05.2015)
Aim of the course -
Student who takes the class will learn to actively use a modern
probabilistic techniques in discrete mathematics and computer science,
including the probabilistic method.
Last update: IUUK (04.05.2015)
Absolvováním přednášky a cvičení se student naučí aktivně používat
moderní pravděpodobnostní techniky včetně pravděpodobnostní metody.
Last update: IUUK (04.05.2015)
Course completion requirements -
The credit from tutorials is obtained for getting sufficiently many points for solutions of homeworks. There will be five sets of homework problems, it will be possible to get sufficiently many points by solving any three of them. The credit from tutorials is a necessary condition for an attempt to pass an exam.
Last update: Klimošová Tereza, Mgr., Ph.D. (30.08.2026)
Podmínkou získání zápočtu je zisk dostatečného množství bodů z domácích úkolů. Bude vypsáno 5 sérií domácích úkolů, přičemž dostatečné množství bodů bude možno získat vyřešením libovolných tří. Zápočet je nutnou podmínkou pro možnost konat zkoušku.
Last update: Klimošová Tereza, Mgr., Ph.D. (30.08.2026)
Literature -
M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge Univ. Press, 2005.
N. Alon, J. Spencer: The Probabilistic Method, 3rd edition, J. Wiley and Sons, 2008.
J. Matousek, J. Vondrak: The probabilistic method, lecture notes, KAM MFF UK, electronic version will be available on the web-site of the lecture, printed version in the library of MFF UK.
J. Spencer: Ten lectures on the probabilistic method, 2nd edition, SIAM, 1994.
Last update: IUUK (04.05.2015)
M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge Univ. Press, 2005.
N. Alon, J. Spencer: The Probabilistic Method, 3rd edition, J. Wiley and Sons, 2008.
J. Matousek, J. Vondrak: The probabilistic method, skripta, KAM MFF UK, elektronická verze bude k dispozici na webové stránce přednášky a papirová v knihovně MFF UK.
J. Spencer: Ten lectures on the probabilistic method, 2nd edition, SIAM, 1994.
Last update: IUUK (04.05.2015)
Course assessment methods and requirements for successful completion, grading scheme -
The exam will be oral based on the contents of the lectures. Extra points gained by students by solving problems for tutorials will be considered in favor of the students.
Last update: Tancer Martin, prof. RNDr., Ph.D. (05.10.2018)
Zkouška bude ústní na základě obsahu přednášek. Bude též přihlédnuto k případným bodům získaným navíc při řešení domácích úkolů.
Last update: Tancer Martin, prof. RNDr., Ph.D. (05.10.2018)
Syllabus -
Basic notions and methods
events, expected value and its linearity
conditional probability, Bayes' rule
Basic inequalities and estimates
Markov's a Chebyshev's inequality
Chernoff-type estimates
Probabilistic method
basic method and alteration method
Lovász local lemma
Advanced techniques
balls and bins model, basic estimates and applications
Markov chains, stationary distribution
basic continuous distributions as limits of discrete ones, properties and applications
Last update: IUUK (04.05.2015)
Základní pojmy a metody
jevy, střední hodnota a její linearita
podmíněná pravděpodobnost, Bayesovo pravidlo
Základní nerovnosti a odhady
Markovova a Čebyševova nerovnost
odhady Černovova typu
Pravděpodobnostní metoda
základní metoda a metoda modifikace
Lovászovo lokální lemma
Pokročilejší techniky
model "balls and bins", základní odhady a aplikace
Markovovy řetězce, stacionární rozdělení
základní spojitá rozdělení jako limity diskrétních, vlastnosti a příklady použití
