Přednáška: středa 14:00 v S3.

Stránky cvičících:

• Michal Berg
• Martin Balko
• Jana Syrovátková

1. Pojmy a značení (množiny, sumace). Důkazové techniky (indukcí, sporem).
2. Relace a jejich vlastnosti. Ekvivalence. Částečná uspořádání. Skládání a inverze relací.
3. Funkce. Kombinatorické počítání (počet funkcí, bijekcí, podmnožin), faktoriály a kombinační čísla.
4. Binomická a multinomická věta. Princip inkluze a exkluze.
5. Konečné pravděpodobnostní prostory, terminologie. Podmíněná pravděpodobnost.
6. Nezávislost jevů, střední hodnota.
7. Rozptyl, Markovova a Čebyševova nerovnost, nezávislost veličin. Grafy, základní pojmy, izomorfismus, podgrafy.
8. Sledy a odvozené pojmy. Stupně vrcholů, skóre.
9. Eulerovské tahy. Orientované grafy. Stromy.
10. Rovinné grafy (nakreslení, stěny, duál). Eulerova formule, odhady na počet hran rovinných grafů. Kuratovského věta.
11. Barevnost grafů, zejména rovinných.
12. Pokročilejší tvrzení k částečným uspořádáním (věta o dlouhém a širokém, Erdős-Szekeresovo lemma). Souvislost s Ramseyovou větou.

• J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky.
• Sbírka příkladů.