Přednáška z Diskrétní matematiky 2023/24

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

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].

datum	co se přednášelo [zdroj]
3. 10.	Motivační příklady: na každé party o 6 lidech se tři znají nebo tři neznají, kdy jde obrázek nakreslit jedním tahem. 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], [Z 1]
10. 10.	Relace, jejich znázornění, skládání a inverze. Vlastnosti relací: reflexivita, symetrie, tranzitivita, slabá antisymetrie. Ekvivalence. [K 1.4-1.5], [Z 2]
17. 10.	Dodělávka: ekvivalence jsou jednoznačně určeny svými třídami. Částečná uspořádání, funkce prosté, na, bijektivní. [Z 2], [Z 3]
24. 10.	Věta o dlouhém a širokém (zde). Ú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], Kombinatorika do kapsy od M. Mareše, [Z 3].
31. 10.	Binomická věta [Z 4], jednoduchý odhad $\binom{n}{\lfloor n/2\rfloor}$ [K 2.4-2.5], princip inkluze a exkluze [K 2.6] Problém šatnářky [K 2.7], [Z 4, Př 5]
7. 11.	Ú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ň. Souvislost a komponenty souvislosti. Vzdálenosti v grafu (metrika). Důkazy: dosažitelnost $u \sim v$ je ekvivalence, princip sudosti. [K 3.1-3.2], [Z 7b], [Z 8]
14. 11.	Uzavřené a otevřené eulerovské tahy (jednotažky), Stromy (definice: minimální souvislé grafy; alternativa: souvislé bez kružnice; mají vždy $n-1$ hran [K 3.2, 3.4, trochu 3.8, 4.1, 4.3], Z 9
21. 11.	Den otevřených dveří
28. 11.	Dokončení stromů (charakterizace) Z 9; Věta o skóre (na zkoušce budu chtít znění, ale ne důkaz). [K 3.4]
5. 12.	Kreslení grafů do roviny – nejprve intuitivně. Co je to rovinné nakreslení a jeho stěny, stereografická projekce, Eulerova formule (vzorec), rovinné grafy mají $O(n)$ hran, průměrný stupeň v rovinných grafech je $<6$ ($<4$ pro grafy bez $K_3$), tedy vždy existuje vrchol stupně $\geq 5$ (resp. $\geq 3$). Náčrt definice duálu $G$. Z 10
12. 12.	Dualita rovinných (multi)grafů, podrozdělení hrany a Kuratovského věta (znění bez důkazu). Rovinnost trochu formálněji Z 10. Barvení grafů, $d$-degenerované grafy jsou $d+1$-obarvitelné. Věta o 4 barvách (bez důkazu). Z 11
19. 12.	jak souvisí barvení rovinných grafů a politických map, věta o 5 barvách. Z 11. Základy pravděpodobnosti: diskrétní pravděpodobnostní prostor, věta o úplné pravděpodobnosti, podmíněná pravděpodobnost. P
9. 1.	Nezávislost jevů. Náhodná veličina, střední hodnota a její linearita, indikátor, rozptyl, Markovova a Čebyševova nerovnost. P

Okruhy zkoušky

Ukázka zkouškového zadání.

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