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.
Poslední úprava: IUUK (04.05.2015)
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.
Cíl předmětu -
Poslední úprava: 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.
Poslední úprava: 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.
Podmínky zakončení předmětu -
Poslední úprava: 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.
Poslední úprava: 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.
Literatura -
Poslední úprava: 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.
Poslední úprava: 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.
Požadavky ke zkoušce -
Poslední úprava: 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ů.
Poslední úprava: 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.
Sylabus -
Poslední úprava: 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í
Poslední úprava: 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
