|
Lecturer(s)
|
-
Sido Richard, RNDr. Ph.D.
-
Vávrová Miroslava, RNDr.
-
Pěchota Jan, RNDr. Ph.D.
-
Hofman Martin, RNDr. Mgr. Ph.D.
-
Kopal Stanislav, doc. RNDr. Ph.D.
-
Marek Josef, doc. Ing. Ph.D.
|
|
Course content
|
1. Basic set theory. Relations and mappings. Combinatorics. 2. Basic algebraic structures. Modular arithmetic. 3. Orderings, properties. Hasse diagram. 4. Lattices. Distributive and complementary lattices. 5. Boolean algebras. Boolean calculus. Direct product of Boolean algebras, Stone representation theorem. 6. Boolean functions, Boolean polynomials, disjunctive and conjunctive normal form. Minimal form. 7. Directed and undirected graphs. Basic graph theory concepts. Graph homomorphisms. 8. Graph connectivity. Trees and spanning trees. Eulerian graphs. Directed graphs. Weak and strong connectivity. Acyclic graphs, condensation. 9. Matrix representation of a graph: adjacency, incidence and Laplace matrix. Basics of algebraic and spectral graph theory. 10. Number of spanning trees. Number of walks. Applications. 11. Weighted graphs. Gentle introduction to algorithms and computational complexity. 12. Applications: minimum spanning tree, distance and shortest paths, critical path, Chinese postman problem. 13. Introduction to further areas: planar graphs, Hamiltonian graphs, graph coloring, network flows, complex networks, coding, cryptography.
|
|
Learning activities and teaching methods
|
Collaborative instruction, Lecture
- Contact hours
- 52 hours per semester
- Preparation for formative assessments (2-20)
- 18 hours per semester
- Preparation for an examination (30-60)
- 58 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| to formulate basic concept of linear algebra and explain their basic properties |
| Skills |
|---|
| to apply basic methods of linear algebra |
| Competences |
|---|
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| to describe matrix representation of a graph and explain relations among properties of graphs and algebraic properties of relevant matrices |
| to explain algorithmic aspects of solving of some basic applicable graph problems |
| to express basic notions of the graph theory and explain their basic properties, including connections among them |
| to explain basic notions of the theory of relation structures: binary relation, equivalence (including a special case of arithmetics modulo 2), linear a partial orderings, Boolean algebra and Boolean functions and polynoms |
| Skills |
|---|
| to represent a graph structure by a matrix including understanding of relations between properties of graphs and algebraic properties of relevant matrices |
| to solve simple problems in arithmetic modulo k |
| to know the concept of equivalence and partition of a set into equivalence classes |
| to design algorithms for solving of basic graph problems, analyze their theoretical and algorithmical attributes, and use the designed algorithms on examples |
| to apply basics of of Boolean algebras including an expression of Bollean functions (polynomials) in canonical conjunctive and disjunctive normal forms |
| Competences |
|---|
| aktivně využívá získané znalosti a dovednosti při řešení praktických problémů |
| teaching methods |
|---|
| Knowledge |
|---|
| Practicum |
| Lecture |
| Skills |
|---|
| Lecture |
| Practicum |
| Competences |
|---|
| Lecture |
| Practicum |
| assessment methods |
|---|
| Knowledge |
|---|
| Combined exam |
| Test |
| Skills demonstration during practicum |
| Skills |
|---|
| Skills demonstration during practicum |
| Test |
| Combined exam |
| Competences |
|---|
| Test |
| Combined exam |
| Skills demonstration during practicum |
|
Recommended literature
|
-
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.
|