teaching:kg12021_prednaska
Toto je starší verze dokumentu!
Přednáška z Kombinatoriky a grafů I 2020/21
Přednáším Kombinatoriku a grafy 1 (NDMI011) každé úterý v 10:40.
Pokud máte dotaz, který můžete vznést veřejně, nejlepší prostor je tým v MS Teams. Pokud v něm nejste, napište mi email. Pokud máte soukromý dotaz, napište mi e-mail na adresu koutecky@iuuk.mff.cuni.cz a do předmětu uveďte text [KG1]. Až bude probíhat výuka osobně, jste též vítáni v mé pracovně S326.
Další materiály doplním v průběhu semestru.
| datum | co se přednášelo [zdroj] |
|---|---|
| 29. 9. | Odhady faktoriálu - jednoduchý, lepší pomocí indukce a integrování, zmínka Stirlingovy formule. Odhad $\binom{n}{k}$ jako $n^k$ když $k \ll n$ a dále lepší odhady $\binom{2m}{m}$. [K 2.4-2.5], záznam |
| 6. 10. | Náhodné procházky. Úvod do vytvořujících funkcí. [K 10.1-10.2], záznam, slajdy doc. Fialy a Martina Balka. |
| 13. 10. | Vytvořující funkce: odvození vzorce pro Fibonacciho a Catalanova čísla. [K 10.3-10.4], úvod do konečných projektivních rovin [K 8.1], záznam, prezentace M. Balka, Fanova rovina (Fiala). |
| 20. 10. | Pokračování KPR: každá přímka má $n+1$ bodů a každým bodem prochází $n+1$ přímek a každá KPR má $n^2 + n + 1$ přímek i bodů; dualita; konstrukce KPR z algebraického tělesa [K 8.1-8.2], záznam, slajdy - konstrukce KPR z alg. tělesa (Fiala), |
| 27. 10. | Pokračování KPR: dokončení konstrukce KPR z algebraického tělesa [K 8.2] souvislosti navzájem ortogonálních latinských čtverců a KPR [K 8.3], záznam, slajdy - konstrukce KPR z NOLČ (Fiala); Slajdy KPR a NOLČ (Balko) |
| 3. 11. | Plán: Počítání dvěma způsoby (Cayleyho formule pomocí POVYKOSů [K 7.6], grafy bez $C_4$ mohou mít nanejvýš $\Oh(n^{3/2})$ hran [6.3], Spernerova věta o velikosti antiřetězce [6.2] |
| 10. - 24. 11 | Plán: Toky v sítích [L 2, 4], [M1] |
| 1. - 8. 12. | Plán: Míra souvislosti grafů [L 3], [K 3.8] |
| 8. - 22. 12. | Plán: Samoopravné kódy [T] |
| 5. 1. | Plán: Ramseyova teorie [K 11 - nové vydání] |
Užitečné zdroje KG1
- Studentské zápisky z přednášky. Velké díky: Tomáš Sláma, Matěj Kripner, Filip Pešek.
- Návod ke Studnici vědomostí, která obsahuje mnohé jinak těžko sehnatelné materiály, mrk, mrk.
- [K] 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).
- [P] Matoušek: Podrobný sylabus o pravděpodobnosti (PDF)
- [L] Mareš, Valla: Průvodce labyrintem algoritmů
teaching/kg12021_prednaska.1604394210.txt.gz · Poslední úprava: 2020/11/03 10:03 autor: Martin Koutecky