Diskrétní matematika
V zimním semestru 2025/2026 učím Diskrétní matematiku pro studenty matematiky [NMIN105]. Přednáška se koná v úterky od 14:00 v N1.
Kdybyste čemukoliv nerozuměli, rád si s vámi domluvím konzultaci. Ozvěte se mi prosím na adresu mares+dm@kam.mff.cuni.cz.
Můžete sledovat přímý přenos z přednášek.
| datum | co se přednášelo [zdroj] | záznam |
|---|---|---|
| 30. 9. | Co je diskrétní matematika. Pár příkladů pro začátek: šest lidí v tramvaji, prvočísel je nekonečně mnoho, jak se sčítá (konečná) aritmetická a geometrická řada, jedničková čísla a jejich dělitelnost. Důkazové techniky: rozbor případů, obměna, spor, indukce, princip holubníku. | video poznámky |
| 7. 10. | Kombinatorické počítání: řetězce nad danou abecedou, řetězce bez opakování, permutace, popis pomocí funkcí, charakteristické posloupnosti podmnožin, sudé a liché podmnožiny, k-prvkové podmnožiny. Kombinační čísla a jejich vlastnosti. Pascalův trojúhelník a Binomická věta. [K 3.3, T] | video poznámky |
| 14. 10. | Přednáška pro nemoc odpadá. Podívejte se prosím na záznam z loňska. Diskrétní pravděpodobnost: diskrétní pravděpodobnostní prostor a jevy, nezávislost jevů. Zmínka o součinových prostorech. | video poznámky xkcd |
| 21. 10. | Přednáška odpadá: Imatrikulace. Gaudeamus igitur! | |
| 28. 10. | Přednáška odpadá: vyberte si svůj svátek :) | |
| 4. 11. | Diskrétní pravděpodobnost: podmíněná pravděpodobnost, věta o rozboru případů, Bayesova věta. Problém šatnářky [K 3.7]. Princip inkluze a exkluze [K 3.7]. | video poznámky |
| 11. 11. | Důkaz Principu inkluze a exkluze. Úvod do grafů: Příklad s mosty města Královce. Definice grafu, cesta/tah/sled, souvislost, stupeň vrcholu, věta o existenci uzavřeného eulerovského tahu [K 4.5]. Co se změní v orientovaných grafech: vstupní/výstupní stupeň, vyvážené grafy, silná a slabá souvislost, podkladový graf, existence uzavřeného eulerovského tahu [K 4.6]. | video poznámky |
| 13. 11. | Plán: Úvod do grafů: definice a základní značení, zoo grafů, bipartitnost [K 4.1], stupeň a princip sudosti [K 4.4], podgrafy a indukované podgrafy, cesty a kružnice v grafech [K 4.2] Extremální úloha: grafy bez trojúhelníků [K 4.8]. | poznámky |
Zdroje
- Všechny poznámky dohromady
- Loňská přednáška s videozáznamy.
- Přednáška pro informatiky z roku 2022 s videozáznamy.
- 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 nejnovějšího (světle modrého). Také pozor na drobné chyby ve starších vydáních (viz errata). [K]
- Mareš: Kombinatorický tahák [T]
- Mareš: Ramseyovy věty [R]
- Mareš, Valla: Průvodce labyrintem algoritmů
- Sbírka úloh
- Stránky mého dávného cvičení coby další zdroj příkladů.
- Graham, Knuth, Patashnik: Concrete Mathematics (pokud máte chuť na něco pokročilejšího, toto je krásně napsaná knížka o věcech na pomezí diskrétní a spojité matematiky)
- Lovász: Combinatorial Exercises (sbírka úloh, obvykle dosti šťavnatých)