| Number |
mgli
|
| ECTS |
3.0 |
| Level |
basic |
| Overview |
This course introduces the students to the fundamental mathematical notions relevant in computer science and shows how to model some practical problems with these tools. Last but not least, this course provides the mathematical basics for more advanced courses.
Sets and operations on sets
Relations, functions and graphs
- Equivalence and order relations
- Functions and their properties
- Properties of graphs
- Model building with graphs
Logic:
- Propositional logic
- Existential and universal quantifiers
Induction und recursion:
- The concept of mathematical induction
- Proof by induction
- Recursion relations up to degree 2
- Applications
Languages, grammars und automata:
- Grammars
- Chomski hierarchy
- Finite automata
- Finite automata and regular languages
(The order and emphasis of the topics are left to the lecturers.)
|
| Learning objectives |
Sets and Operations on Sets:
Students:
- know what a set, an element and a subset is and are able to apply the most important operations on sets (intersection, union, difference, power set, cartesian product).
- Relations, Functions and Graphs:
Students:
- understand what a relation is and are able to decide if a relation is reflexive, symmetric, anti-symmetric or transitive. They are able to construct the composition of two relations;
- understand equivalence relations and order relations as well as the connection between equivalence relations and partitions;
are able to identify injective, surjective and bijective functions and are able to construct inverse functions, if this is possible;
know about the most important properties of directed and undirected graphs and are able to model some practical problems with graphs.
- Logic:
Students:
- know what a proposition is and are able to assign truth values to any formula;
- know about universal and existential quantifiers and can assign a truth value to a predicate.
- Induction and Recursion:
Students:
- understand the concept of mathematical induction and are able to prove some simple statements by induction;
- are able to solve linear homogeneous as well as some simple inhomogeneous recursion relations (up to degree 2), especially recursion relations which occur in the analysis of algorithms.
- Languages and Grammars:
Students:
- understand the notion of grammar and how to describe formal languages with the help of grammars;
- can classify grammars and languages according to the Chomsky hierarchy;
- know what a DFA is, the connection with the regular languages and are able to construct a DFA for simple regular languages.
|
| Prevvious knowledge |
- English level B2 (e.g. passed module ten1)
|
| Exam format |
Continuous assessment grade with final written exam |
