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:

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

Stránku spravuje Martin Mareš