University of West Bohemia
Study programmes & Course catalogue
for academic year 2024/2025
University of West Bohemia
Česky
Search
FAQ

Course: Discrete Mathematics

« Back
Course title Discrete Mathematics
Course code KMA/DMA
Organizational form of instruction Lecture + Tutorial
Level of course Bachelor
Year of study 2
Semester Summer
Number of ECTS credits 4
Language of instruction Czech
Status of course Compulsory
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
Lecturer(s)
  • Š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.
  • Kabela Adam, RNDr. 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.


Study plans that include the course
Faculty Study plan (Version) Category of Branch/Specialization Recommended year of study Recommended semester
Faculty: Faculty of Education Study plan (Version): Information Technologies in Education (19) Category: Informatics courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Geography in Education (19) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Geography in Education (18) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Physics in Education (16) Category: Physics courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Information Technologies in Education (16) Category: Informatics courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Geography in Education (16) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Physical Education in Education (18) Category: Physical education and sport 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Studies in Mathematics (18) Category: Mathematics courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Geography in Education (17) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Chemistry in Education (16) Category: Chemistry courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Information Technologies in Education (15) Category: Informatics courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Chemistry in Education (18) Category: Chemistry courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Information Technologies in Education (18) Category: Informatics courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Music in Education (19) Category: Art and applied art 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Physics in Education (19) Category: Physics courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Biology in Education (15) Category: Biology courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Geography in Education (1) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Biology in Education (18) Category: Biology courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): English Language in Education (19) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Chemistry in Education (17) Category: Chemistry courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Physical Education in Education (17) Category: Physical education and sport 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Biology in Education (16) Category: Biology courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Geography in Education (15) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Chemistry in Education (19) Category: Chemistry courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Technology and Design in Education (18) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Physical Education in Education (19) Category: Physical education and sport 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Studies in Mathematics (19) Category: Mathematics courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Technology and Design in Education (17) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Technology and Design in Education (16) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Studies in Mathematics (17) Category: Mathematics courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Technology and Design in Education (19) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Biology in Education (17) Category: Biology courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Physics in Education (17) Category: Physics courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Physics in Education (15) Category: Physics courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Biology in Education (19) Category: Biology courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Information Technologies in Education (17) Category: Informatics courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Education Study plan (Version): Chemistry in Education (14) Category: Chemistry courses 2 Recommended year of study:2, Recommended semester: Summer
University of West Bohemia, date of update: 26.07.2024 23:53. Data created for academic year 2024/2025