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

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. Plán: 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ů. Kostra grafu: definice, existence, význam. [K 4.2, 5.1]

Cvičení

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

Literatura

Stránku spravuje Martin Mareš