Diskrétní matematika

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

Můžete sledovat přímý přenos z přednášek.

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. 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í. Stěny nakreslení. [K 6.1] video
9. 12. Rovinné grafy: Cesty a kružnice jsou rovinné, stromy taktéž. Jordanova věta o kružnici (bez důkazu). K5 není rovinný. 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; zmínka o kreslení na další plochy. 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] video
16. 12. Barvení map: převod pomocí duality na barvení rovinných grafů. Barvení grafů: dobré obarvení, barevnost grafu, souvislost s klikovostí. 2-obarvitelné grafy jsou právě ty bipartitní, což jsou ty bez lichých kružnic. Barvení indukcí: stromy, 6-barevnost rovinných grafů, (Δ+1)-barevnost grafů s maximálním stupněm Δ. Barevnost rovinných grafů: věta o 5 barvách (s důkazem), věta o 4 barvách (bez důkazu). Aplikace barevnosti: přiřazování kanálů, rozvrhování přednášek. [K 6.8] Úvod do diskrétní pravděpodobnosti: pravděpodobnostní prostory, elementární a složené jevy. Příklady pravděpodobnostních prostorů. Bertrandův paradox (barevné kartičky). [P 1–15] video
6. 1. Diskrétní pravděpodobnost: podmíněná pravděpodobnost, věta o úplné pravděpodobnosti, Bayesova věta, nezávislost jevů. Střední hodnota a její linearita. Aplikace linearity střední hodnoty. [K 10.2, 10.3; P 16–30] Omlouvám se za chybějící tabuli v první cca šestině videozáznamu. video

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.

Zkoušky

Termíny jsou vypsané v SISu. Zkoušet budu prezenčně, kdybyste někdo potřebovali vyzkoušet dálkově (třeba proto, že jste zrovna v karanténě), ozvěte se mi prosím e-mailem.

Zkouška bude ústní s písemnou přípravou: Na začátku zadám otázky. Vy si odpovědi rozmyslíte (času bude dost) a sepíšete. Pak si o nich spolu popovídáme a na základě toho dostanete buďto známku, nebo nápovědu k další práci. Cílem je, aby každý vyřešil všechno, a známka se bude odvíjet od toho, jak moc jsem vám musel napovídat :)

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). K dispozici je katalog definic, vět a příkladů. Úlohy z minulých termínů přidávám do sbírky příkladů.

Zápočet můžete skládat nezávisle na zkoušce. Nicméně doporučuji mít před zkouškou spočítaných dost příkladů, je to skvělá příprava.

Pokud byste z nějakého důvodu zkoušku nestihli složit, mohu vás vyzkoušet i později – během letního zkouškového, během semestru, případně i o prázdninách. Na to už obvykle termíny nevypisuji, vše je na individuální domluvě. Tuto možnost nicméně doporučuji využít spíš v nouzi, než si tak rovnou zkoušku plánovat.

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

Literatura

Stránku spravuje Martin Mareš