|
Vyučující
|
-
Kuřil Martin, RNDr. Ph.D.
|
|
Obsah předmětu
|
1. Kombinatorické počítání (počet podmnožin, posloupnosti, permutace, počet uspořádaných podmnožin, počet podmnožin dané mohutnosti). 2. - 3. Kombinatorické prostředky (indukce, porovnávání a odhady čísel, princip inkluze a exkluze, Dirichletův princip). 4. Binomické koeficienty a Pascalův trojúhelník (binomická věta, Pascalův trojúhelník, identity v Pascalově trojúhelníku). 5. Fibonacciho čísla (Fibonacciho úloha, identity s Fibonacciho čísly, formule pro Fibonacciho čísla). 6. Grafy (definice, součet stupňů všech vrcholů v grafu, cesty, cykly, souvislost, eulerovské tahy, hamiltonovské cykly). 7. - 8. Stromy (definice, počítání stromů, reprezentace stromů, počet neoznačených stromů). 9. Hledání optima (problém minimální kostry, problém obchodního cestujícího). 10. Kombinatorika v geometrii (průsečíky diagonál, počítání oblastí, konvexní mnohoúhelníky). 11. Eulerova formule (rovinné grafy, Eulerova formule pro souvislé rovinné grafy, Eulerova formule pro mnohostěny). 12. - 13. Barvení map a grafů (barvení oblastí dvěma barvami, barvení grafů dvěma barvami, barvení grafů více barvami, chromatické číslo grafu, barvení map, důkaz věty o pěti barvách, věta o čtyřech barvách). Pozn.: Na cvičeních se bude každý týden procvičovat látka z příslušné přednášky.
|
|
Studijní aktivity a metody výuky
|
|
nespecifikováno
|
|
Výstupy z učení
|
Cílem předmětu není pokrýt diskrétní matematiku ve velké šíři, ale spíše probrat několik vybraných výsledků a metod, většinou z oblasti kombinatoriky a teorie grafů. Důraz je kladen na rozvoj matematického myšlení a na řešení problémů (v kombinatorice a teorii grafů lze již na počátku snadno formulovat zajímavé a podnětné problémy).
|
|
Předpoklady
|
nespecifikováno
|
|
Hodnoticí metody a kritéria
|
nespecifikováno
Požadavky k zápočtu: Na počátku zkouškového období se bude psát jedna zápočtová písemná práce, ze které je třeba získat více než jednu třetinu bodů. Ve zkouškovém období je možno psát dvě opravné zápočtové písemné práce. Z opravné zápočtové písemné práce je třeba získat více než jednu třetinu bodů.
|
|
Doporučená literatura
|
-
Fuchs, E. Diskrétní matematika pro učitele. Masarykova univerzita, Brno, 2011.
-
Harris, J. M., Hirst, J. L., Mossinghoff, M. J. Combinatorics and Graph Theory. Springer, New York, 2008.
-
Knuth, D. E. Umění programování, 1. díl, Základní algoritmy. Computer Press, a.s., Brno, 2008.
-
Lovász, L., Pelikán, J., Vesztergombi, K. Discrete Mathematics: Elementary and Beyond. Springer, New York, 2003.
-
Matoušek, J., Nešetřil, J. Kapitoly z diskrétní matematiky. Karolinum, Praha, 2002.
|