Kombinatorika a grafy I - NDMI011 (LS 2017/18)
přednášející V. Jelínek
Přednáška se koná v úterý od 10:40 v S3.
Zkoušky:
Zkouškové termíny byly vypsány
v SISu, další ještě přibudou. Alespoň jeden zkouškový termín vypíšu v
září. K absolvování zkoušky je potřeba nejprve získat zápočet (ovšem v
SISu se můžete na termíny hlásit i tehdy, pokud ještě zápočet nemáte,
důležité je mít zápočet v SISu před tím, než přijdete na zkoušku).
Zkouška na mých termínech je písemná, s možností ústního dozkoušení pro
ty, kdo nebudou spokojeni se známkou z písemné části. Ústní dozkoušení
probíhá obvykle odpoledne v den písemné části zkoušky. Na ústním
dozkoušení si můžete známku z písemné části vylepšit ale i zhoršit.
Co se probralo:
- 20. 2.: Odhady na důležité kombinatorické funkce [MN: kapitoly 2.4 a 2.5].
- 27. 2.: Vytvořující funkce, zobecněná binomická věta, odvození
vytvořující funkce pro posloupnost zadanou pomocí rekurence s
konstantními koeficienty [MN: kapitoly 10.1-10.3].
- 6. 3.: Počítání koeficientů vytvořujících funkcí pomocí rozkladu na
parciální zlomky [MN:kapitola 10.3]. Catalanova čísla, definovná jako počet binárních zakořeněných
stromů, odvození jejich vytvořující funkce a vzorečku [MN: kapitola 10.4]. Definice projektivní
roviny [MN: kap. 8.1].
- 13. 3.: Vlastnosti konečných projektivních rovin [MN: kap. 8.1]. Definice latinských
čtverců a jejich ortogonality [MN: kap. 8.3].
- 20. 3.: Horní odhad na počet navzájem ortogonálních lat. čtverců,
souvislost s projektivními rovinami [MN: kap. 8.3]. Toky v sítích:
základní pojmy, souvislost mezi velikostí max. toku a kapacitou
minimálního řezu [VM: kapitola 2].
- 27. 3.: Königova-Egerváryho věta o velikosti největšího párování
a nejmenšího vrcholového pokrytí v bipartitních grafech [M: kap. 1].
Hallova věta (ve verzi pro systém různých reprezentantů v hypergrafu a
ve verzi pro párování v bipartitním grafu) [VM: kap. 4].
- 3. 4.: Vrcholová a hranová souvislost grafu. Mengerovy věty charakterizující hranově a vrcholově k-souvislé grafy [VM: kap. 3].
- 10. 4.: Lemma o uších [MN: kap. 3.8]. Počítání dvěma způsoby:
počet koster úplného grafu a úplného grafu bez jedné hrany [MN: kap 7.6
a kap. 7.1 cv. 2].
- 17. 4.: Spernerova věta o nezávislém systému množin [MN: kap.
6.2]. Ramseyova věta o existenci velké kliky nebo velké nezávislé
množiny v grafu, její ekvivalentní formulace pomocí barvení hran
úplného grafu dvěma barvami, zobecnění na více barev [VM, kap. 1, M2].
- 24. 4.: Ramseyova věta pro barvení p-tic, zformulovaná v konečné
a nekonečné verzi, důkaz nekonečné verze [M2]. Königovo lemma, ukázka
jeho použití: jestliže každý konečný podgraf spočetného grafu G má
barevnost nejvýš b, tak i G má barevnost nejvýš b [M3].
- 15. 5.: Opravné kódy - základní pojmy: Hammingova vzdálenost,
kódování, dekódování, lineární kód, generující matice a její použití
ke kódování lineárního kódu, ortogonální doplněk, kontrolní matice [T].
- 22. 5.: Souvislost mezi minimální vzdáleností lineárního kódu a
sloupci kontrolní matice. Hammingovy kódy: jejich parametry a
dekódováni pomócí kontrolní matice. Singletonův, Hammingův a
Gilbertův-Varshamovův odhad na parametry kódů [T].
Doporučená literatura:
- [MN] J. Matoušek a J. Nešetřil: Kapitoly z Diskrétní matematiky,
Karolinum
2003. V některých vydáních knihy je několik
chyb,
pozor na ně.
- [VM] Skriptíčka
T. Vally a J. Matouška, ke stažení zde.
- [T] Učební text T. Kaisera k přednášce o samoopravných kódech, ke
stažení zde.
- [M] M. Mareš: Krajinou grafových algoritmů, ke stažení zde.
- [M2] M. Mareš: Ramseyovy věty, ke stažení zde.
- [M3] M. Mareš: Kombinatorické drobnosti, ke stažení zde.
Předchozí odkazy pokrývají celou látku přednášky. Odkazy na další
užitečnou literaturu najdete na stránkách Martina Mareše.
Cvičení a zápočty:
Informace o podmínkách získání zápočtu se dozvíte od svých cvičících. K této paralelce náleží některé z následujících cvičení:
Zkoušky: Přihlašování pomocí SISu,
termíny tamtéž. Zkouška se skládá z písemky, s možností ústního
dozkoušení. Nutnou podmínkou účasti u zkoušky je zisk zápočtu.