teaching:dm1920_prednaska
Toto je starší verze dokumentu!
Přednáška z Diskrétní matematiky 2019/20
Přednáším Diskrétní matematiku (NDMI002) každé úterý v 9:00 v učebně S5.
Pokud se mnou chcete cokoliv probrat, jste vítáni v mé pracovně S326 na Malé Straně. Případně napište e-mail na adresu koutecky+dm@iuuk.mff.cuni.cz
a/nebo uveďte v předmětu text [DM]
.
V druhé paralelce přednáší Martin Mareš, přednášku se budeme snažit udržovat synchronní.
datum | co se přednášelo [zdroj] |
---|---|
1. 10. | Motivační příklady: na každé party o 5 lidech se tři znají nebo tři neznají, kdy jde obrázek nakreslit jedním tahem, kolika způsoby skákat po schodech. Co je diskrétka a k čemu je dobrá? Jak se buduje matematika (definice, axiomy, věty, důkazy: přímo, sporem, indukcí). Značení: sumy, produkty, množiny, n-tice, kartézský součin. [K 1.1-1.3] |
8. 10. | Relace, jejich znázornění, příklady od doc. Fialy (1, 2, 3), skládání a inverze. Vlastnosti relací: reflexivita, symetrie, tranzitivita, slabá antisymetrie. Ekvivalence a to, že jsou jednoznačně vystiženy svými třídami. [K 1.4-1.5] |
15. 10. | Částečná uspořádání (příklad), funkce prosté, na, bijektivní. Úvod do kombinatorického počítání, počet funkcí $f: [n] \to [m]$, počet prostých funkcí, počet podmnožin $[n]$, binomický koeficient $\binom{n}{k}$ a kombinatorické důkazy pár základních vztahů s $\binom{n}{k}$. [K 2.1-2.3] |
22. 10. | Binomická věta [Z 4], odhady $n!$ a $\binom{n}{k}$ [K 2.4-2.5], princip inkluze a exkluze [K 2.6] |
29. 10. | Imatrikulace – můžete si přečíst možná překvapivou stránku o slavné písni Gaudeamus Igitur |
5. 11. | Plán: problém šatnářky [K 2.7], úvod do teorie grafů [3.1-3.2] |
12. 11. | Děkanský den |
Užitečné zdroje
- Návod ke Studnici vědomostí, která obsahuje mnohé jinak těžko sehnatelné materiály, mrk, mrk.
- Matoušek, Nešetřil: Kapitoly z diskrétní matematiky, Karolinum. Existuje několik různých vydání, která se liší číslováním kapitol; odkazy výše jsou podle staršího (černého). Také pozor na drobné chyby ve starších vydáních (viz errata). [K]
- Matoušek: Podrobný sylabus o pravděpodobnosti [P] (PDF)
- Mareš, Valla: Průvodce labyrintem algoritmů [L]
- Slajdy doc. Fialy, většinou obsahují konkrétní příklady, dobré pro získání intuice.
- Poznámky Toma Slámy z přednášek Martina Mareše
teaching/dm1920_prednaska.1571737644.txt.gz · Poslední úprava: 2019/10/22 11:47 autor: Martin Koutecky