PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Pravděpodobnostní techniky II - NTIN095
Anglický název: Probabilistic Techniques II
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018 do 2019
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: nevyuč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.
doc. RNDr. Martin Klazar, Dr.
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.

Podmínky zakončení předmětu -
Poslední úprava: doc. Mgr. Robert Šámal, Ph.D. (14.02.2018)

Pro zápočet je potřeba získat nejméně 45 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 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ů.

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