Rozdíly

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

--- teaching:dm2122_prednaska [2021/11/04 18:01] – Martin Koutecky
+++ teaching:dm2122_prednaska [2022/01/06 19:50] (aktuální) – prednaska 6. 1. Martin Koutecky
@@ Řádek 15: / Řádek 15: @@
 | 28. 10. | //Odpadá -- státní svátek//|
 | 4. 11. | 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]**  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$]]. [[https://stream.cuni.cz/cs/Detail/15351|záznam, bohužel jen čtvrtina obrazovky]], příště snad už bude vše OK...|
-| 11. 11. | //Plán: Ú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]]]** // |
+| 11. 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]]]**, [[https://stream.cuni.cz/cs/Detail/15457|záznam]]|
+| 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]]**
-| 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]]**].|
+{{ :teaching:dm2122:priklad_zkouska_2122.pdf |Ukázka zkouškového zadání.}}
-| 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.}}** */