|
Lecturer(s)
|
-
Marek Josef, doc. Ing. Ph.D.
|
|
Course content
|
1. Combinatorics. 2. Advanced combinatorics. Difference equations. 3. Discrete dynamical systems. 4. Basic algebraic structures. Modular counting. Latin squares. 5. Detecting primes. Code theory and cryptography. 6. Boolean algebras. Boolean functions. Minimisation. 7. Basic concepts of graph theory. Graph connectivity. Minimum spanning tree. Eulerian graphs. 8. Planar graphs. Digraphs. Strong connectivity. k-connectivity. 9. Matrices assigned to graphs. Algebraic properties of matrices. Spectra of matrices and graph properties. 10. Distance in graphs. Dijkstra algorithm. Floyd-Warshall algorithm. 11. Critical path. Cycle and cut spaces. 12. Hamiltonian graphs. Graph colouring. Basics of Ramsey theory. 13. Graph problems as optimisation tasks. Computational complexity.
|
|
Learning activities and teaching methods
|
Lecture, Practicum
- Contact hours
- 39 hours per semester
- Preparation for an examination (30-60)
- 30 hours per semester
- Preparation for comprehensive test (10-40)
- 11 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| popsat pojem množiny |
| popsat pojem funkce |
| vymezit pojem vektoru a matice |
| Skills |
|---|
| řešit soustavy rovnic |
| vypočítat vlastní čísla a vektory matice |
| využívat derivace a integrály |
| Competences |
|---|
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| ovládat metody řešení jednodušších kombinatorických úloh |
| definovat základní pojmy z oblasti Booleovských funkcí |
| definovat základní pojmy teorie grafů |
| znát algoritmy k řešení základních grafových úloh |
| Skills |
|---|
| řešit soustavy rovnic v aritmetice modulo k |
| vyčíslovat a zjednodušovat Booleovské funkce |
| řešit eulerovské problémy teorie grafů |
| zjistit vzdálenost v grafech pomocí Dijkstrova algoritmu |
| řešit úlohu minimální kostry grafu |
| určit prostor kružnic a řezů grafu |
| Competences |
|---|
| N/A |
| N/A |
| teaching methods |
|---|
| Knowledge |
|---|
| Interactive lecture |
| Lecture |
| Practicum |
| Skills |
|---|
| Practicum |
| Interactive lecture |
| Competences |
|---|
| Interactive lecture |
| Practicum |
| assessment methods |
|---|
| Knowledge |
|---|
| Oral exam |
| Skills |
|---|
| Written exam |
| Competences |
|---|
| Oral exam |
| Written exam |
|
Recommended literature
|
-
Čada, Roman; Kaiser, Tomáš; Ryjáček, Zdeněk. Diskrétní matematika. Plzeň : Západočeská univerzita, 2004. ISBN 80-7082-939-7.
|