|
Vyučující
|
-
Marek Josef, doc. Ing. Ph.D.
|
|
Obsah předmětu
|
1. Kombinatorika. Pokročilá kombinatorika. 2. Diferenční rovnice. Diskrétní dynamické systémy. 3. Základní algebraické struktury. Modulární počítání. Latinské čtverce. 4. Rozpoznávání prvočísel. Kódování a kryptografie. 5. Bloková schémata. Steinerovy trojice. 6. Uspořádání. Svazy. Booleovy algebry. Booleovské funkce. Minimalizace forem. 7. Základní pojmy teorie grafů. Souvislost grafu. Minimální kostra. Eulerovské grafy. 8. Rovinné grafy. Grafy na plochách. Orientované grafy. Silná souvislost. k-souvislost. 9. Maticový popis grafu. Algebraické vlastnosti matic. Spektra matic a vlastnosti grafu. 10. Vzdálenost v grafech. Dijkstrův algoritmus, Floydův-Warshallův algoritmus. Dynamické programování. 11. Kritická cesta. Prostor kružnic a řezů grafu. 12. Hamiltonovské grafy. Barvení grafů. Extremální teorie grafů. Úvod do Ramseyovy teorie. 13. Grafové úlohy jako optimalizační problémy. Výpočetní složitost.
|
|
Studijní aktivity a metody výuky
|
Přednáška s aktivizací, Přednáška, Cvičení
- Kontaktní výuka
- 52 hodin za semestr
- Příprava na dílčí test [2-10]
- 30 hodin za semestr
- Příprava na zkoušku [10-60]
- 56 hodin za semestr
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| u posluchačů se předpokládá znalost základních pojmů podmiňujícího předmětu (KMA/LA nebo KMA/LA-A) a znalost kombinatoriky v rozsahu učiva střední školy |
| Výsledky učení |
|---|
| úspěšný absolvent bude schopen: - řešit základní úlohy kombinatoriky, - prokázat znalost základních matematických pojmů relace a funkce, - aplikovat základní poznatky teorie grup, - řešit rovnice s kongruencemi, - definovat a rozpoznat relaci uspořádání, - popsat svazy a Booleovské algebry, - pracovat s Booleovskými funkcemi, - aktivně používat základní pojmy teorie grafů, - popsat grafovou strukturu pomocí matic a využít je ke zjištění vlastností grafu, - aplikovat lineární algebru v teorii grafů, - řešit úlohu kritické cesty |
| Vyučovací metody |
|---|
| Přednáška založená na výkladu, |
| Přednáška s aktivizací studentů, |
| Cvičení (praktické činnosti), |
| Hodnotící metody |
|---|
| Kombinovaná zkouška, |
| Test, |
| Demonstrace dovedností (praktická činnost), |
|
Doporučená literatura
|
-
Gross, Jonathan; Yellen, Jay. Graph theory and its applications. Boca Raton : CRC Press, 1999. ISBN 0-8493-3982-0.
-
Matoušek, Jiří; Nešetřil Jaroslav. Invitation to discrete mathematics. Oxford University Press, USA, 1998. ISBN 978-0198502081.
-
Scheinerman, Edward R. Mathematics: A discrete introduction. Brooks Cole, 2005. ISBN 978-0534398989.
-
Van Lint, J. H.; Wilson, R. M. A course in combinatorics. Cambridge : Harvard University Press, 2001. ISBN 0-521-00601-5.
|