| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:kg12021_prednaska [2020/11/03 10:03] – plán Martin Koutecky | teaching:kg12021_prednaska [2021/01/08 13:34] (aktuální) – zkouska Martin Koutecky |
|---|
| | 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)]], | | | 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)]]| | | 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. | //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]**//| | | 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. - 24. 11 | //Plán: Toky v sítích **[L 2, 4]**, **[M1]**//| | | 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]]| |
| | 1. - 8. 12. | //Plán: Míra souvislosti grafů **[L 3]**, **[K 3.8]**//| | | 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]]| |
| | 8. - 22. 12. | //Plán: Samoopravné kódy **[T]**//| | | 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)]]| |
| | 5. 1. |//Plán: Ramseyova teorie **[K 11 - nové vydání]**//| | | 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}} |
| |
