Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- teaching:dm2324_prednaska [2023/11/07 23:33] – Martin Koutecky
+++ teaching:dm2324_prednaska [2024/01/10 00:04] (aktuální) – zkouska Martin Koutecky
@@ Řádek 8: / Řádek 8: @@
 ^ datum ^ co se přednášelo [zdroj] ^
 | 3. 10. | Motivační příklady: na každé party o 6 lidech se tři znají nebo tři neznají, kdy jde obrázek nakreslit jedním tahem. 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]**, **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson1.pdf|[Z 1]]]** |
-| 10. 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. **[K 1.4-1.5]**, **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson2.pdf|[Z 2]]]**|
+| 10. 10. | Relace, jejich znázornění, skládání a inverze. Vlastnosti relací: reflexivita, symetrie, tranzitivita, slabá antisymetrie. Ekvivalence. **[K 1.4-1.5]**, **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson2.pdf|[Z 2]]]**|
 | 17. 10. | Dodělávka: ekvivalence jsou jednoznačně určeny svými třídami. Částečná uspořádání, funkce prosté, na, bijektivní. **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson2.pdf|[Z 2]]]**, **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson3.pdf|[Z 3]]]**|
 | 24. 10. | Věta o dlouhém a širokém ([[https://slama.dev/poznamky/diskretni-matematika#dlouh%C3%BD-a-%C5%A1irok%C3%BD|zde]]). Ú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]**, [[http://mj.ucw.cz/papers/komb-tahak.pdf|Kombinatorika do kapsy od M. Mareše]], [[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson3.pdf|[Z 3]]].|
 | 31. 10. | Binomická věta **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson4.pdf|[Z 4]]]**, jednoduchý odhad $\binom{n}{\lfloor n/2\rfloor}$ **[K 2.4-2.5]**, princip inkluze a exkluze **[K 2.6]**  Problém šatnářky **[K 2.7]**, **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson4.pdf|[Z 4, Př 5]]]** |
 | 7. 11. | Ú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ň. Souvislost a komponenty souvislosti. Vzdálenosti v grafu (metrika). Důkazy: 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]]]**|
-| 14. 11. | //Plán: Uzavřené a otevřené eulerovské tahy (jednotažky), Stromy (definice: minimální souvislé grafy; alternativa: souvislé bez kružnice; mají vždy $n-1$ hran **[K 3.2, 3.4, trochu 3.8, 4.1, 4.3]**, **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson9.pdf|Z 8]]**//|
+| 14. 11. | Uzavřené a otevřené eulerovské tahy (jednotažky), Stromy (definice: minimální souvislé grafy; alternativa: souvislé bez kružnice; mají vždy $n-1$ hran **[K 3.2, 3.4, trochu 3.8, 4.1, 4.3]**, **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson9.pdf|Z 9]]**|
+| 21. 11. | //Den otevřených dveří//|
+| 28. 11. | Dokončení stromů (charakterizace) **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson9.pdf|Z 9]]**; Věta o skóre (na zkoušce budu chtít znění, ale ne důkaz). **[K 3.4]**|
+| 5. 12. | Kreslení grafů do roviny -- nejprve intuitivně. Co je to rovinné nakreslení a jeho stěny, stereografická projekce, Eulerova formule (vzorec), rovinné grafy mají $O(n)$ hran, průměrný stupeň v rovinných grafech je $<6$ ($<4$ pro grafy bez $K_3$), tedy vždy existuje vrchol stupně $\geq 5$ (resp. $\geq 3$). Náčrt definice duálu $G$. **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson10.pdf|Z 10]]**|
+| 12. 12. | Dualita rovinných (multi)grafů, podrozdělení hrany a Kuratovského věta (znění bez důkazu). Rovinnost trochu formálněji **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson10.pdf|Z 10]]**. Barvení grafů, $d$-degenerované grafy jsou $d+1$-obarvitelné. Věta o 4 barvách (bez důkazu). **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson11.pdf| Z 11]]**|
+| 19. 12. | jak souvisí barvení rovinných grafů a politických map, věta o 5 barvách. **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson11.pdf| Z 11]]**. Základy pravděpodobnosti: diskrétní pravděpodobnostní prostor, věta o úplné pravděpodobnosti, podmíněná pravděpodobnost. **[[https://research.koutecky.name/db/_media/teaching:bits:dm-prob-2pp.pdf|P]]**|
+| 9. 1. | Nezávislost jevů. 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]]**|
-/*
-| 18. 11. | Uzavřené a otevřené eulerovské tahy (jednotažky), Stromy (definice: minimální souvislé grafy; alternativa: souvislé bez kružnice; mají vždy $n-1$ hran **[K 3.2, 3.4, trochu 3.8, 4.1, 4.3]**, **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson9.pdf|Z 8]]** [[https://stream.cuni.cz/cs/Detail/15544|záznam]]|
-| 25. 11. | Dokončení stromů (charakterizace); něco o počítání sledů délky $k$ a grafové metrice. Věta o skóre. [[https://stream.cuni.cz/cs/Detail/15647|záznam]]|
-| 2. 12. | Kreslení grafů do roviny. Trocha topologie roviny (oblouky, topologické kružnice), definice rovinného nakreslení. Stěny nakreslení.  **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson10.pdf|Z 10]]**, [[https://stream.cuni.cz/cs/Detail/15739|záznam]].|
-| 9. 12. | Jordanova věta o kružnici (bez důkazu). Dualita rovinných (multi)grafů, Eulerova formula, horní odhad na počet hran rovinného grafu. **[[https://iuuk.mff.cuni.cz/~rakdver/dm/lesson10.pdf|Z 10]]** [[https://stream.cuni.cz/cs/Detail/15846|záznam]]|
-| 16. 12.| Existence vrcholu nízkého stupně. 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]]**. Základy pravděpodobnosti: diskrétní pravděpodobnostní prostor, věta o úplné pravděpodobnosti, podmíněná pravděpodobnost. **[[https://research.koutecky.name/db/_media/teaching:bits:dm-prob-2pp.pdf|P]]** [[https://stream.cuni.cz/cs/Detail/15988|záznam]]|
-| 6. 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]]. [[https://stream.cuni.cz/cs/Detail/16154|záznam]] | */
-**[[https://research.koutecky.name/dm_zkouska.html|Okruhy zkoušky (21/22)]]**
+**[[https://research.koutecky.name/dm2324_zkouska.html|Okruhy zkoušky]]**
-{{ :teaching:dm2122:priklad_zkouska_2122.pdf |Ukázka zkouškového zadání. (21/22)}}
+{{ :teaching:dm2122:priklad_zkouska_2122.pdf |Ukázka zkouškového zadání.}}
 {{page>teaching:bits:zdroje_dm}}