Sylabus
Martingaly, Azumova nerovnost.
Talagrandova nerovnost.
Poissonovo paradigma -- Jansonova nerovnost a Brunovo síto.
Kvazináhodnost.
Náhodné grafy.
Vícefázové náhodné procesy (iterativní barvení řídkých grafů).
Anotace
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í techniky 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.