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. Plán: Odhady faktoriálu a kombinačních čísel. [K 3.4–3.5] Princip inkluze a exkluze, dva jeho důkazy: počítací a algebraický. Problém šatnářky. [K 3.6–3.7]

Cvičení

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

Literatura

Stránku spravuje Martin Mareš