Discrete Mathematics

• 26 hrs lectures
• 26 hrs exercises

• 60 pts final exam (written part)
• 40 pts mid-term test (written part)

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.

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.

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.

Secondary school mathematics.

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.

Examples at tutorials are chosen to suitably complement the lectures.

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

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

The minimal total score of 15 points gained out of  the five written tests.