Course detail

Discrete Mathematics

FIT-IDMAcad. year: 2021/2022

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. Network flows.


Language of instruction

Czech

Number of ECTS credits

5

Mode of study

Not applicable.

Guarantor

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

Department

Department of Mathematics (UMAT)

Learning outcomes of the course unit

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 claims and their proofs.

Prerequisites

Secondary school mathematics.

Co-requisites

Not applicable.

Planned learning activities and teaching methods

Not applicable.

Assesment methods and criteria linked to learning outcomes

  • Evaluation of the five written tests (max 25 points).

Course curriculum

Not applicable.

Work placements

Not applicable.

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.

Specification of controlled education, way of implementation and compensation for absences

  • The knowledge of students is tested at exercises (max. 6 points); at five written tests for 5 points each, at evaluated home assignment with the defence for 5 points, and at the final exam for 64 points.
  • If a student can substantiate serious reasons for an absence from an exercise, (s)he can either attend the exercise with a different group (please inform the teacher about that). 
  • Passing boundary for ECTS assessment: 50 points.

Recommended optional programme components

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

Not applicable.

Recommended reading

Not applicable.

Classification of course in study plans

  • Programme IT-BC-3 Bachelor's

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

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

Type of course unit

 

Lecture

26 hod., optionally

Teacher / Lecturer

doc. RNDr. Dana Hliněná, Ph.D.
doc. Mgr. Lukáš Holík, Ph.D.
RNDr. Petr Fuchs, Ph.D.
Ing. Ondřej Lengál, Ph.D.

Syllabus

  1. The formal language of mathematics. A set intuitively. Basic set operations. Power set. Cardinality. Sets of numbers.  The principle of inclusion and exclusion.
  2. Binary relations and mappings. The composition of binary relations and mappings.
  3. Reflective, symmetric, and transitive closure. Equivalences and partitions.
  4. Partially ordered sets and lattices. Hasse diagrams. Mappings.
  5. Binary operations and their properties.
  6. General algebras and algebras with one operation. Groups as algebras with one operation. Congruences and morphisms.
  7. General algebras and algebras with two operations. Lattices as algebras with two operations. Boolean algebras.
  8.  Propositional logic. Syntax and Semantics. Satisfiability and validity. Logical equivalence and logical consequence. Ekvivalent formulae. Normal forms.
  9. Predicate logic. The language of first-order predicate logic. Syntax, terms, and formulae, free and bound variables. Interpretation.
  10. Predicate logic. Semantics, truth definition. Logical validity, logical consequence. Theories. Equivalent formulae. Normal forms.
  11. A formal system of logic. Hilbert-style axiomatic system for propositional and predicate logic. Provability, decidability, completeness, incompleteness.
  12. Basic concepts of graph theory.  Graph Isomorphism. Trees and their properties. Trails, tours, and Eulerian graphs.
  13. Finding the shortest path. Dijkstra's algorithm. Minimum spanning tree problem. Kruskal's and Jarnik's algorithms. Planar graphs.

Computer-assisted exercise

26 hod., compulsory

Teacher / Lecturer

Mgr. Juraj Síč
Ing. Dominik Harmim
Mgr. Gabriela Vážanová, Ph.D.
doc. Mgr. Lukáš Holík, Ph.D.
Ing. Vojtěch Havlena, Ph.D.
doc. RNDr. Dana Hliněná, Ph.D.
RNDr. Petr Fuchs, Ph.D.
Ing. Ondřej Lengál, Ph.D.

Syllabus

Examples at tutorials are chosen to suitably complement the lectures.