Diskrétní matematika
V zimním semestru 2024/2025 učím Diskrétní matematiku pro studenty matematiky [NMIN105]. Přednáška se koná ve středy od 10:40 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 |
---|---|---|
2. 10. | 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 |
9. 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 |
16. 10. | 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 |
23. 10. | Přednáška odpadá: Imatrikulace. Gaudeamus igitur! | |
30. 10. | 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 |
6. 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, existence uzavřeného eulerovského tahu [K 4.6]. | video poznámky |
13. 11. | Ú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]. | video poznámky |
20. 11. | Stromy: motivace kostrou grafu [K 5.3], definice, lemma o koncovém vrcholu, lemma o odebírání listů, stromy jsou souvislé grafy s n vrcholy a n-1 hranami, věta o charakterizaci stromů [K 5.1]. Relace a způsoby jejich znázorňování (maticí, různými grafy), inverzní relace [K 1.4]. | video poznámky |
27. 11. | Zobrazení neboli funkce a jejich vlastnosti. Skládání relací a funkcí a mírný zmatek v jejich značení. Vlastnosti relací: reflexivita, symetrie, antisymetrie, tranzitivita. Ekvivalence: definice, popis pomocí rozkladu na ekvivalenční třídy [K 1.4–1.5]. Komponenty souvislosti grafu jsou ekvivalenční třídy [K 4.2]. Uspořádání: definice, příklady (dělitelnost, inkluze, lexikografické uspořádání) [K 2.1–2.2]. | video poznámky |
4. 12. | Uspořádání: bezprostřední předchůdce, Hasseovy diagramy, nejmenší/minimální a největší/maximální prvky, opačné uspořádání, řetězce/antiřetězce, suprema/infima. Existence minimálního prvku v konečné uspořádané množině, existence lineárního rozšíření (topologické uspořádání grafu) [K 2.2]. Isomorfismus grafů, uspořádaných množin a obecně relačních struktur [K 4.1]. Věta o vnořování do inkluze [K 2.3]. | video poznámky |
11. 12. | Plán: Rovinné grafy: Neformální definice nakreslení a jeho stěn. Cesty a kružnice jsou rovinné, stromy taktéž. Jordanova věta o kružnici (bez důkazu). K5 není rovinný. Hranice stěny je nakreslením uzavřeného sledu (bez důkazu). Kreslení na sféru, stereografická projekce a možnost zvolit si vnější stěnu. Zmínka o kreslení na další plochy. Eulerova formule, maximální rovinné grafy jsou triangulace, horní odhad počtu hran rovinného grafu, existence vrcholu nízkého stupně; analogické věty pro grafy bez trojúhelníků. K3,3 není rovinný. Dělení a kontrakce hran zachovává rovinnost. Kuratowského věta (bez důkazu). [K 6.1–6.5, 6.7] | video poznámky |
18. 12. | Plán: Barvení map: převod pomocí duality na barvení rovinných grafů. Barvení grafů: dobré obarvení, barevnost grafu, souvislost s klikovostí. 2-obarvitelné grafy jsou právě ty bipartitní, což jsou ty bez lichých kružnic. Barvení indukcí: stromy, 6-barevnost rovinných grafů, (Δ+1)-barevnost grafů s maximálním stupněm Δ. Barevnost rovinných grafů: věta o 5 barvách (s důkazem), věta o 4 barvách (bez důkazu). Aplikace barevnosti: přiřazování kanálů, rozvrhování přednášek [K 6.8]. Platónská tělesa a souvislost s rovinnými grafy [K 6.6]. | |
8. 1. | Plán: Ramseyova věta pro grafy, vícebarevná Ramseyova věta, nekonečná Ramseyova věta (spočetná verze), Ramseyova čísla a jejich dolní odhad pravděpodobnostní metodou. [K 11.1–11.3, R] |
Zkoušky
Termíny jsou vypsané v SISu, přihlašujte se prosím tam. Zápočet je potřeba získat před zkouškou.
Zkouška bude ústní s písemnou přípravou: Na začátku zadám otázky. Vy si odpovědi rozmyslíte (času bude dost) a sepíšete. Pak si o nich spolu popovídáme a na základě toho dostanete buďto známku, nebo nápovědu k další práci. Cílem je, aby každý vyřešil všechno, a známka se bude odvíjet od toho, jak moc jsem vám musel napovídat :)
Ke zkoušce je potřeba:
- znát teorii, která byla odpřednesena (včetně důkazů);
- umět teorii používat k řešení příkladů podobných těm, které jste potkali na cvičeních.
Všechny definice i tvrzení byste měli umět přesně formulovat (se všemi předpoklady, a to i na známku dobře) a dokázat (s výjimkou vět, jejichž důkaz jsem nepřednášel). Brzy se tu objeví katalog definic, vět a příkladů. K dispozici je katalog definic, vět a příkladů. Úlohy z minulých termínů přidávám do sbírky příkladů.
Pokud byste z nějakého důvodu zkoušku nestihli složit, mohu vás vyzkoušet i později – během letního zkouškového, během semestru, případně i o prázdninách. Na to už obvykle termíny nevypisuji, vše je na individuální domluvě. Tuto možnost nicméně doporučuji využít spíš v nouzi, než si tak rovnou zkoušku plánovat.
Přeji hodně štěstí a jasnou mysl.
Literatura
- 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)