Podstatou pravděpodobnostní metody je důkaz existence objektů počítáním:
ve vhodném pravděpodobnostním prostoru se ukáže, že s nenulovou pravděpodobností
dostaneme kýžený objekt.
Přednáška navazuje na Pravděpodobnostní metodu NTIN022 kde byly probrány základní
techniky. (Ty je nezbytně nutné znát ať již z této přednášky nebo odjinud.)
V této přednášce se zaměříme na jejich prohloubení a rozšíření.
Přednáška se doplňuje, ale nepřekrývá s přednáškou Pravděpodobnostní algoritmy NDMI025.
Poslední úprava: IUUK (28.04.2016)
Probabilistic method is a way to prove existence of objects by counting:
in a suitable probability space one shows that with nonzero probability
we get the desired object.
This class is a continuation of Probabilistic method NTIN022 where the
basic techniques were described. (The knowledge of those is necessary
to follow this class.) In this class we will extend and deepen these techniques.
The class is complementing (but not overlapping) with Probabilistic algorithms NDMI025.
Cíl předmětu -
Poslední úprava: doc. Mgr. Robert Šámal, Ph.D. (25.01.2023)
Absolvováním přednášky a cvičení se student naučí aktivně používat
pokročilé partie pravděpodobnostní metody.
Poslední úprava: doc. Mgr. Robert Šámal, Ph.D. (25.01.2023)
The students will learn to actively use advanced techniques
in Probabilistic method.
Literatura -
Poslední úprava: T_KAM (04.05.2011)
N. Alon, J.H. Spencer: Probabilistic Method, Wiley, 2000.
M. Molloy, B. Reed: Graph Colouring and the Probabilistic Method, Springer, 2002.
S. Janson, T. Luczak, A. Rucinski: Random Graphs, Wiley-Interscience, 2000.
Poslední úprava: T_KAM (04.05.2011)
N. Alon, J.H. Spencer: Probabilistic Method, Wiley, 2000.
M. Molloy, B. Reed: Graph Colouring and the Probabilistic Method, Springer, 2002.
S. Janson, T. Luczak, A. Rucinski: Random Graphs, Wiley-Interscience, 2000.
Sylabus -
Poslední úprava: IUUK (22.04.2016)
Martingaly, Azumova nerovnost.
Talagrandova nerovnost.
Poissonovo paradigma -- Jansonova nerovnost a Brunovo síto.
