Přednáším Diskrétní matematiku (NDMI002) každý čtvrtek v 14:00 v učebně S3.
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], [Z 2], záznam (bohužel bez tabule, snad příště) |
| 14. 10. | Částečná uspořádání (příklad), funkce prosté, na, bijektivní. [Z 2], [Z 3] záznam |
| 21. 10. | Ú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áznam |
| 28. 10. | Odpadá – státní svátek |
| 4. 11. | Binomická věta [Z 4], odhady $n!$ a $\binom{n}{k}$ [K 2.4-2.5], princip inkluze a exkluze [K 2.6] Problém šatnářky [K 2.7], [Z 4, Př 5], příklad pro $n=4$. záznam, bohužel jen čtvrtina obrazovky, příště snad už bude vše OK… |
| 11. 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], záznam |
| 18. 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 8 záznam |
| 25. 11. | Dokončení stromů (charakterizace); něco o počítání sledů délky $k$ a grafové metrice. Věta o skóre. záznam |
| 2. 12. | Kreslení grafů do roviny. Trocha topologie roviny (oblouky, topologické kružnice), definice rovinného nakreslení. Stěny nakreslení. Z 10, záznam. |
| 9. 12. | Jordanova věta o kružnici (bez důkazu). Dualita rovinných (multi)grafů, Eulerova formula, horní odhad na počet hran rovinného grafu. Z 10 záznam |
| 16. 12. | Existence vrcholu nízkého stupně. 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. Základy pravděpodobnosti: diskrétní pravděpodobnostní prostor, věta o úplné pravděpodobnosti, podmíněná pravděpodobnost. P záznam |
| 6. 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. záznam |