Course details
Discrete Mathematics
IDM Acad. year 2021/2022 Winter semester 5 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. Network flows.
News

Guarantor
Deputy Guarantor
Language of instruction
Completion
Time span
Assessment points
Department
Lecturer
Hliněná Dana, doc. RNDr., Ph.D. (UMAT)
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
Lengál Ondřej, Ing., Ph.D. (UITS)
Instructor
Harmim Dominik, Ing. (UITS)
Havlena Vojtěch, Ing., Ph.D. (UITS)
Hliněná Dana, doc. RNDr., Ph.D. (UMAT)
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
Lengál Ondřej, Ing., Ph.D. (UITS)
Síč Juraj, Mgr. (UITS)
Vážanová Gabriela, Mgr. (UMAT)
Course Web Pages
Aktuální informace k předmětu naleznete zde: web stránka
Streaming přednášek: zde
Subject specific learning outcomes and competences
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.
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.
Why is the course taught
Mathematics stood at the birth of computer science and since then has always been in the core of almost all of its progress.
Discrete mathematics aims at understanding the aspects of the real world that are the most fundamental from the point of view of computer science. It studies such concepts as a set (e.g. a collection of data, resources, agents), relations and graphs (e.g. relationships among data or description of a communication), and operations over elements of a set (especially basic arithmetical operations and their generalization).
The mathematical logic then gives means of expressing ideas and reasoning clearly and correctly and is, moreover, the foundation of "thinking of computers".
Generally speaking, discrete mathematics teaches the art of abstraction  how to apprehend the important aspects of a problem and work with them. It provides a common language for talking about those aspects precisely and effectively. Besides communication of ideas, it helps to structure thought into exactly defined notions and relationships, which is necessary when designing systems so large and complex as today's software and hardware.
For example, discrete math gives the basic tools for expressing what a program does; what its data structures represent; how the amount of needed resources depends on the size of the input; how to specify and argue that a program does what it should do. Similarly essential uses can be found everywhere in computer science. One could say that a programmer without mathematics is similar to a piano player who cannot read notes: if he is talented, he can still succeed, but his options are limited, especially when it comes to solving complex problems.
In order to teach mathematical thinking to students, we emphasize practising mathematics by using it to solve problems  in the same way as programming can be only learnt through programming, mathematics also can be learnt only by doing it.
Prerequisite knowledge and skills
Secondary school mathematics.
Study literature
 Hliněný, P., Úvod do informatiky. Elportál, Brno, 2010.
 Kovár, M., Diskrétní matematika, FEKT VUT, Brno, 2013
 Anderson I., A First Course in Discrete Mathematics, SpringerVerlag, London 2001.
 Grimaldi R. P., Discrete and Combinatorial Mathematics, Pearson Addison Valley, Boston 2004.
 Grossman P., Discrete mathematics for computing, Palgrave Macmillan, New York 2002.
 Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992.
 Kolman B., Busby R. C., Ross S. C., Discrete Mathematical Structures, Pearson Education, HongKong 2001.
 Klazar M., Kratochvíl J, Loebl M., Matoušek J. Thomas R., Valtr P., Topics in Discrete Mathematics, SpringerVerlag, Berlin 2006.
 Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2007.
 Matoušek J., Nešetřil J., Invitation to Discrete Mathematics, Oxford University Press, Oxford 2008.
 O'Donnell, J., Hall C., Page R., Discrete Mathematics Using a Computer, SpringerVerlag, London 2006.
 Sochor, A., Klasická matematická logika, Karolinum, Praha 2001.
Syllabus of lectures
 The formal language of mathematics. A set intuitively. Basic set operations. Power set. Cardinality. Sets of numbers. The principle of inclusion and exclusion.
 Binary relations and mappings. The composition of binary relations and mappings.
 Reflective, symmetric, and transitive closure. Equivalences and partitions.
 Partially ordered sets and lattices. Hasse diagrams. Mappings.
 Binary operations and their properties.
 General algebras and algebras with one operation. Groups as algebras with one operation. Congruences and morphisms.
 General algebras and algebras with two operations. Lattices as algebras with two operations. Boolean algebras.
 Propositional logic. Syntax and Semantics. Satisfiability and validity. Logical equivalence and logical consequence. Ekvivalent formulae. Normal forms.
 Predicate logic. The language of firstorder predicate logic. Syntax, terms, and formulae, free and bound variables. Interpretation.
 Predicate logic. Semantics, truth definition. Logical validity, logical consequence. Theories. Equivalent formulae. Normal forms.
 A formal system of logic. Hilbertstyle axiomatic system for propositional and predicate logic. Provability, decidability, completeness, incompleteness.
 Basic concepts of graph theory. Graph Isomorphism. Trees and their properties. Trails, tours, and Eulerian graphs.
 Finding the shortest path. Dijkstra's algorithm. Minimum spanning tree problem. Kruskal's and Jarnik's algorithms. Planar graphs.
Syllabus of numerical exercises
Examples at tutorials are chosen to suitably complement the lectures.
Progress assessment
 Evaluation of the five written tests (max 25 points).
Controlled instruction
 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.
Exam prerequisites
The minimal total score of 12 points gained out of the five written tests.
Schedule
Day  Type  Weeks  Room  Start  End  Lect.grp  Groups  Info 

Mon  exam  20211220  A113 E104 E105 E112 G202  10:00  11:50  1BIA 1BIB 2BIA 2BIB  předtermín  
Mon  exam  20220117  D105 E112 T10/1.36 T12/2.173 T8/010 T8/020 T8/030  12:00  13:50  1BIA 1BIB 2BIA 2BIB  1. oprava  
Tue  lecture  lectures  D0206 D105  08:00  09:50  1BIB 2BIA 2BIB  xx 30  49  Hliněná, Holík, Lengál 
Tue  lecture  lectures  D0206 D105  12:00  13:50  1BIA 2BIA 2BIB  xx 10  29  Hliněná, Holík, Lengál 
Tue  exercise  lectures  D0207  14:00  15:50  1BIA 1BIB 2BIA 2BIB  xx  Harmim 
Tue  exercise  lectures  D0207  16:00  17:50  1BIA 1BIB 2BIA 2BIB  xx  Holík 
Wed  exercise  lectures  T8/T 5.03  07:00  08:50  1BIA 1BIB 2BIA 2BIB  xx  Vážanová 
Wed  exercise  lectures  G202  09:00  10:50  1BIA 1BIB 2BIA 2BIB  xx  Síč 
Wed  exercise  lectures  T8/T 3.22  09:00  10:50  1BIA 1BIB 2BIA 2BIB  xx  Vážanová 
Wed  exercise  lectures  G202  11:00  12:50  1BIA 1BIB 2BIA 2BIB  xx  Síč 
Wed  exercise  lectures  T8/T 3.22  11:00  12:50  1BIA 1BIB 2BIA 2BIB  xx  Vážanová 
Wed  exercise  lectures  A113  18:00  19:50  1BIA 1BIB 2BIA 2BIB  xx  Harmim 
Thu  exercise  lectures  G202  08:00  09:50  1BIA 1BIB 2BIA 2BIB  xx  Lengál 
Thu  exam  20220203  D105  09:00  10:50  1BIA 1BIB 2BIA 2BIB  2. oprava  
Thu  exam  20220106  D0206 D105 E112 T10/1.36 T12/2.173 T12/SF1.141 T8/010 T8/020 T8/030  10:00  12:50  1BIA 1BIB 2BIA 2BIB  řádná  
Thu  exercise  lectures  T8/T 3.22  11:00  12:50  1BIA 1BIB 2BIA 2BIB  xx  Fuchs 
Thu  exercise  lectures  A113  12:00  13:50  1BIA 1BIB 2BIA 2BIB  xx  Havlena 
Thu  exercise  lectures  T8/T 3.22  13:00  14:50  1BIA 1BIB 2BIA 2BIB  xx  Fuchs 
Fri  exercise  lectures  T8/T 3.22  07:00  08:50  1BIA 1BIB 2BIA 2BIB  xx  Vážanová 
Fri  exercise  lectures  A113  08:00  09:50  1BIA 1BIB 2BIA 2BIB  xx  Hliněná 
Fri  exercise  lectures  T8/T 3.22  09:00  10:50  1BIA 1BIB 2BIA 2BIB  xx  Vážanová 
Fri  exercise  lectures  A113  10:00  11:50  1BIA 1BIB 2BIA 2BIB  xx  Hliněná 
Fri  exercise  lectures  G202  13:00  14:50  1BIA 1BIB 2BIA 2BIB  xx  Lengál 
Fri  exercise  lectures  G202  15:00  16:50  1BIA 1BIB 2BIA 2BIB  xx  Síč 
Fri  exercise  20211015  D0206 D0207 D105  17:00  18:50  1BIA 1BIB 2BIA 2BIB  
Fri  exercise  20211112  D0206 D0207 D105  17:00  18:50  1BIA 1BIB 2BIA 2BIB  
Fri  exercise  20211210  D105  17:00  18:50  1BIA 1BIB 2BIA 2BIB  Demo IDM  
Fri  exercise  20211217  D105  17:00  18:50  1BIA 1BIB 2BIA 2BIB  Demo IDM  
Fri  lecture  20211105  D0206 D0207 D105  17:00  18:50  1BIA 1BIB 2BIA 2BIB 
Course inclusion in study plans