Pravdepodobnostné metódy

Robert Lukoťka, Ján Mazák, M255, mazak / lukotka at dcs.fmph.uniba.sk

Informačný list: 2-INF-133_00

Hodnotenie: pozri informačný list.

Materiály

• Prerekvizita: [pdf] (skriptá z pravdepodobnosti)
• Poznámky: [pdf]
• Kniha: [web] / [pdf]

1. prednáška:

• revízia pravdepodobnosti a náhodných premenných (prerekvizita, kap. 1 z Poznámok)
• Markovova nerovnosť (časť kap. 2 z Poznámok)

2. prednáška:

• Čebyševova nerovnosť (kap. 2 z Poznámok)

3. prednáška:

• Nerovnosti, birthday paradox (kap. 3, 4 z Poznámok)

4. prednáška:

• Concentration bounds, median trick (kap. 5, 6 z Poznámok)

5. prednáška:

• Random walk, triangles in random graphs (kap. 7, 8 z Poznámok)

6. prednáška:

• Isolated vertices in random graphs, Poisson approximation (kap. 9, 10 z Poznámok)

7. prednáška:

• Perfect matchings in bipartite graphs (kap. 11 z Poznámok)

8. prednáška:

• Models G(n, m) vs. G(n, p), thresholds for monotone properties (kap. 1 z Knihy)

9. prednáška:

• Evolution: subcritical phase (kap. 2.1 z Knihy)

10. prednáška:

• Evolution: supercritical phase, phase transition (kap. 2.2, 2.3 z Knihy); overview of results (kap. 3, 4, 5.1, 6.1, 6.2 z Knihy)

11. prednáška:

• Homework review: connectivity (Thm 4.1 z Knihy), Chromatic number and girth (kap. 12 z Poznámok), brief overview of basic results on other invariants and other models of random graphs (Thm 7.1, 7.2, 7.3, 7.7, kap. 9.1, 13.1, 13.2 z Knihy)