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 -
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: Klazar Martin, doc. RNDr., 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.
Last update: Klazar Martin, doc. RNDr., Dr. (22.09.2020)
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)
Requirements to the exam -
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í
