|
Vyučující
|
-
Přibyl Jiří, PhDr. Ph.D.
-
Kuřil Martin, RNDr. Ph.D.
|
|
Obsah předmětu
|
1. Kombinatorické počítání (počet podmnožin, počet posloupností, prostá zobrazení a permutace, 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 (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, reprezentace a počítání stromů, isomorfismus 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).
|
|
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: Podmínkou udělení zápočtu je získání alespoň polovičního množství bodů ze dvou zápočtových písemných prací, které studenti píšou v průběhu semestru. Ve zkouškovém období je možno psát celkem dvě opravné zápočtové písemné práce. Zkouška bude písemná.
|
|
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, 2008.
-
Herman, J., Kučera, R., Šimša, J. Metody řešení matematických úloh II. Brno: Masarykova univerzita, 2004.
-
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. Praha: Karolinum, 2002.
|