Course details
Discrete Mathematics
IDM Acad. year 2024/2025 Winter semester 4 credits
Sets, relations and mappings. Equivalences and partitions. Posets. Structures with one and two operations. Lattices and Boolean algebras. Propositional and predicate calculus. Elementary notions of graph theory. Connectedness. Subgraphs and morphisms of graphs. Planarity. Trees and their properties. Basic graph algorithms. Directed graphs.
Guarantor
Course coordinator
Language of instruction
Completion
Time span
- 26 hrs lectures
- 26 hrs exercises
Assessment points
- 80 pts final exam
- 20 pts numeric exercises
Department
Lecturer
Instructor
Hliněná Dana, doc. RNDr., Ph.D. (UMAT)
Tůma Martin, Mgr., Ph.D. (UMAT)
Vážanová Gabriela, Mgr., Ph.D. (UMAT)
Course Web Pages
Learning objectives
This course provides basic knowledge of mathematics necessary for a number of following courses. The students will learn elementary knowledge of algebra and discrete mathematics with an emphasis on mathematical structures that are needed for later applications in computer science. The students will acquire basic knowledge of discrete mathematics and the ability to understand the logical structure of a mathematical text. They will be able to explain mathematical structures and to formulate their own mathematical propositions and their proofs.
Prerequisite knowledge and skills
Secondary school mathematics.
Syllabus of lectures
- The formal language of mathematics. Basic formalisms - statements, proofs, propositional and predicate logic.
- Intuitive set concepts. Basic set operations. Cardinality. Sets of numbers. The principle of inclusion and exclusion.
- Proof techniques.
- Binary relations, their properties and composition.
- Reflective, symmetric, and transitive closure. Equivalences and partitions.
- Partially ordered sets, lattices. Hasse diagrams. Mappings.
- Basic concepts of graph theory. Graph Isomorphism, trees, trails, tours, and Eulerian graphs.
- Finding the shortest path, Dijkstra's algorithm. Minimum spanning tree problem. Kruskal's and Jarnik's algorithms. Planar graphs.
- Directed graphs.
- Binary operations and their properties.
- Algebras with one operation, groups.
- Congruences and morphisms.
- Algebras with two operations, lattices as algebras. Boolean algebras.
Syllabus of numerical exercises
Problems discussed at numerical classes are chosen so as to complement suitably the lectures.
Progress assessment
Written tests during the semester (maximum 20 points). Classes are compulsory. Presence at lectures will not be controlled, absence at numerical classes has to be excused.
Schedule
Day | Type | Weeks | Room | Start | End | Capacity | Lect.grp | Groups | Info |
---|---|---|---|---|---|---|---|---|---|
Mon | exercise | 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures | A112 | 09:00 | 10:50 | 64 | 1BIA 1BIB 2BIA 2BIB | xx | Tůma |
Mon | exercise | 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures | T8/T 3.02 | 15:00 | 16:50 | 56 | 1BIA 1BIB 2BIA 2BIB | xx | Tůma |
Mon | exercise | 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures | T8/T 3.02 | 17:00 | 18:50 | 56 | 1BIA 1BIB 2BIA 2BIB | xx | Tůma |
Tue | lecture | lectures | D0206 D105 | 08:00 | 09:50 | 470 | 1BIB 2BIA 2BIB | 30 - 49 xx | Hliněná |
Tue | exercise | 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures | A112 | 09:00 | 10:50 | 64 | 1BIA 1BIB 2BIA 2BIB | xx | Tůma |
Tue | exercise | 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures | A112 | 11:00 | 12:50 | 64 | 1BIA 1BIB 2BIA 2BIB | xx | Tůma |
Tue | lecture | lectures | D0206 D105 | 12:00 | 13:50 | 470 | 1BIA 2BIA 2BIB | 10 - 29 xx | Hliněná |
Tue | exercise | 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures | A112 | 13:00 | 14:50 | 64 | 1BIA 1BIB 2BIA 2BIB | xx | Tůma |
Wed | exercise | 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures | T8/T 3.02 | 09:00 | 10:50 | 56 | 1BIA 1BIB 2BIA 2BIB | xx | Vážanová |
Wed | exercise | 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures | T8/T 3.02 | 11:00 | 12:50 | 56 | 1BIA 1BIB 2BIA 2BIB | xx | Vážanová |
Wed | exercise | 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures | D0207 | 14:00 | 15:50 | 66 | 1BIA 1BIB 2BIA 2BIB | xx | Hliněná |
Wed | exercise | 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures | D0207 | 16:00 | 17:50 | 66 | 1BIA 1BIB 2BIA 2BIB | xx | Tůma |
Wed | exercise *) | 2024-09-18 | T8/T 3.02 | 17:00 | 18:50 | 0 | 1BIA 1BIB 2BIA 2BIB | xx | Fuchs |
Thu | exercise | 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures | A113 | 10:00 | 11:50 | 64 | 1BIA 1BIB 2BIA 2BIB | xx | Hliněná |
Thu | exercise *) | 2024-09-19 | A113 | 14:00 | 15:50 | 0 | 1BIA 1BIB 2BIA 2BIB | xx | Hliněná |
Fri | exercise | 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures | A112 | 12:00 | 13:50 | 64 | 1BIA 1BIB 2BIA 2BIB | xx | Fuchs |
Fri | exercise | 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures | A112 | 14:00 | 15:50 | 64 | 1BIA 1BIB 2BIA 2BIB | xx | Fuchs |
Course inclusion in study plans
- Programme BIT, 1st year of study, Compulsory
- Programme BIT (in English), 1st year of study, Compulsory