Diskrétní matematika

V zimním semestru 2022/2023 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.

Více se tu objeví začátkem semestru.

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

datum co se přednášelo [zdroj] záznam
4. 10. Co je diskrétní matematika. Úvodní příklad: šest lidí v autobuse. 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. Dvojice, k-tice a kartézské součiny. Důkaz neexistence množiny všech množin. [K 1.1–1.3] video
12. 10. 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.5] video
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, řetězce/antiřetězce. V konečné uspořádané množině vždy existuje minimální prvek. [K 2.1–2.2] 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, T] video
26. 10. Kombinační čísla a jejich základní vlastnosti. Pascalův trojúhelník a Binomická věta. Rozklad čísla na součet, přihrádkový princip. [K 3.3, T] Princip inkluze a exkluze, dva jeho důkazy: počítací a algebraický [K 3.6]. video
1. 11. Problém šatnářky (aplikace inkluze a exkluze) [K 3.7]. Odhady faktoriálu a kombinačních čísel [K 3.4–3.5]. Úvod do teorie grafů: definice a základní značení, zoo grafů, bipartitnost, isomorfismus grafů [K 4.1]. video
8. 11. Grafy: Počet (neisomorfních) grafů [K 4.1], stupeň a skóre, regularita, princip sudosti, věta o skóre [K 4.4]. Podgrafy a indukované podgrafy, cesty a kružnice v grafech [K 4.2]. video
15. 11. Grafy: Relace dosažitelnosti, souvislost a komponenty souvislosti [K 4.2]. Operace s grafy: přidání a odebrání vrcholu/hrany, dělení hrany, kontrakce hrany [K 4.7]. Kreslení grafů jedním tahem: věta o existenci uzavřeného eulerovského tahu [K 4.5]. Orientované grafy: silná a slabá souvislost, eulerovské tahy [K 4.6]. video
22. 11. Přednáška se nekoná: dnes otevíráme dveře.
29. 11. Matice sousednosti a počítání sledů jejím umocňováním [K 4.2]. Vzdálenost v grafu (metrika) [K 4.2]. 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]. (Alternativní způsob budování teorie viz poznámky Zdeňka Dvořáka níže.) video
6. 12. Rovinné grafy: Neformální definice nakreslení a jeho stěn. 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. 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
13. 12. Plán: 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]
20. 12. Plán: Diskrétní pravděpodobnost: 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. Aplikace linearity střední hodnoty. Rozdělení náhodné veličiny, Markovova nerovnost. [K 10.2, 10.3; P 16–30]
3. 1. Plán: Sbíráme ovoce u cesty (aneb aplikace diskrétní matematiky): Řetězce a antiřetězce, věta o Dlouhém a Širokém. [K 2.4] 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]. Platónská tělesa a souvislost s rovinnými grafy [K 6.6].

Cvičení

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

Zkoušky

Termíny budou vypsané v SISu. Zkoušet budu prezenčně, kdybyste někdo potřebovali vyzkoušet dálkově, 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). Brzy se tu objeví 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š