Course details

Discrete Mathematics

IDM Acad. year 2020/2021 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.


Guarantor

Deputy Guarantor

Language of instruction

Czech

Completion

Credit+Examination (written)

Time span

26 hrs lectures, 26 hrs exercises

Assessment points

60 exam, 40 mid-term test

Department

Department of Mathematics (DMAT FEEC BUT)

Lecturer

Instructor

Beran Vítězslav, Ing., Ph.D. (DCGM FIT BUT)
Černocký Jan, doc. Dr. Ing. (DCGM FIT BUT)
Fuchs Petr, RNDr., Ph.D. (DMAT FEEC BUT)
Havlena Vojtěch, Ing. (DITS FIT BUT)
Herout Adam, prof. Ing., Ph.D. (DCGM FIT BUT)
Hliněná Dana, doc. RNDr., Ph.D. (DMAT FEEC BUT)
Holík Lukáš, Mgr., Ph.D. (DITS FIT BUT)
Hynek Jiří, Ing., Ph.D. (DIFS FIT BUT)
Křena Bohuslav, Ing., Ph.D. (DITS FIT BUT)
Křivka Zbyněk, Ing., Ph.D. (DIFS FIT BUT)
Lengál Ondřej, Ing., Ph.D. (DITS FIT BUT)
Mrázek Vojtěch, Ing., Ph.D. (DCSY FIT BUT)
Očenášek Pavel, Mgr. Ing., Ph.D. (DIFS FIT BUT)
Síč Juraj, Bc. (DITS FIT BUT)
Smrčka Aleš, Ing., Ph.D. (DITS FIT BUT)
Strnadel Josef, Ing., Ph.D. (DCSY FIT BUT)
Svoboda Zdeněk, RNDr., CSc. (DMAT FEEC BUT)
Švec Ján, Ing. (DCGM FIT BUT)
Vážanová Gabriela, Mgr. (DMAT FEEC BUT)
Zemčík Pavel, prof. Dr. Ing. (DCGM FIT BUT)

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 kwnowledge and skills

Secondary school mathematics.

Study literature

  • Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2007. (in Czech).
  • Matoušek J., Nešetřil J., Invitation to Discrete Mathematics, Oxford University Press, Oxford 2008.
  • Hliněný, P., Úvod do informatiky. Elportál, Brno, 2010. (in Czech).
  • Kovár, M., Diskrétní matematika, FEKT VUT, Brno, 2013. (in Czech).

Fundamental literature

  • Anderson I., A First Course in Discrete Mathematics, Springer-Verlag, 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. (in Slovak).
  • Kolman B., Busby R. C., Ross S. C., Discrete Mathematical Structures, Pearson Education, Hong-Kong 2001.
  • Klazar M., Kratochvíl J, Loebl M., Matoušek J. Thomas R., Valtr P., Topics in Discrete Mathematics, Springer-Verlag, Berlin 2006.
  • Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2007. (in Czech).
  • 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, Springer-Verlag, London 2006.
  • Sochor, A., Klasická matematická logika, Karolinum, Praha 2001. (in Czech).

Syllabus of lectures

  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.

Syllabus of numerical exercises

Examples at tutorials are chosen to suitably complement the lectures.

Progress assessment

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

Controlled instruction

  • The knowledge of students is tested at exercises; at five written tests for 8 points each, and at the final exam for 60 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 15 points gained out of  the five written tests.

Schedule

DayTypeWeeksRoomStartEndLect.grpGroupsInfo
Monexam2021-01-18 A218 D0206 D0207 D105 E104 E105 E112 08:0009:50 1BIA 1BIB 2BIA 2BIB 1. oprava
Monexam2021-01-18 G108 G202 08:0009:50 1BIA 1BIB opravny termin IDM
Monexam2021-01-18 A112 A113 A218 C228 D0206 D0207 D105 E104 E105 E112 G108 G202 L314 M103 M104 M105 N103 N104 N105 N203 N204 N205 O204 T10/1.36 T12/2.173 T8/010 T8/020 T8/030 T8/235 12:0013:50 1BIA 1BIB 2BIA 2BIB 1. oprava
Monexam2020-12-21 A112 A113 D0206 D0207 D105 E104 E105 E112 13:0014:50 1BIA 1BIB 2BIA 2BIB Předtermín
Tuelecturelectures D0206 D105 08:0009:50 1BIB 2BIA 2BIB xx Hliněná
Tuelecture2., 3., 4., 5., 6., 7., 8., 10., 11., 12., 13. of lectures D105v 08:0009:50YT, ZP; Lengál
Tueexam2021-01-12 A112 A113 A218 C228 D0206 D0207 D105 E104 E105 E112 G108 G202 L314 M103 M104 M105 N103 N104 N105 N203 N204 N205 O204 T10/1.36 T12/2.173 T8/010 T8/020 T8/030 12:0013:50 1BIA 1BIB 2BIA 2BIB řádná
Tuelecturelectures D0206 D105 13:0014:50 1BIA 2BIA 2BIB xx Hliněná
Tuelecture2., 3., 4., 5., 6., 7., 8., 10., 11., 12., 13. of lectures D105v 13:0014:50YT, ZP; Lengál
Tueexam2021-01-12 A112 A113 A218 C228 D0206 D0207 D105 E104 E105 E112 G108 G202 L314 M103 M104 M105 N103 N104 N105 N203 N204 N205 O204 14:0015:50 1BIA 1BIB 2BIA 2BIB řádná
Tueexerciselectures D0207 15:0016:50 1BIA 1BIB 2BIA 2BIB xx Holík
Tueexercise5., 6., 7. of lectures D0207v 15:0016:50YT, ZP, Hliněná
Tueexam2021-01-12 A218 C228 L314 M103 M104 M105 N103 N104 N105 N203 N204 N205 O204 16:0017:50 1BIA 1BIB 2BIA 2BIB řádná
Tueexerciselectures D0207 17:0018:50 1BIA 1BIB 2BIA 2BIB xx Lengál
Tueexam2021-01-12 A218 C228 G108 G202 L314 M103 M104 M105 N103 N104 N105 N203 N204 N205 O204 18:0019:50 1BIA 1BIB 2BIA 2BIB řádná
Tueexerciselectures A113 19:0020:50 1BIA 1BIB 2BIA 2BIB xx Lengál
Wedexerciselectures T8/503 07:0008:50 1BIA 1BIB 2BIA 2BIB xx Vážanová
Wedexerciselectures T8/030 09:0010:50 1BIA 1BIB 2BIA 2BIB xx Vážanová
Wedexercise2020-11-11 A113v 14:0015:50YT, ZP, bez projekce; Hliněná
Wedexerciselectures D0207 18:0019:50 1BIA 1BIB 2BIA 2BIB xx Holík
Wedexerciselectures G202 18:0019:50 1BIA 1BIB 2BIA 2BIB xx Havlena
Wedlecture2020-11-18 D105v 18:0019:50YT, ZP
Thuexam2021-02-04 A112 A113 D0206 D0207 D105 E112 G108 G202 L314 M103 M104 M105 N103 N104 N105 N203 N204 N205 O204 T8/010 T8/020 T8/030 09:0010:50 1BIA 1BIB 2BIA 2BIB 2. oprava
Thuotherlectures A218 09:0010:50konzultace Lengál
Thuexercise2020-10-29 A113v 10:0011:50YT, ZP, Hliněná
Thuexerciselectures T8/522 11:0012:50 1BIA 1BIB 2BIA 2BIB xx Fuchs
Thuexerciselectures A113 12:0013:50 1BIA 1BIB 2BIA 2BIB xx Síč
Thuexerciselectures T8/522 13:0014:50 1BIA 1BIB 2BIA 2BIB xx Fuchs
Thuexerciselectures D0207 16:0017:50 1BIA 1BIB 2BIA 2BIB xx Síč
Thuexerciselectures A113 18:0019:50 1BIA 1BIB 2BIA 2BIB xx Síč
Friexerciselectures T8/322 07:0008:50 1BIA 1BIB 2BIA 2BIB xx Vážanová
Friexerciselectures A113 08:0009:50 1BIA 1BIB 2BIA 2BIB xx Hliněná
Friexercise2., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13. of lectures A113v 08:0009:50YT, ZP, bez projekce
Friexerciselectures T8/322 09:0010:50 1BIA 1BIB 2BIA 2BIB xx Vážanová
Friexerciselectures A113 10:0011:50 1BIA 1BIB 2BIA 2BIB xx Hliněná
Friexercise2., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13. of lectures A113v 10:0011:50YT, ZP, bez projekce

Course inclusion in study plans

  • Programme BIT, 1st year of study, Compulsory
  • Programme IT-BC-3, field BIT, 1st year of study, Compulsory
Back to top