Diskrétní matematika

V zimním semestru 2018/2019 přednáším Diskrétní matematiku [NDMI002]. Přednáška se koná každé úterý od 10:40 v S5.

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

V druhé paralelce přednáší Zdeněk Dvořák, přednášky se budeme snažit udržovat synchronní.

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]
2. 10. Co je diskrétní matematika. Úvodní příklad: od skákání po schodišti až k Fibonacciho číslům. Jak se buduje matematika (definice, axomy, věty, důkazy). Ukázky důkazových technik (přímo, sporem, minimálním protipříkladem, indukcí). Sumy a produkty. Množiny a základní operace s nimi. Dvojice, k-tice a kartézské součiny. Důkaz neexistence množiny všech množin. [K 1.1–1.3]
9. 10. 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, transitivita. Ekvivalence: definice, popis pomocí rozkladu na ekvivalenční třídy. [K 1.4–1.6]
16. 10. Uspořádání: definice, příklady (dělitelnost, inkluze, lexikografické uspořádání), bezprostřední předchůdce, Hasseovy diagramy, nejmenší a minimální prvky. Kombinatorické počítání: počet funkcí, prostých funkcí, permutací; počet všech podmnožin, sudých a lichých podmnožin, k-prvkových podmnožin. Kombinační čísla a jejich základní vlastnosti; Binomická věta. [K 2.1, 2.2, 3.1–3.3]
23. 10. Důkaz Binomické věty. Princip inkluze a exkluze, dva jeho důkazy: počítací a algebraický. Problém šatnářky. [K 3.6, 3.7]
30. 10. Místo přednášky se koná imatrikulace. Gaudeamus igitur!
6. 11. Místo přednášky pohyb: děkanský sportovní den.
13. 11. Úvod do diskrétní pravděpodobnosti: pravděpodobnostní prostory, elementární a složené jevy, 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. [K 10.2, 10.3; P 1–24]
20. 11. Pravděpodobnost: střední hodnota a její linearita. Rozptyl, Markovova a Čebyševova nerovnost. [K 10.2, 10.3; P 25–37] Úvod do teorie grafů: definice a základní značení. [K 4.1]
27. 11. Teorie grafů: zoo grafů, isomorfismus grafů, odhad počtu neisomorfních grafů na n vrcholech, stupeň a skóre, princip sudosti, podgrafy a indukované podgrafy, cesty a kružnice v grafech, souvislost a komponenty souvislosti. Charakterizace bipartitních grafů. Vzdálenosti v grafu (metrika). (Přednášel Jiří Fiala.) [K 4.1, 4.2, 4.4 bez Věty o skóre]
4. 12. 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ů. Kostra grafu: definice, existence, význam. [K 4.2, 5.1]
11. 12. Kreslení grafů jedním tahem: věta o existenci uzavřeného eulerovského tahu. Orientované grafy: silná a slabá souvislost, eulerovské tahy. Kreslení grafů do roviny. Trocha topologie roviny (oblouky, topologické kružnice), definice rovinného nakreslení. Stěny nakreslení. [K 4.5, 4.6, 6.1, 6.2]
18. 12. Jordanova věta o kružnici (bez důkazu). K5 není rovinný. Barvení map a Problém 4 barev. Kreslení na sféru, stereografická projekce a možnost zvolit si vnější stěnu. Dualita rovinných (multi)grafů, převod barvení mapy na barvení rovinných grafů. Eulerova formule, triangulování grafů, horní odhad na počet hran rovinného grafu, existence vrcholu nízkého stupně. Věta o 5 barvách. [K 6.3–6.5, 6.8]
8. 1. Částečně uspořádané množiny: Linearizace částečného uspořádání, vnořování do inkluze, věta o Dlouhém a Širokém, Erdősovo-Szekeresovo lemma. Topologické uspořádání orientovaného grafu coby jiný pohled na linearizaci uspořádání. [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

Už je to tak, k přednášce patří i zkouška :) Na termíny se prosím zapisujte v SISu. Předtermín je 11. 1. 2019 od 12:20 v S9.

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).

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

Literatura

Stránku spravuje Martin Mareš