Pravděpodobnostní techniky - NTIX022

• Anglický název: Probabilistic Techniques
• Zajišťuje: Studijní oddělení (32-STUD)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: zimní
• E-Kredity: 6
• Rozsah, examinace: zimní 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: vyučován
• Jazyk výuky: angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Je zajišťováno předmětem: NTIN022
• Další informace: http://iuuk.mff.cuni.cz/~samal/vyuka/pm/
• Garant: doc. Mgr. Robert Šámal, Ph.D.; doc. RNDr. Martin Tancer, Ph.D.
• Třída: Informatika Mgr. - Diskrétní modely a algoritmy; M Mgr. MSTR; M Mgr. MSTR > Povinně volitelné
• Kategorizace předmětu: Informatika > Diskrétní matematika, Teoretická informatika
• Prerekvizity : {NXXX007, NXXX008, NXXX009, NXXX036, NXXX037, NXXX051, NXXX052, NXXX053}
• Neslučitelnost : NTIN022
• Záměnnost : NTIN022

Anotace

čeština

Pravděpodobnostní techniky patří k nejdůležitějším nástrojům diskrétní matematiky, stále častěji se také objevují v návrhu a analýze algoritmů a v dalších odvětvích informatiky. Přednáška pokrývá základní pojmy, metody a odhady a ilustruje je na příkladech z informatiky i z diskrétní matematiky.

Poslední úprava: IUUK (04.05.2015)

angličtina

Probabilistic techniques are a major tool of discrete mathematics, they are also frequently used in design and analysis of algorithms and other areas of computer science. The lecture introduces basic notions, methods, and estimates and illustrates them on examples from computer science and discrete mathematics.

Poslední úprava: IUUK (04.05.2015)

Cíl předmětu

čeština

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

moderní pravděpodobnostní techniky včetně pravděpodobnostní metody.

Poslední úprava: IUUK (04.05.2015)

angličtina

Student who takes the class will learn to actively use a modern

probabilistic techniques in discrete mathematics and computer science,

including the probabilistic method.

Poslední úprava: IUUK (04.05.2015)

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

čeština

Pro zápočet je potřeba získat nejméně 50 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 i závěrečný zápočtový test mohou mít kontaktní nebo distanční formu.

Poslední úprava: Klazar Martin, doc. RNDr., Dr. (22.09.2020)

angličtina

For getting the credit from tutorials, the students are required to get at least 50 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. Both exam and the tutorial test may be in person or in distant mode.

Poslední úprava: Klazar Martin, doc. RNDr., Dr. (22.09.2020)

Literatura

čeština

• M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge Univ. Press, 2005.

• N. Alon, J. Spencer: The Probabilistic Method, 3rd edition, J. Wiley and Sons, 2008.

• J. Matousek, J. Vondrak: The probabilistic method, skripta, KAM MFF UK, elektronická verze bude k dispozici na webové stránce přednášky a papirová v knihovně MFF UK.

• J. Spencer: Ten lectures on the probabilistic method, 2nd edition, SIAM, 1994.

Poslední úprava: IUUK (04.05.2015)

angličtina

• M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge Univ. Press, 2005.

• N. Alon, J. Spencer: The Probabilistic Method, 3rd edition, J. Wiley and Sons, 2008.

• J. Matousek, J. Vondrak: The probabilistic method, lecture notes, KAM MFF UK, electronic version will be available on the web-site of the lecture, printed version in the library of MFF UK.

• J. Spencer: Ten lectures on the probabilistic method, 2nd edition, SIAM, 1994.

Poslední úprava: IUUK (04.05.2015)

Požadavky ke zkoušce

čeština

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: Tancer Martin, doc. RNDr., Ph.D. (05.10.2018)

angličtina

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: Tancer Martin, doc. RNDr., Ph.D. (05.10.2018)

Sylabus

čeština

Základní pojmy a metody

• jevy, střední hodnota a její linearita

• podmíněná pravděpodobnost, Bayesovo pravidlo

Základní nerovnosti a odhady

• Markovova a Čebyševova nerovnost

• odhady Černovova typu

Pravděpodobnostní metoda

• základní metoda a metoda modifikace

• Lovászovo lokální lemma

Pokročilejší techniky

• model "balls and bins", základní odhady a aplikace

• Markovovy řetězce, stacionární rozdělení

• základní spojitá rozdělení jako limity diskrétních, vlastnosti a příklady použití

Poslední úprava: IUUK (04.05.2015)

angličtina

Basic notions and methods

• events, expected value and its linearity

• conditional probability, Bayes' rule

Basic inequalities and estimates

• Markov's a Chebyshev's inequality

• Chernoff-type estimates

Probabilistic method

• basic method and alteration method

• Lovász local lemma

Advanced techniques

• balls and bins model, basic estimates and applications

• Markov chains, stationary distribution

• basic continuous distributions as limits of discrete ones, properties and applications

Poslední úprava: IUUK (04.05.2015)