|
Lecturer(s)
|
-
Marek Josef, doc. Ing. Ph.D.
|
|
Course content
|
1. Combinatorics. Advanced combinatorics. 2. Difference equations. Discrete dynamical systems. 3. Basic algebraic structures. Modular counting. Latin squares. 4. Detecting primes. Code theory and cryptography. 5. Block designs. Steiner triple systems. 6. Orderings. Lattices. Boolean algebra. Boolean functions. Minimisation. 7. Basic concepts of graph theory. Graph connectivity. Minimum spanning tree. Eulerian graphs. 8. Planar graphs. Graphs on surfaces. 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. Dynamic programming. 11. Critical path. Cycle and cut spaces. 12. Hamiltonian graphs. Graph colouring. Extremal graph theory. Basics of Ramsey theory. 13. Graph problems as optimisation tasks. Computational complexity.
|
|
Learning activities and teaching methods
|
Interactive lecture, Lecture, Practicum
- Contact hours
- 52 hours per semester
- Preparation for formative assessments (2-20)
- 30 hours per semester
- Preparation for an examination (30-60)
- 56 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| An active knowledge of linear algebra in a range of the course KMA/LA-A or KMA/LA-A and of combinatorics at high school level is assumed. |
| learning outcomes |
|---|
| A student will be able to: - solve basic problems of combinatorics, - use actively the concept of a relation and a function, - apply basic facts of group theory, - solve linear congruence equations, - identify partial ordering relation, - define lattices and Boolean algebras, - deal with Boolean functions, - use actively basic concepts of graph theory, - describe a graph with help of matrices and use them to determine properties of the graph, - apply linear algebra in graph theory, - solve critical path problem. |
| teaching methods |
|---|
| Lecture |
| Interactive lecture |
| Practicum |
| assessment methods |
|---|
| Combined exam |
| Test |
| Skills demonstration during practicum |
|
Recommended literature
|
-
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.
|