PředmětyPředměty(verze: 945)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
Pravděpodobnostní techniky 2 - NTIN095
Anglický název: Probabilistic Techniques 2
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2023
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: nevyučován
Jazyk výuky: angličtina
Způsob výuky: prezenční
Způsob výuky: prezenční
Další informace: https://iuuk.mff.cuni.cz/~samal/vyuka/2223/PT2/
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
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: IUUK (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: 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.

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.

Požadavky ke zkoušce
Poslední úprava: doc. Mgr. Robert Šámal, Ph.D. (13.07.2019)

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

Sylabus -
Poslední úprava: IUUK (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