Cviceni budou po prednasce (od 12:20 v S6) zhruba kazdy druhy tyden.
Rozsah vyuky: ZS 2/2 Z, Zk
Prednaska se vzajemne doplnuje s prednaskou L. Kucery nebo J. Sgalla "Pravdepodobnostni algoritmy".
2.přednáška 12.10.2005 Doporučená literatura. Užitečné odhady faktoriálů a kombinačních čísel. Zkoumání funkce m(k), což jest nejmenší počet hran k-grafu, který není řádně 2-obarvitelný: m(2)=3, m(3)=7, m(k) > 2k-1. Definice náhodné veličiny, střední hodnoty a jejich vlastnosti. Aplikace: existuje turnaj, který obsahuje alespoň 2n-1/n! hamiltonovských cest.
3.přednáška 19.10.2005 Aplikace střední hodnoty: střední hodnota počtu pevných bodů náhodné permutace, každý graf obsahuje bip. podgraf s alespoň polovinou hran (plus zmínka o "derandomizaci"---jak to udělat nenáhodně), balancování vektorů (sčítání plus/minus násobků daných vektorů, aby součet byl co nejmenší/největsí). Erdös-Ko-Radonova věta.
4.přednáška 26.10.2005 Další dvě aplikace volby náhodné permutace: Bollobásova věta a Spernerova věta. Metoda alterace (nápravy) a její aplikace: vylepšení odhadu Ramseyových čísel, slabá forma Turánovy věty a množina bodů bez malých trojúhelníků.
5.prednaska 1.11.2005 [JM] Erdosuv dukaz existence vysoce barevnych grafu bez kratkych cyklu. Rozptyl, kovariance, Cebysevova nerovnost. Dolni odhad prostredniho binomickeho koeficientu.
6.prednaska 8.11.2005 [RS] Dodělávka z 4. přednášky: pravděpodobnost, že tři náhodně zvolené body tvoří trojúhelník s malým obsahem. Množiny s různými součty: odhady na jejich velikost využitím Čebyševovy nerovnosti a také `metody popotahování' (bootstrapping).
7.prednaska 15.11.2005 Aplikace Čebyševovy nerovnosti: prahová funkce pro vlastnost obsahovat trojúhelník.
8.prednaska 22.11.2005 Aplikace Čebyševovy nerovnosti: prahová funkce pro vlastnost obsahovat daný vyvážený graf. Začátek zkoumání "klikovosti" náhodného grafu a návnada na Lovászovo lokální lemma.
9.prednaska 29.11.2005 "Klikovost" náhodného grafu s n vrcholy je skoro jistě menší než 2 log2n a větší než (2-epsilon)log2n (důkaz pomocí Čebyševovy nerovnosti a dlouhého výpočtu). Lovászovo lokální lemma: symetrická i obecná verze, pozorování o nezávislosti na množině jevů, aplikace na barvení hypergrafů.
10.prednaska 7.12.2005 [JM] Priklad: pravdepodobnost, ze konvexni obal n nahodnych bodu na jednotkove kruznici bude obsahovat stred kruznice. Aplikace LLL: existence cyklu delky delitelne k v orientovanych grafech; legracni prosta zobrazeni; barveni R (konecna cast). Strucny uvod do euklidovske Ramseyovy teorie.
11.prednaska 14.12.2005 [JM] Definice topologickeho prostoru, kompaktnost (pouze orientacne), vyuziti pri dukazu existence vhodneho barveni R. Silna koncentrace kolem stredni hodnoty: uvod; Cernovova nerovnost - zakladni verze s dukazem.
12. a 13. prednaska 21.12.2005 [JM] Pojem diskrepance mnozinoveho systemu. Horni odhad diskrepance m mnozin na n bodech pomoci Cernovovy nerovnosti. Obecnejsi verze Cernovovy nerovnosti; intuice pomoci centralni limitni vety. Technika pravdepodobnostniho zaokrouhlovani na prikladu maximalniho k-pakovani. Dolni odhad (Cernovova nerovnost je temer optimalni) - bez dukazu. Dolni odhad pro diskrepanci m mnozin na n bodech. Jiny dolni odhad diskrepance pres Hadamardovy matice.
14. prednaska 11.1.2006 [JM] Pojem soucinoveho pravdepodobnostniho prostoru, funkce f na nem, vliv i-te promenne na ni, veta o koncentraci funkci. Priklady: pocet zivych zajicu, barevnost nahodneho grafu (tam se "prirozeny" soucinovy prostor musi chytre "uzavorkovat"). Veta o ctyrhodnotove koncentraci barevnosti pro dostatecne male p.