Diskrétní matematika

V zimním semestru 2021/2022 se Diskrétní matematika [NDMI002] vyučuje ve třech paralelkách:

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.

datum co se přednášelo [zdroj] záznam
5. 10. Co je diskrétní matematika. Úvodní příklady: šest lidí v autobuse, 3 domečky a 3 studny, od skákání po schodišti až k Fibonacciho číslům, Jak se buduje matematika (definice, axiomy, věty, důkazy). Ukázky důkazových technik (sporem, indukcí, minimálním protipříkladem). Sumy a produkty. [K 1.1–1.2] video
12. 10. Množiny a základní operace s nimi. Důkaz neexistence množiny všech množin. 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í. [K 1.3–1.5] video
14. 10. Vlastnosti relací: reflexivita, symetrie, antisymetrie, transitivita. Ekvivalence: definice, popis pomocí rozkladu na ekvivalenční třídy. [K 1.5] 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, řetězce/antiřetězce. [K 2.1–2.2] video
21. 10. Kombinatorické počítání: počet funkcí, prostých funkcí, permutací; počet všech podmnožin, k-prvkových podmnožin, sudých a lichých podmnožin. Popisování podmnožin a posloupností pomocí funkcí. [K 3.1–3.2] Kombinační čísla a jejich základní vlastnosti. Pascalův trojúhelník a Binomická věta. [K 3.3] Viz též kombinatorický tahák. video
28. 10. Přednáška se nekoná. Vyberte si svůj svátek.
4. 11. Princip inkluze a exkluze, dva jeho důkazy: počítací a algebraický. Problém šatnářky. [K 3.6–3.7] Odhady faktoriálu. [K 3.4] video
11. 11. Odhady kombinačních čísel. [K 3.5] Úvod do teorie grafů: definice a základní značení, zoo grafů, bipartitnost, isomorfismus grafů, počet (neisomorfních) grafů. [K 4.1] Stupeň a skóre, regularita, princip sudosti. [K 4.4] video
18. 11. Podgrafy a indukované podgrafy, cesty a kružnice v grafech, relace dosažitelnosti, souvislost a komponenty souvislosti. Matice sousednosti a počítání sledů jejím umocňováním. Vzdálenost v grafu (metrika). [K 4.1, 4.2] Operace s grafy: přidání a odebrání vrcholu/hrany, dělení hrany. [K 4.7] video
25. 11. Operace s grafy: kontrakce hrany. [K 4.7] 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. [K 4.5, 4.6] video
2. 12. Plán: Stromy: definice, lemma o koncovém vrcholu, princip stromové indukce, věta o charakterizaci stromů. [K 5.1] Kostra grafu: definice, existence, význam. [K 5.3] Kreslení (multi)grafů do roviny. Trocha topologie roviny (oblouky, topologické kružnice), definice rovinného nakreslení. Cesty a kružnice jsou rovinné, stromy taktéž. Stěny nakreslení. [K 6.1]

Cvičení

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

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.

Literatura

Stránku spravuje Martin Mareš