PředmětyPředměty(verze: 807)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Pravděpodobnostní techniky - NTIN022
Anglický název: Probabilistic Techniques
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017
Semestr: zimní
E-Kredity: 6
Rozsah, examinace: zimní 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://iuuk.mff.cuni.cz/~samal/vyuka/pm/
Garant: doc. Mgr. Robert Šámal, Ph.D.
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
Anotace -
Poslední úprava: (04.05.2015)

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

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

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

Podmínky zakončení předmětu -
Poslední úprava: RNDr. Martin Tancer, Ph.D. (13.10.2017)

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: (04.05.2015)

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

Sylabus -
Poslední úprava: (04.05.2015)

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í

 
Univerzita Karlova | Informační systém UK