Course detail
Discrete Mathematics
FIT-IDMAcad. year: 2020/2021
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.
Supervisor
Department
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.
Recommended optional programme components
Not applicable.
Recommended or required reading
Hliněný, P., Úvod do informatiky. Elportál, Brno, 2010. (in Czech).
Hliněný, P., Úvod do informatiky. Elportál, Brno, 2010. (CS)
Kovár, M., Diskrétní matematika, FEKT VUT, Brno, 2013 (CS)
Kovár, M., Diskrétní matematika, FEKT VUT, Brno, 2013. (in Czech).
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.
Grossman P., Discrete mathematics for computing, Palgrave Macmillan, New York 2002.
Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992. (CS)
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).
Sochor, A., Klasická matematická logika, Karolinum, Praha 2001. (CS)
Planned learning activities and teaching methods
Not applicable.
Assesment methods and criteria linked to learning outcomes
- Evaluation of the five written tests (max 40 points).
Exam prerequisites:
The minimal total score of 15 points gained out of the five written tests.
Language of instruction
Czech, English
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; 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.
Type of course unit
Lecture
26 hours, optionally
Teacher / Lecturer
Syllabus
- 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 first-order 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. Hilbert-style 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.
Computer-assisted exercise
26 hours, compulsory
Teacher / Lecturer
Ing. Vítězslav Beran, Ph.D.
doc. Dr. Ing. Jan Černocký
RNDr. Petr Fuchs, Ph.D.
Ing. Vojtěch Havlena
prof. Ing. Adam Herout, Ph.D.
doc. RNDr. Dana Hliněná, Ph.D.
Mgr. Lukáš Holík, Ph.D.
Ing. Jiří Hynek, Ph.D.
Ing. Bohuslav Křena, Ph.D.
Ing. Zbyněk Křivka, Ph.D.
Ing. Ondřej Lengál, Ph.D.
Ing. Vojtěch Mrázek, Ph.D.
Mgr. Ing. Pavel Očenášek, Ph.D.
Bc. Juraj Síč
Ing. Aleš Smrčka, Ph.D.
Ing. Josef Strnadel, Ph.D.
doc. RNDr. Zdeněk Svoboda, CSc.
Ing. Ján Švec
Mgr. Gabriela Vážanová
prof. Dr. Ing. Pavel Zemčík
Syllabus
Examples at tutorials are chosen to suitably complement the lectures.
eLearning
eLearning: currently opened course