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.
Aim of the course -
Last update: IUUK (04.05.2015)
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.
Course completion requirements -
Last update: doc. RNDr. Martin Klazar, Dr. (22.09.2020)
For getting the credit from tutorials, the students are required to get at least 50 points from homework. The total number of available points will be at least 180. There is no provision for repeated attempts for the credit. Credit from tutorials is a necessary condition for an attempt to pass an exam. Both exam and the tutorial test may be in person or in distant mode.
Last update: doc. RNDr. Martin Klazar, Dr. (22.09.2020)
Pro zápočet je potřeba získat nejméně 50 bodů za domácí úkoly. Celkový počet možných bodů bude nejméně 180. Charakter předmětu neumožňuje opravný termín pro zisk zápočtu. Zápočet je nutnou podmínkou pro možnost konat zkoušku.
Zkouška i závěrečný zápočtový test mohou mít kontaktní nebo distanční formu.
Literature -
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, 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.
Requirements to the exam -
Last update: doc. RNDr. Martin Tancer, Ph.D. (05.10.2018)
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: doc. RNDr. Martin Tancer, 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ů.
Syllabus -
Last update: IUUK (04.05.2015)
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í
