Jiří Sgall, Robert Šámal

Přednáška Pravděpodobnostní techniky (NTIN022) 2016/17


Přednáška: Pá 12:20 v S5, cvičení: Pá 14:00 v S6 (většina práce formou domácích úkolů). Informace o cvičeních: web cvičícího -- Tomáš Toufar.

Seznam probrané látky najdete na konci teto stranky (průběžně doplňováno).


Rozsah výuky: ZS 2/2 Z, Zk

Anotace

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 algoritmu a v dalších odvětvích informatiky a patří k nejdůležitějším nástrojům diskrétní matematiky.
O náplní přednášky si můžete udělat představu podle látky probrané minule. Letos se přednáška bude (patrně) přednášet česky.

Organizační poznámky

Cvičení probíhá hlavně formou individuální práce posluchačů (domácí úkoly, třeba řešit průběžně během semestru).

Učební text

Skripta J. Matoušek, J. Vondrák: The probabilistic method vyšla v ITI Sériích (preprintova řada Institutu teoretické informatiky MFF UK) pod číslem 2002-087 a je k dispozici v informatické knihovně MFF UK.

Sylabus


Basic notions and methods: events, expected value and its linearity, conditional probability, Bayes' rule.
Basic inequalities and estimates: Markov's a Chebyshev's inequality, Chernoff-type estimates.
Probabilistic method: basic method and alteration method, Lovász local lemma.
Advanced techniques: balls and bins model, basic estimates and applications, Markov chains, stationary distribution, basic continuous distributions as limits of discrete ones, properties and applications. Illustration of the methods on examples from various areas of discrete mathematics and theoretical computer science.

References

Probraná témata

6.10.2016
Jak dokázat existenci grafu házením korunou: dolní odhad na Ramseyova čísla, $R(k) > 2^{k/2}$, kde $R(k,k)$ je Ramseyovo číslo, minimální počet vrcholů grafu, který zaručeně má nezávislou množinu nebo kliku s $k$ vrcholy. Připomenutí a přehled základních pojmů z pravděpodobnosti: pravděpodobnostní prostor, union bound -- subaditivita pravděpodobnosti, nezávislé jevy. Odhady pro faktoriál, kombinační čísla, $1+x \le e^x$.
13.10.2016
Další aplikace základní metody: formule v CNF, kde každá klauzule má $k$ literálů a počet klauzulí je menší než $2^k$ je splnitelná. Pokračování úvodního přehledu praděpodobnosti: náhodné veličiny, linearita střední hodnoty, distribuce, nezávislé veličiny. Přehled distribucí (diskrétních i spojitých). Využití linearity střední hodnoty: Počet pevných bodů náhodné permutace. Existuje turnaj s mnoha hamiltonovskými cestami.
20.10.2016
MAX-SAT -- jak splnit mnoho klauzulí ve formuli. Každý graf má řez obsahující alespoň polovinu hran. (a metoda na derandomizaci -- nalezení řezu efektivním algoritmem) Plus-mínusové součty vektorů mohou být malé i velké.
Metoda změny Slabá Turánova věta: $\alpha(G) \geq n/2d$, kde $\alpha$ je max. velikost nezávislé množiny v grafu s $n$ vrcholy a průměrným stupněm $d$.
Markovova nerovnost Existence grafů s libovolně velkým obvodem a barevností.
4.11.2016
Bayesovo pravidlo. Aplikace na testování násobení matic.
Konstrukce množiny bodů ve čtverci bez malých trojúhelníků. (Metoda změny.)
Rozptyl, standardní odchylka, kovariance. Výpočet rozptylu pro součet náhodných veličin.
11.11.2016 -- přednáška se nekonala
18.11.2016 -- přednáška se nekonala
25.11.2016
Čebyševova nerovnost (s důkazem). Náhodné grafy, zavedení prahové funkce. Prahová funkce pro "obsahovat $K_4$" je $n^{2/3}$. Prahová funkce pro "obsahovat libovolný podgraf" (pomocí hustoty podgrafu, pro balancované grafy).
2.12.2016 -- přednáška dvakrát
Čebyševova nerovnost -- další aplikace: odhad prostředního binomického čísla, množiny s různými součty Lovászovo lokální lemma -- znění, aplikace (splnitelnost řídkých formulí, existence hr.disjunktních cest, cvičení s prostými zobrazeními). Černovova/Chernoffova nerovnost -- znění (zatím jen "symetrická"), aplikace (max. stupeň v $G(n,1/2)$, diskrepance). Důkaz lokálního lemmatu a znění v obecné verzi.
9.12.2016
Důkaz Černovovy nerovnosti. Dalších mnoho verzí (některé s důkazem). Aplikace na zaokrouhlování lineárního programu ($k$-párování v hypergrafu).
16.12.2016
Balls and bins. Dolní odhad přímým výpočtem. Poissonovo rozdělení, Poissonovská aproximace. Horní odhad přes Poissonovskou aproximaci. Síla dvou výběrů, znění odhadů s naznačením důkazu. [MU 5.1-5.4, 14.1]
6.1.2017
Markovovy řetězce. Definice časově homogenních diskrétních řetězců. Aplikace: Algoritmy pro 2-SAT a 3-SAT. [MU 7.1-7.2]
13.1.2017
Markovovy řetězce. Klasifikace stavů: transientní, pozitivně rekurentní, nulově rekurentní. Klasifikace řetězců: ireducibilni, (a)periodické, ergodické. Stacionární distribuce, její existence a jednoznačnost pro konečné ergodické řetězce. Poznámky ke stacionárním distrubucím. Spojité Markovovy řetězce, exponenciální rozdělení a jejich vztah. [MU 7.3, 8.3, 8.5]