Course detail
Discrete Mathematics
FIT-IDMAcad. year: 2019/2020
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.
Language of instruction
Number of ECTS credits
Mode of study
Guarantor
Department
Learning outcomes of the course unit
Prerequisites
Co-requisites
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).
Exam prerequisites:
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.
Course curriculum
Work placements
Aims
Specification of controlled education, way of implementation and compensation for absences
- 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).
- Passing boundary for ECTS assessment: 50 points.
Recommended optional programme components
Prerequisites and corequisites
Basic literature
Recommended reading
Classification of course in study plans
Type of course unit
Lecture
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
Teacher / Lecturer
Syllabus