PředmětyPředměty(verze: 804)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Pravděpodobnostní techniky II - NTIN095
Anglický název: Probabilistic Techniques II
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2016
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Další informace: http://kam.mff.cuni.cz/~samal/vyuka/pm2/
Garant: doc. Mgr. Robert Šámal, Ph.D.
Třída: Informatika Mgr. - volitelný
Kategorizace předmětu: Informatika > Diskrétní matematika, Teoretická informatika
Anotace -
Poslední úprava: (28.04.2016)

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.
Cíl předmětu -
Poslední úprava: T_KAM (04.05.2011)

Absolvováním přednášky a cvičení se student naučí aktivně používat

pokročilé partie pravděpodobnostní metody.

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.

Sylabus -
Poslední úprava: (22.04.2016)

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ů).

 
Univerzita Karlova | Informační systém UK