BIE-ZDM – Elements of Discrete Mathematics
Students get both a mathematical sound background, but also practical calculation skills in the area of combinatorics, value estimation and formula approximation, and tools for solving recurrent equations.
- Sets, cardinality, countable sets, power set of a finite set and its cardinality.
- Power set of the set of natural numbers - uncountable set.
- Exclusion and inclusion, its use to determine cardinality.
- "Pigeon-hole principle", number of structures, i.e., number of maps, relations, trees (on finite structures).
- Function estimates (factorial, binomial coefficients, ...).
- Relation, equivalence relation (examples of equivalence of connected/strongly connected components).
- Relation matrix, relational databases.
- Mathematical induction as a tool for determining the number of finite objects.
- Mathematical induction as a tool for proving algorithm correctness.
- Mathematical induction as a tool for solving recursive problems.
- Structural induction.
- Runtime complexity of recursive algorithms - solving recursive equations with constant coefficients, homogeneous equations.
- Solving non-homogeneous recursive equations with constant coefficients.
- Cardinality calculations.
- Countability, uncountability.
- Inclusion and exclusion principle.
- Numbers of structures over finite sets.
- Asymptotic function behavior.
- Relations and directed graphs.
- Basic proofs by induction.
- Application of proofs by induction in combinatorics.
- Application of proofs by induction in programming.
- Induction and recursive algorithms.
- Uses of induction in formal language theory.
- Runtime complexity calculations.
- Solving linear recurrent equations.