Skip to main content

Modulbeschreibung - Fundamentals of Mathematics for Computer Science
(Mathematische Grundlagen der Informatik)

Nummer
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
    Diese Seite teilen: