Formale Grundlagen der Informatik (HWS 2015)

The basic goal of computer sciences is to solve complex problems from economics, science and society. In general, it is a multi-stage process consisting of the following steps:

  • formal specification of the problem
  • designing a suitable algorithm
  • implementing the algorithm using a higher programming language
  • running the program (i.e., compilation into a sequence of machine code instructions, which are then executed by a respective processor)

In this course you will learn to reconstruct these steps for an easy formal model to get a basic idea of the fundamentals of informatics, e.g., computation problem, algorithm, program, circuit, and execution of maschine code instructions by a processor. Therefore, you need to know a formally correct and easy way to specify such concepts, which is provided by the language of higher mathematics.

We start by introducing the required mathematical basics such as sets, relations, maps, graphs and boolean functions. Subsequently, the following topics will be treated in further detail:

  • introduction to propositional logic and realisation of boolean functions using logic circuits
  • finite automata and their realisation
  • turing machines as an easy maschine model
  • an idea of limitations w.r.t. computability