Diskrétní matematika

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

Na přednášky používáme Zoom, odkaz jste dostali mailem. Pokud vám chybí, napište mi prosím. Videozáznamy přednášek se budou objevovat zde.

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] video
5. 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, axiomy, věty, důkazy). Ukázky důkazových technik (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] video tabule
12. 10. 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] video tabule
19. 10. 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. V konečné uspořádané množině vždy existuje minimální prvek. [K 2.1–2.2] Řetězce a antiřetězce, věta o Dlouhém a Širokém. [K 2.4] video tabule
26. 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 tabule
2. 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 a kombinačních čísel. [K 3.4–3.5] video tabule
9. 11. Úvod do teorie grafů: definice a základní značení, zoo grafů, bipartitnost, isomorfismus grafů. [K 4.1] Stupeň a skóre, regularita, princip sudosti, věta o skóre. [K 4.4] video tabule
16. 11. Grafy: počet (neisomorfních) grafů, 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, kontrakce hrany. [K 4.7] video tabule
23. 11. 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] Stromy: definice, lemma o koncovém vrcholu, princip stromové indukce. [K 5.1] video tabule
30. 11. Věta o charakterizaci stromů. Kostra grafu: definice, existence, význam. [K 5.1, 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] video tabule
7. 12. Kreslení (multi)grafů do roviny: 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] Barvení map: převod pomocí duality na barvení rovinných grafů. [K 6.8] video tabule
14. 12. Barvení grafů: dobré obarvení, barevnost grafu, souvislost s klikovostí, degenerovaností a maximálním stupněm. 2-obarvitelné grafy jsou právě ty bipartitní, což jsou ty bez lichých kružnic. Barevnost rovinných grafů: 6-barevnost z degenerovanosti, věta o 5 barvách (s důkazem), věta o 4 barvách (bez důkazu). [K 6.8] Úvod do diskrétní pravděpodobnosti: pravděpodobnostní prostory, elementární a složené jevy. [P 1–12] video tabule
21. 12. Diskrétní pravděpodobnost: příklady pravděpodobnostních prostorů, 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, nezávislost projekcí. Střední hodnota a její linearita. [K 10.2, 10.3; P 13–28] video tabule
4. 1. Pravděpodobnost: aplikace linearity střední hodnoty, rozdělení náhodné veličiny, Markovova nerovnost. [P 29–31, 36]. Sbíráme ovoce u cesty (aneb aplikace diskrétní matematiky): Erdősovo-Szekeresovo lemma o monotónních podposloupnostech [K 2.4]. De Bruijnovy posloupnosti a jejich konstrukce pomocí orientovaných eulerovských tahů (příklad pro k=4) [K 4.6]. video tabule

Cvičení

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

Zkoušky

Termíny jsou vypsané v SISu. V prvním týdnu zkouškového jsou čistě distanční. V dalších týdnech jsou vypsány jak prezenční (držíme si palce, aby to šlo), tak distanční termíny. Stále platí, že preferuji prezenční zkoušení, ale pokud bydlíte daleko a je pro vás problém přijet na otočku do Prahy, vyzkouším vás distančně. Pokud se termíny hodně zaplní, vypíši ještě další.

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

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š