Course: Discrete Mathematics

« Back
Course title Discrete Mathematics
Course code KMA/DMA-A
Organizational form of instruction Lecture + Tutorial
Level of course Bachelor
Year of study 1
Semester Summer
Number of ECTS credits 5
Language of instruction English
Status of course Compulsory-optional, Optional
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
Course availability The course is available to visiting students
Lecturer(s)
  • Čada Roman, Doc. Ing. Ph.D.
  • Tomiczková Světlana, RNDr. Ph.D.
Course content
1. basic concepts of set theory, binary relations 2. mappings (functions), basic algebraic structures 3. tolerance relation and equivalence, congruence relation 4. ordering relation, partial and total ordering, Hasse diagram 5. supremum and infimum, lattice, distributive lattice 6. complemented lattice, Boolean algebra, Boolean calculus, Stone's representation theorem for Boolean algebras 7. direct product of Boolean algebras, Boolean functions, Boolean polynomials, disjunctive and conjunctive normal form 8. graph, oriented and non-oriented graph, graph homomorphisms and related concepts, paths in graphs, degree of a vertex, Eulerian graph, trees 9. oriented graphs, weak and strong connectivity, acyclic graphs, condensation graph 10. incidence matrix of an oriented graph, Laplacian matrix, counting spanning trees, incidence matrix of a non-oriented graph 11. cycle and cut space of a graph 12. adjacency matrix, counting walks 13. labeled graphs, distance in a graph, Dijkstra's algorithm

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
professional 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.


Study plans that include the course
Faculty Study plan (Version) Branch of study Category Recommended year of study Recommended semester
Faculty of Applied Sciences Mathematics for Business Studies (2011) Mathematics courses 1 Summer
Faculty of Applied Sciences Mathematics and Management (2011) Mathematics courses 1 Summer
Faculty of Applied Sciences General Mathematics (2012) Mathematics courses 1 Summer
Faculty of Applied Sciences General Mathematics (2012) Mathematics courses 1 Summer
Faculty of Applied Sciences Mathematics for Science (2012) Mathematics courses 1 Summer