Course detail

Discrete Mathematics

FIT-IDMAcad. year: 2023/2024

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.

Language of instruction

Czech

Number of ECTS credits

4

Mode of study

Not applicable.

Guarantor

doc. RNDr. Dana Hliněná, Ph.D.

Department

Department of Mathematics (UMAT)

Entry knowledge

Secondary school mathematics.

Rules for evaluation and completion of the course

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.

Aims

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.

Study aids

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

Not applicable.

Recommended reading

Not applicable.

Elearning

eLearning: currently opened course

Classification of course in study plans

  • Programme BIT Bachelor's 1 year of study, winter semester, compulsory
  • Programme BIT Bachelor's 1 year of study, winter semester, compulsory

  • Programme IT-BC-3 Bachelor's

    branch BIT , 1 year of study, winter semester, compulsory

Type of course unit

 

Lecture

26 hod., compulsory

Teacher / Lecturer

doc. RNDr. Dana Hliněná, Ph.D.

Syllabus

  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.

Computer-assisted exercise

26 hod., compulsory

Teacher / Lecturer

RNDr. Petr Fuchs, Ph.D.
doc. RNDr. Dana Hliněná, Ph.D.
Mgr. Martin Tůma, Ph.D.

Syllabus

Examples at tutorials are chosen to complement suitably the lectures.

Elearning

eLearning: currently opened course