| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:dm1920_prednaska [2019/10/01 11:58] – Martin Koutecky | teaching:dm1920_prednaska [2020/01/09 14:20] (aktuální) – okruhy Martin Koutecky |
|---|
| V druhé paralelce přednáší [[http://mj.ucw.cz/vyuka/1920/dm/|Martin Mareš]], přednášku se budeme snažit udržovat synchronní. | V druhé paralelce přednáší [[http://mj.ucw.cz/vyuka/1920/dm/|Martin Mareš]], přednášku se budeme snažit udržovat synchronní. |
| |
| {{tablelayout?colwidth="100px,-"&rowsHeaderSource=1&rowsVisible=2&float=left}} | {{tablelayout?colwidth="100px,-"&rowsHeaderSource=1&rowsVisible=100&float=left}} |
| ^ datum ^ co se přednášelo [zdroj] ^ | ^ 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]**| | | 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 ([[https://kam.mff.cuni.cz/~fiala/DM/010-reprezentace_relace.pdf|1]], [[https://kam.mff.cuni.cz/~fiala/DM/012-vlastnosti_relaci.pdf|2]], [[https://kam.mff.cuni.cz/~fiala/DM/015-relace_ekvivalence.pdf|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í ([[https://kam.mff.cuni.cz/~fiala/DM/020-cast_usp.pdf|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 **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson4.pdf|[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 [[https://en.wikipedia.org/wiki/Gaudeamus_igitur|Gaudeamus Igitur]]//| |
| | | 5. 11. | Problém šatnářky **[K 2.7]**, **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson4.pdf|[Z 4, Př 5]]]**, [[https://kam.mff.cuni.cz/~fiala/DM/050-satnarka.pdf|příklad pro $n=4$]]. Úvod do teorie grafů -- definice: graf, úplný graf (klika), prázdný graf, cesta, kružnice, podgraf, indukovaný podgraf, doplněk grafu, sled v grafu, tah, cesta, cyklus, relace dosažitelnosti $u \sim v$ (z $u$ existuje cesta do $v$), isomorfismus, stupeň. Důkazy: odhad na počet neisomorfních grafů, dosažitelnost $u \sim v$ je ekvivalence, princip sudosti. **[K 3.1-3.2]**, **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson7b.pdf|[Z 7b]]]**, **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson8.pdf|[Z 8]]]**| |
| | | 12. 11. | //[[https://www.mff.cuni.cz/cs/vnitrni-zalezitosti/dekansky-den/2019|Děkanský den]]//| |
| | | 19. 11. | Souvislost a komponenty souvislosti. Vzdálenosti v grafu (metrika). Operace s grafy: přidání a odebrání vrcholu/hrany. Stromy: definice, lemma o koncovém vrcholu, princip stromové indukce, věta o charakterizaci stromů. **[K 3.2, 3.4, trochu 3.8, 4.1, 4.3]**, [**[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson8.pdf|Z 8]], [[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson9.pdf|Z 9 (bez Eulerovských tahů)]]**].| |
| | | 26. 11. | Kostra grafu: definice, existence, význam. Kreslení grafů jedním tahem: věta o existenci uzavřeného eulerovského tahu. Orientované grafy: silná a slabá souvislost, eulerovské tahy. Kreslení grafů do roviny. Trocha topologie roviny (oblouky, topologické kružnice), definice rovinného nakreslení. Stěny nakreslení. Jordanova věta o kružnici (bez důkazu). **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson9.pdf|Z 9 (bez stromů)]]**, **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson10.pdf| Z 10]]**].| |
| | | 3. 12. | $K_5$ není rovinný. Kreslení na sféru, stereografická projekce a možnost zvolit si vnější stěnu. Dualita rovinných (multi)grafů. Eulerova formule, horní odhad na počet hran rovinného grafu, existence vrcholu nízkého stupně. **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson10.pdf| Z 10]]**.| |
| | | 11. 12. | Podrozdělení hrany a Kuratovského věta (znění bez důkazu). Barvení map a Problém 4 barev, převod barvení mapy na barvení rovinných grafů. $d$-degenerované grafy jsou $d+1$-obarvitelné. Věta o 5 barvách. **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson11.pdf| Z 11]]**.| |
| | | 18. 12. | Úvod do pravděpodobnosti, diskrétní pravděpodobnostní prostor, věta o úplné pravděpodobnosti, podmíněná pravděpodobnost. Náčrt: náhodná veličina, střední hodnota, linearita střední hodnoty, indikátor (vrátíme se k nim). **[[http://kam.mff.cuni.cz/~matousek/dm-prob-2pp.ps|P]]**.| |
| | | 7. 1. | Náhodná veličina, střední hodnota a její linearita, indikátor, rozptyl, Markovova a Čebyševova nerovnost. **[[http://kam.mff.cuni.cz/~matousek/dm-prob-2pp.ps|P]]**, slajdy doc. Fialy: [[https://kam.mff.cuni.cz/~fiala/DM/060-2_kostky.pdf|6]], [[https://kam.mff.cuni.cz/~fiala/DM/070-test_nemoci.pdf|7]], [[https://kam.mff.cuni.cz/~fiala/DM/080-rozdeleni.pdf|8]], [[https://kam.mff.cuni.cz/~fiala/DM/090-nahodna_velicina_kostka.pdf|9]], [[https://kam.mff.cuni.cz/~fiala/DM/100-stredni_hodnota_karty.pdf|10]], [[https://kam.mff.cuni.cz/~fiala/DM/110-odhad_pravdepodobnosti.pdf|11]], [[https://kam.mff.cuni.cz/~fiala/DM/120-zavislost_velicin.pdf|12]].| |
| | |
| | **{{ :teaching:dm1920:otazky.pdf |Okruhy zkoušky.}}** |
| |
| |
| {{page>teaching:bits:zdroje_dm}} | {{page>teaching:bits:zdroje_dm}} |
