Diskrétní matematika, zimní semestr 2008/2009 (P. Kolman)
Predtermin 18.12.: Kdo zkousku udelal, najde vysledek v SISu, kdo nikoli,
nema v SISu napsano nic.
Predtermin 12.1.: Kdo zkousku udelal, najde vysledek v SISu, kdo nikoli,
nema v SISu napsano nic (do SISu zadano v 958 v utery).
Pozadavky ke zkousce: Nize vyjmenovane casti z tretiho vydani
knihy Kapitoly z diskretni matematiky (Nesetril, Matousek). Naprostou
vetsinu latky jsme probrali na prednasce, malou cast si nastudujte z
knihy.
Kapitola 1
Kapitola 2
Kapitola 3 (bez 3.5)
Kapitola 4 (pouze 4.1, 4.2, 4.5, 4.8)
Kapitola 5 (bez 5.4)
Kapitola 7
Kapitola 8 (pouze 8.1, 8.2 a 8.6)
Kapitola 11 (bez 11.3)
Kapitola 13 (pouze 13.4)
Terminy zkousek budou vypsany v SISu. Prvni predtermin bude uz pred vanocemi
(ctvrtek 18.12.).
1. přednáška (1. 10. 2008)
Úvod, princip matematické indukce.
2. přednáška (22. 10. 2008)
Relace, zobrazeni, pocitani zobrazeni a podmnozin.
3. přednáška (29. 10. 2008)
Dalsi pocitani, binomicke koeficienty; relace ekvivalence a usporadani.
4. přednáška (5. 11. 2008)
Podrobneji o relacich ekvivalence (rozklad na tridy) a usporadani
(lexikograficke, castecne a linearni, minimalni prvek).
5. přednáška (12. 11. 2008)
Pokracovani o usporadani (zuplnovani castecneho; vnorovani jednoho
do druheho; maximalni velikost retezce a antiretezce; Lemma Erdos-Szekeres).
6. přednáška (19. 11. 2008)
Faktoriál - odhady, princip inkluze a exkluze
7. přednáška (26. 11. 2008)
Šatnářka;
Grafy - úvod, izomorfismus grafů
8. přednáška (3. 12. 2008)
Eulerovské grafy; grafy bez trojúhelníků
9. přednáška (10. 12. 2008)
Stromy
10. přednáška (17. 12. 2008)
Pocitani dvema zpusoby, princip sudosti, nezavisly system mnozin
11. přednáška (7. 1. 2009)
Minimální kostra grafu, hladový algoritmus; prostor kružnic graf
leden 2009