Pravděpodobnostní techniky

Sylabus

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í

Anotace

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.