|
Vyučující
|
-
Kabela Adam, RNDr. Ph.D.
-
Šebková Milena, RNDr.
-
Ekstein Jan, RNDr. Ph.D.
-
Teska Jakub, RNDr. Mgr. Ph.D.
-
Holub Přemysl, Doc. RNDr. Ph.D.
-
Čada Roman, Doc. Ing. Ph.D.
|
|
Obsah předmětu
|
1. Základní pojmy teorie množin. Relace a zobrazení. Kombinatorika. 2. Základní algebraické struktury. Modulární aritmetika. 3. Uspořádání, vlastnosti. Hasseův diagram. 4. Svazy. Distributivní, komplementární svaz. 5. Booleova algebra. Booleovský kalkulus. Direktní součin booleovských algeber, Stoneova věta o reprezentaci. 6. Booleovské funkce. Booleovské polynomy, disjunktivní a konjunktivní normální forma. Minimální forma. 7. Orientované a neorientované grafy. Základní grafové pojmy. Grafové homomorfismy. 8. Souvislost grafu. Stromy a kostry. Eulerovské grafy. Orientované grafy. Slabá a silná souvislost. Acyklické grafy, kondenzace grafu. 9. Maticová reprezentace grafu: matice sousednosti, incidenční matice, Laplaceova matice. Základy algebraické a spektrální teorie grafů. 10. Počet koster grafu. Počty sledů. Aplikace. 11. Ohodnocené grafy. Jemný úvod do algoritmů a výpočetní složitosti. 12. Aplikační úlohy: minimální kostra, vzdálenost a minimální cesta, kritická cesta, úloha čínského pošťáka. 13. Úvod do dalších oblastí: rovinné grafy, hamiltonovské grafy, barvení grafů, toky v sítích, rozsáhlé sítě, kódování, kryptografie.
|
|
Studijní aktivity a metody výuky
|
Skupinová výuka, Přednáška
- Kontaktní výuka
- 52 hodin za semestr
- Příprava na dílčí test [2-10]
- 18 hodin za semestr
- Příprava na zkoušku [10-60]
- 58 hodin za semestr
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| formulovat s porozuměním podstatě věci základní pojmy lineární algebry a vysvětlit jejich základní vlastnosti |
| Odborné dovednosti |
|---|
| aplikovat s porozuměním podstatě věci základní metody a techniky lineární algebry |
| Obecné způsobilosti |
|---|
| bc. studium: své učení a pracovní činnost si sám plánuje a organizuje, |
| Výsledky učení |
|---|
| Odborné znalosti |
|---|
| popsat maticový popis grafu a vysvětlit vztahy mezi vlastnostmi grafu a algebraickými vlastnostmi příslušné matice |
| vysvětlit algoritmické aspekty řešení základních grafových úloh |
| formulovat základní pojmy z teorie grafů a vysvětlit jejich základní vlastnosti, včetně porozumění souvislostem |
| vysvětlit základní pojmy z teorie relačních struktur: binární relace, ekvivalence (včetně aplikace na aritmetiku modulo 2), uspořádání a částečného uspořádání, Booleovy algebry a Booleovské polynomy a funkce |
| Odborné dovednosti |
|---|
| popsat grafovou strukturu pomocí matice včetně porozumění vztahům mezi vlastnostmi grafu a algebraickými vlastnostmi příslušné matice |
| řešit jednoduché úlohy v aritmetikách modulo k |
| ovládat pojmy ekvivalence a rozkladu množiny na třídy ekvivalence |
| navrhnout a formulovat algoritmy řešení základních grafových úloh, analyzovat jejich teoretické a algoritmické vlastnosti, a navržené algoritmy prakticky použít |
| prakticky použít základy teorie Booleových algeber, včetně vyjádření Booleovského polynomu v konjunktivní a disjunktivní normální formě |
| Obecné způsobilosti |
|---|
| aktivně využívá získané znalosti a dovednosti při řešení praktických problémů |
| Vyučovací metody |
|---|
| Odborné znalosti |
|---|
| Cvičení (praktické činnosti), |
| Přednáška založená na výkladu, |
| Odborné dovednosti |
|---|
| Přednáška založená na výkladu, |
| Cvičení (praktické činnosti), |
| Obecné způsobilosti |
|---|
| Přednáška založená na výkladu, |
| Cvičení (praktické činnosti), |
| Hodnotící metody |
|---|
| Odborné znalosti |
|---|
| Kombinovaná zkouška, |
| Test, |
| Demonstrace dovedností (praktická činnost), |
| Odborné dovednosti |
|---|
| Demonstrace dovedností (praktická činnost), |
| Test, |
| Kombinovaná zkouška, |
| Obecné způsobilosti |
|---|
| Test, |
| Kombinovaná zkouška, |
| Demonstrace dovedností (praktická činnost), |
|
Doporučená literatura
|
-
Biggs, Norman L. Discrete Mathematics. Oxford Univ. Press, 2002. ISBN 9780198507178.
-
Čada, Roman; Kaiser, Tomáš; Ryjáček, Zdeněk. Diskrétní matematika. Plzeň : Západočeská univerzita, 2004. ISBN 80-7082-939-7.
-
Gross, Jonathan L.; Yellen, Jay; Anderson, Mark. Graph Theory and Its Applications. Chapman and Hall/CRC, New York, 2018. ISBN 9781482249484.
-
Keller, M.T.; Trotter, W.T. Applied Combinatorics. CreateSpace Independent Publishing Platform. 2017.
-
Kopka, Jan. Svazy a Booleovy algebry. Univerzita J.E.Purkyně v Ústí nad Labem, 1991. ISBN 80-7044-025-2.
-
Matoušek, Jiří; Nešetřil, Jaroslav. Kapitoly z diskrétní matematiky. Čtvrté, upravené a doplněné vydání. 2019. ISBN 978-80-246-1740-4.
|