Course details

# Discrete Mathematics

IDM Acad. year 2023/2024 Winter semester 4 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. Directed graphs.

Guarantor

Course coordinator

Language of instruction

Completion

Time span

- 26 hrs lectures
- 26 hrs exercises

Assessment points

- 80 pts final exam
- 20 pts numeric exercises

Department

Lecturer

Instructor

Hliněná Dana, doc. RNDr., Ph.D. (UMAT)

Tůma Martin, Mgr., Ph.D. (UMAT)

Course Web Pages

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

Why is the course taught

Mathematics stood at the birth of computer science and since then it 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.

Syllabus of lectures

- The formal language of mathematics. Basic formalisms - statements, proofs, propositional and predicate logic.
- Intuitive set concepts. Basic set operations. Cardinality. Sets of numbers. The principle of inclusion and exclusion.
- Proof techniques.
- Binary relations, their properties and composition.
- Reflective, symmetric, and transitive closure. Equivalences and partitions.
- Partially ordered sets, lattices. Hasse diagrams. Mappings.
- Basic concepts of graph theory. Graph Isomorphism, trees, trails, tours, and Eulerian graphs.
- Finding the shortest path, Dijkstra's algorithm. Minimum spanning tree problem. Kruskal's and Jarnik's algorithms. Planar graphs.
- Directed graphs.
- Binary operations and their properties.
- Algebras with one operation, groups.
- Congruences and morphisms.
- Algebras with two operations, lattices as algebras. Boolean algebras.

Syllabus of numerical exercises

Examples at tutorials are chosen to complement suitably the lectures.

Progress assessment

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.

Exam prerequisites

The condition for receiving the credit is obtaining at least 8 points from the tests during the semester and active work at classes.

Course inclusion in study plans

- Programme BIT, 1st year of study, Compulsory
- Programme BIT (in English), 1st year of study, Compulsory
- Programme IT-BC-3, field BIT, 1st year of study, Compulsory