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í
• 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

Anotace

čeština

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.

Poslední úprava: IUUK (28.04.2016)

angličtina

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

Poslední úprava: IUUK (28.04.2016)

Cíl předmětu

čeština

Absolvováním přednášky a cvičení se student naučí aktivně používat pokročilé partie pravděpodobnostní metody.

Poslední úprava: Šámal Robert, doc. Mgr., Ph.D. (25.01.2023)

angličtina

The students will learn to actively use advanced techniques in Probabilistic method.

Poslední úprava: Šámal Robert, doc. Mgr., Ph.D. (25.01.2023)

Podmínky zakončení předmětu

čeština

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

Poslední úprava: Šámal Robert, doc. Mgr., Ph.D. (14.02.2018)

angličtina

For getting the credit from tutorials, the students are required to get at least 45 points from homework. The total number of available points will be at least 180. There is no provision for repeated attempts for the credit. Credit from tutorials is a necessary condition for an attempt to pass an exam.

The exam will be oral based on the contents of the lectures. Extra points gained by students by solving problems for tutorials will be considered in favor of the students.

Poslední úprava: Šámal Robert, doc. Mgr., Ph.D. (14.02.2018)

Literatura

čeština

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)

Požadavky ke zkoušce

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

Poslední úprava: Šámal Robert, doc. Mgr., Ph.D. (13.07.2019)

Sylabus

čeština

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

Poslední úprava: IUUK (22.04.2016)

angličtina

Martingales, Azuma inequality.

Talagrand inequality.

Poisson paradigm -- Janson inequality and Brun sieve.

Quasirandomness.

Random graphs.

Multi-phase random processes (iterative coloring of sparse graphs).

Poslední úprava: IUUK (22.04.2016)