FIT-IDMAcad. year: 2018/2019
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.
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.
Secondary school mathematics.
Recommended optional programme components
Recommended or required reading
Planned learning activities and teaching methods
Assesment methods and criteria linked to learning outcomes
- Evaluation of the two home assignments solved in the groups (max 10 points).
- Evaluation of the two mid-term exams (max 30 points).
The minimal total score of 10 points gained out of the mid-term exams. Plagiarism and not allowed cooperation will cause that involved students are not classified and disciplinary action may be initiated.
Language of instruction
This course provides basic knowledge of mathematics neccessary 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
- Participation in lectures in this course is not controlled.
- The knowledge of students is tested at exercises; including two homework assignments worth for 5 points each, at two midterm exams for 15 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) or ask his/her teacher for an alternative assignment to compensate for the lost points from the exercise.
- Passing bounary for ECTS assessment: 50 points.
Type of course unit
26 hours, optionally
Teacher / Lecturer
- The formal language of mathematics. A set intuitively. Basic set
operations. Power set. Cardinality. Sets of numbers. Combinatoric
properties of sets. The principle of inclusion and exclusion.
- Binary relations and mappings. Composition of binary relations and
mappings. Reflective, symmetric, and transitive closure. Equivalences
and partitions. Partially ordered sets and lattices. Hasse diagrams.
- Sequences and recursive formulas.
- 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.
- Directed graphs, network flows, finding maximum flow, applications.
- Propositional logic, its syntax and semantics.
- Predicate logic, its syntax and semantics.
- Demonstration of usage and utility of propositional and predicate logic in proofs. Proof techniques and their illustrations.
- 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.
26 hours, compulsory
Teacher / Lecturer
Examples at tutorials are chosen to suitably complement the lectures.
eLearning: currently opened course