Kombinatorika a grafy I - NDMI011 (LS 2018/19)

přednášející V. Jelínek

Přednáška se koná ve středu od 12:20 v S5.

Zkoušky:

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.

Obsah přednásky bude obdobný loňské verzi.

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].
13. 3.: Vlastnosti konečných projektivních rovin [MN: kap. 8.1]. Definice latinských čtverců a jejich ortogonality, horní odhad na počet navzájem ortogonálních lat. čtverců, souvislost s projektivními rovinami [MN: kap. 8.3].
20. 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 pro p=1,2 [M2]. Königovo lemma [M3], náznak důkazu konečné Ramseyovy věty z nekonečné pomocí Königova lemmatu [M2].
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í:

Pondělí 14:00 T8 (vede J. Amemori)
Úterý 14:00 S10 (vedu já)
Středa 14:00 S10 (vede J. Pekárek)
Pátek 10:40 S6 (vede T. Klimošová)