teaching:kg12021_prednaska
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. | Počítání dvěma způsoby. Spernerova věta o velikosti antiřetězce [K 6.2], grafy bez $C_4$ mohou mít nanejvýš $O(n^{3/2})$ hran [K 6.3], Cayleyho formule pomocí POVYKOSů [K 7.6]. záznam, Fialovy slajdy: Spernerova věta, Rekurence na počet koster v grafu, #koster přes determinanty |
| 10. 11. | Toky v sítích [MV 2], Fialovy slajdy: ukázka sítě, F-F algoritmus, cyklení F-F, Slajdy M. Balka, záznam |
| 24. 11 | Aplikace toků: Königova věta (v bipartitním grafu platí max párování = min vrcholové pokrytí), Hallova věta (nutná a postačující podmínka pro existenci systému různých reprezentantů neboli párování pokrývající jednu stranu bipartitního grafu), aplikace Hallovy věty (doplňování latinských obdélníků) – dokončení příště. [MV 4], [M1], záznam, ukázka SRR, doplňování latinských obdélníků, slajdy M. Balka |
| 1. 12. | Míra souvislosti grafů [MV 3], záznam, slajdy (Balko), konstrukce $t$ cest (Fiala) |
| 8. 12. | Konstrukce $2$-souvislých grafů pomocí lepení uší [K 3.8], Úvod do samoopravných kódů [T] záznam, slajdy (Fiala), slajdy (Balko) |
| 15. 12. | Základní odhady na $A(n,d)$, lineární kódy [T 3]. záznam |
| 22. 12. | Dokončení samoopravných kódů: jak se dekóduje Hammingův kód a že je perfektní. [T 3 + začátek 4]; úvod do Ramseyovy teorie [K 11 – nové vydání], záznam, slajdy (Balko) - kódy, slajdy (Balko) - Ramsey |
| 5. 1. | Ramseyovy věty: více barev, $p$-tice, nekonečné grafy. [M 2], záznam |
Zkouška
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.txt · Poslední úprava: 2021/01/08 13:34 autor: Martin Koutecky