Pravděpodobnostní metoda - NTIN022

• Anglický název: Probabilistic Method
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2014 do 2014
• 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: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• 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. - Teoretická informatika; Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika, Teoretická informatika
• Je neslučitelnost pro: NDMI038
• Je záměnnost pro: NDMI038

Anotace

čeština

Poslední úprava: IUUK (04.05.2015)

Pravděpodobnostní metoda je způsob důkazu existence kombinatorických objektů "počítáním". Pro mnoho důležitých objektů je to jediný známý důkaz. Pravděpodobnostní metoda se stále častěji objevuje i v návrhu a analýze algoritmů a v dalších odvětvích informatiky a patří k nejdůležitějším nástrojům diskrétní matematiky.

angličtina

Poslední úprava: IUUK (04.05.2015)

The probabilistic method is one of the most important tools in combinatorics and theoretical computer science; it is a way of proving the existence of combinatorial objects by "counting". For many important objects it is the only known existence proof. The course reviews some elementary probabilistic notions and demonstrates the techniques (the basic probabilistic methods, linearity of expectation, alteration, second moment, Lovasz Local Lemma, and others) on numerous examples.

Cíl předmětu

čeština

Poslední úprava: IUUK (04.05.2015)

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

důkazovou techniku, tzv. pravděpodobnostní metodu.

angličtina

Poslední úprava: IUUK (04.05.2015)

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

probabilistic techniques in discrete mathematics and computer science,

including the probabilistic method.

Literatura

čeština

Poslední úprava: IUUK (04.05.2015)

N. Alon, J. Spencer: The Probabilistic Method, J. Wiley and Sons 1993

J. Spencer: Ten lectures on the probabilistic method, SIAM, 1987

J. Matoušek: Pravděpodobnostní metoda, kapitola ze skript J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky, MATFYZPRESS 1997 (pokrývá jen úvodní část přednášky)

J. Matousek a J. Vondrak: The probabilistic method, skripta, KAM MFF UK, elektronicka verze bude k dispozici na webove strance J. Matouska a papirova v knihovne MFF UK.

angličtina

Poslední úprava: IUUK (04.05.2015)

N. Alon, J. Spencer: The Probabilistic Method, J. Wiley and sons, 1983.

J. Spencer: Ten lectures on the probabilistic method, SIAM, 1987.

J. Matousek and J. Vondrak: The probabilistic method; available electronically from J. Matousek webpage, and in print from the library of MFF UK.

Sylabus

čeština

Poslední úprava: IUUK (04.05.2015)

Základní pravděpodobnostní metoda, linearita střední hodnoty, metoda modifikace, použití variance.

Lovászovo lokální lemma.

Pseudonáhodnost a explicitní konstrukce.

Odhady Černovova typu.

Ilustrace metod na příkladech z různých oblastí diskrétní matematiky a informatiky.

angličtina

Poslední úprava: IUUK (04.05.2015)

Basic probabilistic method. The alteration method. Second moment method. Lovász local lemma. Pseudorandomness and explicit constructions. Chernoff-type estimates. Illustrations of the methods on numerous examples from combinatorics and computer science.