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 se mnou chcete cokoliv probrat, jste vítáni v mé pracovně S322 na Malé Straně. Případně napište e-mail na adresu mares+dm@kam.mff.cuni.cz.

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. Plán: 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, Jordanova věta o kružnici [bez důkazu]). K5 není rovinný. Stěny nakreslení a jejich hranice (u souvislých grafů to jsou uzavřené sledy). Kreslení na sféru, stereografická projekce a možnost zvolit si vnější stěnu. [K 4.5, 4.6, 6.1, 6.2]

Cvičení

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

Literatura

Stránku spravuje Martin Mareš