Diskrétní matematika

V zimním semestru 2019/2020 přednáším Diskrétní matematiku [NDMI002]. Přednáška se koná každý čtvrtek od 10:40 v S5. Ve druhé paralelce přednáší Martin Koutecký, přednášky se budeme snažit udržovat synchronní.

Pokud chcete cokoliv konzultovat, napište mi prosím e-mail na mares+dm@kam.mff.cuni.cz a domluvíme se.

Studentům kombinovaného studia doporučuji vybrat si libovolného cvičícího a domluvit se s ním na získání zápočtu za domácí úkoly. Účast na cvičení není nutná, ale hodí se alespoň občas se tam stavit, abyste měli přehled, co se dělá. Za mnou samozřejmě můžete přijít na konsultaci, domluvte se e-mailem.

datum co se přednášelo [zdroj]
3. 10. Co je diskrétní matematika. Úvodní příklady: šest lidí v autobuse, od skákání po schodišti až k Fibonacciho číslům, 3 domečky a 3 studny. Jak se buduje matematika (definice, axomy, věty, důkazy). Ukázky důkazových technik (přímo, sporem, indukcí, minimálním protipříkladem). Sumy a produkty. Množiny a základní operace s nimi. Důkaz neexistence množiny všech množin. [K 1.1–1.3]
10. 10. Potence množiny. Dvojice, k-tice a kartézské součiny. Relace a způsoby jejich znázorňování (maticí, různými grafy). 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, transitivita. Ekvivalence: definice, popis pomocí rozkladu na ekvivalenční třídy. [K 1.4–1.6]
17. 10. Důkaz věty o ekvivalenčních třídách. Uspořádání: definice, příklady (dělitelnost, inkluze, lexikografické uspořádání), bezprostřední předchůdce, Hasseovy diagramy, nejmenší/minimální a největší/maximální prvky. Kombinatorické počítání: počet funkcí, prostých funkcí, permutací; počet všech podmnožin, k-prvkových podmnožin. Popisování podmnožin a posloupností pomocí funkcí. [K 2.1–2.2, 3.1–3.2]
24. 10. Kombinační čísla a jejich základní vlastnosti. Pascalův trojúhelník a Binomická věta. [K 3.3] Odhady faktoriálu a kombinačních čísel. [K 3.4–3.5]
31. 10. Princip inkluze a exkluze, dva jeho důkazy: počítací a algebraický. Problém šatnářky. [K 3.6–3.7] Úvod do teorie grafů: definice a základní značení, zoo grafů, isomorfismus grafů. [K 4.1]
7. 11. Grafy: odhad počtu neisomorfních grafů na n vrcholech, stupeň a skóre, princip sudosti, věta o skóre, podgrafy a indukované podgrafy, cesty a kružnice v grafech, souvislost a komponenty souvislosti. [K 4.1, 4.2, 4.4]
14. 11. Grafy: Vzdálenost v grafu (metrika). Operace s grafy: přidání a odebrání vrcholu/hrany, dělení hrany, kontrakce hrany. Stromy: definice, lemma o koncovém vrcholu, princip stromové indukce, věta o charakterizaci stromů. [K 4.2, 5.1]
21. 11. Přednáška odpadá: Otevíráme dveře
28. 11. Kostra grafu: definice, existence, význam. Kreslení grafů jedním tahem: věta o existenci uzavřeného eulerovského tahu. Odbočka k multigrafům. Orientované grafy: silná a slabá souvislost, eulerovské tahy. Kreslení (multi)grafů do roviny. Trocha topologie roviny (oblouky, topologické kružnice), definice rovinného nakreslení. [K 4.5, 4.6, 6.1]
5. 12. Kreslení (multi)grafů do roviny: Cesty a kružnice jsou rovinné, stromy taktéž. Jordanova věta o kružnici (bez důkazu). K5 není rovinný. Stěny nakreslení, hranice stěny je nakreslením uzavřeného sledu. Kreslení na sféru, stereografická projekce a možnost zvolit si vnější stěnu. Eulerova formule, triangulování grafů, horní odhad na počet hran rovinného grafu, existence vrcholu nízkého stupně; analogické věty pro grafy bez trojúhelníků. K3,3 není rovinný. Kuratowského věta (bez důkazu). [K 6.1–6.5]
12. 12. Barvení grafů: dobré obarvení, barevnost grafu, souvislost s klikovostí, degenerovaností a maximálním stupněm. 2-obarvitelné grafy jsou právě ty bipartitiní, což jsou ty bez lichých kružnic. Barevnost rovinných grafů: 6-barevnost z degenerovanosti, věta o 5 barvách (s důkazem), věta o 4 barvách (bez důkazu). Barvení map: převod pomocí duality na barvení rovinných grafů. Úvod do diskrétní pravděpodobnosti: pravděpodobnostní prostory, elementární a složené jevy. [K 6.8, P 1–12]
19. 12. Diskrétní pravděpodobnost: Bertrandův paradox (barevné kartičky), podmíněná pravděpodobnost, věta o úplné pravděpodobnosti, Bayesova věta, nezávislost jevů. Součinové prostory, nezávislost projekcí. Střední hodnota a její linearita. [K 10.2, 10.3; P 13–30]
9. 1. Pravděpodobnost: rozdělení náhodné veličiny, rozptyl, směrodatná odchylka, Markovova a Čebyševova nerovnost, nezávislost náhodných veličin a její důsledky (střední hodnota součinu, rozptyl součtu). Částečně uspořádané množiny: Linearizace částečného uspořádání (topologické uspořádání orientovaného grafu), věta o Dlouhém a Širokém, Erdősovo-Szekeresovo lemma. [P 34–41, K 2.2, 2.4, L 5.8]

Cvičení

Jelikož paralelky jsou synchronní, můžete si vybrat libovolné cvičení. Cvičení vedou:

Zkoušky

Na termíny se prosím zapisujte v SISu. 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).

Zápočet můžete skládat nezávisle na zkoušce.

Přeji hodně štěstí a čistou mysl.

Literatura

Stránku spravuje Martin Mareš