Přednáška z Diskrétní matematiky 2019/20

Přednáším Diskrétní matematiku (NDMI002) každé úterý v 9:00 v učebně S5.

Pokud se mnou chcete cokoliv probrat, jste vítáni v mé pracovně S326 na Malé Straně. Případně napište e-mail na adresu koutecky+dm@iuuk.mff.cuni.cz a/nebo uveďte v předmětu text [DM].

V druhé paralelce přednáší Martin Mareš, přednášku se budeme snažit udržovat synchronní.

datum	co se přednášelo [zdroj]
1. 10.	Motivační příklady: na každé party o 5 lidech se tři znají nebo tři neznají, kdy jde obrázek nakreslit jedním tahem, kolika způsoby skákat po schodech. Co je diskrétka a k čemu je dobrá? Jak se buduje matematika (definice, axiomy, věty, důkazy: přímo, sporem, indukcí). Značení: sumy, produkty, množiny, n-tice, kartézský součin. [K 1.1-1.3]
8. 10.	Relace, jejich znázornění, příklady od doc. Fialy (1, 2, 3), skládání a inverze. Vlastnosti relací: reflexivita, symetrie, tranzitivita, slabá antisymetrie. Ekvivalence a to, že jsou jednoznačně vystiženy svými třídami. [K 1.4-1.5]
15. 10.	Částečná uspořádání (příklad), funkce prosté, na, bijektivní. Úvod do kombinatorického počítání, počet funkcí $f: [n] \to [m]$, počet prostých funkcí, počet podmnožin $[n]$, binomický koeficient $\binom{n}{k}$ a kombinatorické důkazy pár základních vztahů s $\binom{n}{k}$. [K 2.1-2.3]
22. 10.	Binomická věta [Z 4], odhady $n!$ a $\binom{n}{k}$ [K 2.4-2.5], princip inkluze a exkluze [K 2.6]
29. 10.	Imatrikulace – můžete si přečíst možná překvapivou stránku o slavné písni Gaudeamus Igitur
5. 11.	Problém šatnářky [K 2.7], [Z 4, Př 5], příklad pro $n=4$. Úvod do teorie grafů – definice: graf, úplný graf (klika), prázdný graf, cesta, kružnice, podgraf, indukovaný podgraf, doplněk grafu, sled v grafu, tah, cesta, cyklus, relace dosažitelnosti $u \sim v$ (z $u$ existuje cesta do $v$), isomorfismus, stupeň. Důkazy: odhad na počet neisomorfních grafů, dosažitelnost $u \sim v$ je ekvivalence, princip sudosti. [K 3.1-3.2], [Z 7b], [Z 8]
12. 11.	Děkanský den
19. 11.	Souvislost a komponenty souvislosti. Vzdálenosti v grafu (metrika). Operace s grafy: přidání a odebrání vrcholu/hrany. Stromy: definice, lemma o koncovém vrcholu, princip stromové indukce, věta o charakterizaci stromů. [K 3.2, 3.4, trochu 3.8, 4.1, 4.3], [Z 8, Z 9 (bez Eulerovských tahů)].
26. 11.	Kostra grafu: definice, existence, význam. Kreslení grafů jedním tahem: věta o existenci uzavřeného eulerovského tahu. Orientované grafy: silná a slabá souvislost, eulerovské tahy. Kreslení grafů do roviny. Trocha topologie roviny (oblouky, topologické kružnice), definice rovinného nakreslení. Stěny nakreslení. Jordanova věta o kružnici (bez důkazu). Z 9 (bez stromů), Z 10].
3. 12.	$K_5$ není rovinný. Kreslení na sféru, stereografická projekce a možnost zvolit si vnější stěnu. Dualita rovinných (multi)grafů. Eulerova formule, horní odhad na počet hran rovinného grafu, existence vrcholu nízkého stupně. Z 10.
11. 12.	Podrozdělení hrany a Kuratovského věta (znění bez důkazu). Barvení map a Problém 4 barev, převod barvení mapy na barvení rovinných grafů. $d$-degenerované grafy jsou $d+1$-obarvitelné. Věta o 5 barvách. Z 11.
18. 12.	Úvod do pravděpodobnosti, diskrétní pravděpodobnostní prostor, věta o úplné pravděpodobnosti, podmíněná pravděpodobnost. Náčrt: náhodná veličina, střední hodnota, linearita střední hodnoty, indikátor (vrátíme se k nim). P.
7. 1.	Náhodná veličina, střední hodnota a její linearita, indikátor, rozptyl, Markovova a Čebyševova nerovnost. P, slajdy doc. Fialy: 6, 7, 8, 9, 10, 11, 12.

Okruhy zkoušky.

Užitečné zdroje

Sbírka úloh z DM
Návod ke Studnici vědomostí, která obsahuje mnohé jinak těžko sehnatelné materiály, mrk, mrk.
Matoušek, Nešetřil: Kapitoly z diskrétní matematiky, Karolinum. Existuje několik různých vydání, která se liší číslováním kapitol; odkazy výše jsou podle staršího (černého). Také pozor na drobné chyby ve starších vydáních (viz errata). [K]
Matoušek: Podrobný sylabus o pravděpodobnosti [P] (PDF)
Mareš, Valla: Průvodce labyrintem algoritmů [L]
Poznámky Zdeňka Dvořáka [Z]
Slajdy doc. Fialy, většinou obsahují konkrétní příklady, dobré pro získání intuice.
Poznámky Toma Slámy z přednášek Martina Mareše