PředmětyPředměty(verze: 806)
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.

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