Diskrétní matematika

V zimním semestru 2024/2025 učím Diskrétní matematiku pro studenty matematiky [NMIN105]. Přednáška se koná ve středy od 10:40 v N1.

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.

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

datum co se přednášelo [zdroj] záznam
2. 10. Co je diskrétní matematika. Pár příkladů pro začátek: šest lidí v tramvaji, prvočísel je nekonečně mnoho, jak se sčítá (konečná) aritmetická a geometrická řada, jedničková čísla a jejich dělitelnost. Důkazové techniky: rozbor případů, obměna, spor, indukce, princip holubníku. video poznámky
9. 10. Kombinatorické počítání: řetězce nad danou abecedou, řetězce bez opakování, permutace, popis pomocí funkcí, charakteristické posloupnosti podmnožin, sudé a liché podmnožiny, k-prvkové podmnožiny. Kombinační čísla a jejich vlastnosti. Pascalův trojúhelník a Binomická věta. [K 3.3, T] video poznámky
16. 10. Diskrétní pravděpodobnost: diskrétní pravděpodobnostní prostor a jevy, nezávislost jevů. Zmínka o součinových prostorech. video poznámky
23. 10. Přednáška odpadá: Imatrikulace. Gaudeamus igitur!
30. 10. Diskrétní pravděpodobnost: podmíněná pravděpodobnost, věta o rozboru případů, Bayesova věta. Problém šatnářky [K 3.7]. Princip inkluze a exkluze [K 3.7]. video poznámky
6. 11. Důkaz principu inkluze a exkluze. Úvod do grafů: Příklad s mosty města Královce. Definice grafu, cesta/tah/sled, souvislost, stupeň vrcholu, věta o existenci uzavřeného eulerovského tahu [K 4.5]. Co se změní v orientovaných grafech: vstupní/výstupní stupeň, vyvážené grafy, silná a slabá souvislost, existence uzavřeného eulerovského tahu [K 4.6]. video poznámky
13. 11. Úvod do grafů: definice a základní značení, zoo grafů, bipartitnost [K 4.1], stupeň a princip sudosti [K 4.4], podgrafy a indukované podgrafy, cesty a kružnice v grafech [K 4.2] Extremální úloha: grafy bez trojúhelníků [K 4.8]. video poznámky
20. 11. Stromy: motivace kostrou grafu [K 5.3], definice, lemma o koncovém vrcholu, lemma o odebírání listů, stromy jsou souvislé grafy s n vrcholy a n-1 hranami, věta o charakterizaci stromů [K 5.1]. Relace a způsoby jejich znázorňování (maticí, různými grafy), inverzní relace [K 1.4]. video poznámky
27. 11. Plán: 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, tranzitivita. Ekvivalence: definice, popis pomocí rozkladu na ekvivalenční třídy. [K 1.4–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. V konečné uspořádané množině vždy existuje minimální prvek. [K 2.1–2.2]

Literatura

Stránku spravuje Martin Mareš