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

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š