| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:kg12021_prednaska [2020/09/29 17:36] – Martin Koutecky | teaching:kg12021_prednaska [2021/01/08 13:34] (aktuální) – zkouska Martin Koutecky |
|---|
| ^ datum ^ co se přednášelo [zdroj] ^ | ^ 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]**, [[https://stream.cuni.cz/cs/Detail/5653|záznam]]| | | 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]**, [[https://stream.cuni.cz/cs/Detail/5653|záznam]]| |
| | | 6. 10. | Náhodné procházky. Úvod do vytvořujících funkcí. **[K 10.1-10.2]**, [[https://stream.cuni.cz/cs/Detail/5858|záznam]], slajdy [[https://kam.mff.cuni.cz/~fiala/KG1/011-vytvorujici_fce.pdf|doc. Fialy]] a [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace2.pdf|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]**, [[https://stream.cuni.cz/cs/Detail/6127|záznam]], [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace3.pdf| prezentace M. Balka]], [[https://kam.mff.cuni.cz/~fiala/KG1/020-Fanova_rovina.pdf|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]**, [[https://stream.cuni.cz/cs/Detail/7319|záznam]], [[https://kam.mff.cuni.cz/~fiala/KG1/025-konstrukce_z_teles.pdf|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]**, [[https://stream.cuni.cz/cs/Detail/7596|záznam]], [[https://kam.mff.cuni.cz/~fiala/KG1/030-konstrukce_proj_roviny.pdf|slajdy - konstrukce KPR z NOLČ (Fiala)]]; [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace5.pdf| 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]**. [[https://stream.cuni.cz/cs/Detail/7832|záznam]], Fialovy slajdy: [[https://kam.mff.cuni.cz/~fiala/KG1/040-Spernerova_veta.pdf|Spernerova věta]], [[https://kam.mff.cuni.cz/~fiala/KG1/035-kostry_rekurence.pdf|Rekurence na počet koster v grafu]], [[https://kam.mff.cuni.cz/~fiala/KG1/037-kostry_det.pdf|#koster přes determinanty]]| |
| | | 10. 11. | Toky v sítích **[MV 2]**, Fialovy slajdy: [[https://kam.mff.cuni.cz/~fiala/KG1/070-toky.pdf|ukázka sítě]], [[https://kam.mff.cuni.cz/~fiala/KG1/065-Ford_Fulkerson.pdf|F-F algoritmus]], [[https://kam.mff.cuni.cz/~fiala/KG1/080-nekonecne_zlepsovani.pdf|cyklení F-F]], [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace6.pdf|Slajdy M. Balka]], [[https://stream.cuni.cz/cs/Detail/8026|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]**, [[https://stream.cuni.cz/cs/Detail/8413|záznam]], [[https://kam.mff.cuni.cz/~fiala/KG1/100-Hall.pdf|ukázka SRR]], [[https://kam.mff.cuni.cz/~fiala/KG1/110-latin.pdf|doplňování latinských obdélníků]], [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace7.pdf|slajdy M. Balka]]| |
| | | 1. 12. | Míra souvislosti grafů **[MV 3]**, [[https://stream.cuni.cz/cs/Detail/9622|záznam]], [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace8.pdf|slajdy (Balko)]], [[https://kam.mff.cuni.cz/~fiala/KG1/060-konstrukce_cest.pdf|konstrukce $t$ cest (Fiala)]]| |
| | | 8. 12. | Konstrukce $2$-souvislých grafů pomocí lepení uší **[K 3.8]**, Úvod do samoopravných kódů **[T]** [[https://stream.cuni.cz/cs/Detail/9752|záznam]], [[https://kam.mff.cuni.cz/~fiala/KG1/125-kody.pdf|slajdy (Fiala)]], [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace12.pdf|slajdy (Balko)]]| |
| | | 15. 12. | Základní odhady na $A(n,d)$, lineární kódy **[T 3]**. [[https://stream.cuni.cz/cs/Detail/9916|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í]**, [[https://stream.cuni.cz/cs/Detail/10006|záznam]], [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace12.pdf|slajdy (Balko) - kódy]], [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace10.pdf|slajdy (Balko) - Ramsey]] | |
| | | 5. 1. | Ramseyovy věty: více barev, $p$-tice, nekonečné grafy. **[M 2]**, [[https://stream.cuni.cz/cs/Detail/10079|záznam]]| |
| | |
| | |
| | ===== Zkouška ===== |
| | |
| | {{ :teaching:kg12021:okruhy_kg1.pdf |Popis formy a obsahu zkoušky.}} |
| |
| {{page>teaching:bits:zdroje_kg1}} | {{page>teaching:bits:zdroje_kg1}} |
| |
