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

Hliněná Dana, doc. RNDr., Ph.D. (UMAT)

Course coordinator

Fuchs Petr, RNDr., Ph.D. (UMAT)

Language of instruction

Czech, English

Completion

Credit+Examination (written)

Time span

  • 26 hrs lectures
  • 26 hrs exercises

Assessment points

  • 80 pts final exam
  • 20 pts numeric exercises

Department

Department of Mathematics (UMAT)

Lecturer

Hliněná Dana, doc. RNDr., Ph.D. (UMAT)

Instructor

Fuchs Petr, RNDr., Ph.D. (UMAT)
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

web pages of the guarantor

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

  1. The formal language of mathematics. Basic formalisms - statements, proofs, propositional and predicate logic.
  2. Intuitive set concepts. Basic set operations. Cardinality. Sets of numbers. The principle of inclusion and exclusion.
  3. Proof techniques.
  4. Binary relations, their properties and composition.
  5. Reflective, symmetric, and transitive closure. Equivalences and partitions.
  6. Partially ordered sets, lattices. Hasse diagrams. Mappings.
  7. Basic concepts of graph theory. Graph Isomorphism, trees, trails, tours, and Eulerian graphs.
  8. Finding the shortest path, Dijkstra's algorithm. Minimum spanning tree problem. Kruskal's and Jarnik's algorithms. Planar graphs.
  9. Directed graphs.
  10. Binary operations and their properties.
  11. Algebras with one operation, groups.
  12. Congruences and morphisms.
  13. 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

DayTypeWeeksRoomStartEndCapacityLect.grpGroupsInfo
Mon exam 2024-12-16 T12/SF 1.141 T8/T 0.10 T8/T 0.20 T8/T 0.30 09:0011:00 předtermín
Mon exercise 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures A112 09:0010:5064 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:0016:5056 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:0018:5056 1BIA 1BIB 2BIA 2BIB xx Tůma
Tue lecture lectures D0206 D105 08:0009:50470 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:0010:5064 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:0012:5064 1BIA 1BIB 2BIA 2BIB xx Tůma
Tue lecture lectures D0206 D105 12:0013:50470 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:0014:5064 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:0010:5056 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:0012:5056 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:0015:5064 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:0017:5067 1BIA 1BIB 2BIA 2BIB xx Tůma
Wed exercise *) 2024-09-18 T8/T 3.02 17:0018:500 1BIA 1BIB 2BIA 2BIB xx Fuchs
Thu exercise 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures A113 10:0011:5064 1BIA 1BIB 2BIA 2BIB xx Hliněná
Thu exercise *) 2024-09-19 A113 14:0015:500 1BIA 1BIB 2BIA 2BIB xx Hliněná
Fri exam 2025-01-31 Aula profesora Braunera Aula profesora Kalendovského D0207 E104 E105 E112 T12/SF 1.141 T12/SF 2.162 T8/T 0.10 T8/T 0.20 T8/T 0.30 10:3012:30 3. termín
Fri exercise 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures A112 12:0013:5064 1BIA 1BIB 2BIA 2BIB xx Fuchs
Fri exam 2025-01-03 A112 A113 Aula profesora Braunera Aula profesora Kalendovského D0207 E104 E105 E112 G202 T12/SF 1.141 T12/SF 2.162 T8/T 0.10 T8/T 0.20 T8/T 0.30 13:3015:30 1. termín
Fri exam 2025-01-17 Aula profesora Braunera Aula profesora Kalendovského D0206 D0207 D105 T12/SF 1.141 T12/SF 2.162 T8/T 0.10 T8/T 0.20 T8/T 0.30 13:3015:30 2. termín
Fri exercise 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12., 13. of lectures A112 14:0015:5064 1BIA 1BIB 2BIA 2BIB xx Fuchs
It is not possible to register this class in Studis. (Some exercises may be opened later if needed, but this is not guaranteed.)

Course inclusion in study plans

  • Programme BIT, 1st year of study, Compulsory
  • Programme BIT (in English), 1st year of study, Compulsory
Back to top