Theoretical Computer Science II (ACS II) - Overview

Lecturer: Prof. Dr. Bernhard Nebel, Prof. Dr. Christian Becker-Asano


Lectures: Monday, 12:15-14:00 and Thursday 12:15-13:00
Exercise sessions: Thursday, 13:15-14:00


Lectures: Building 101, Room 01-009/13
Exercise sessions: Building 101, Room 01-009/13


Lectures are held in English, and the course material and exercise sheets are in English. Students may ask questions and submit exercise sheets in German or English.

Credit Points

6 ECTS points

Aims of the lecture

The participants should get a foundational knowledge of the theoretical aspects of computer science.

Contents of the lecture

This course will address theoretical aspects of computer science. It comprises the fundamental mathematical properties of computer hard and software. We will see what can be computed, and what cannot, and if it can be computed, how hard (efficient) it is to compute it. More specifically, the following topics will be included:
  • Automata
  • Formal languages
  • Formal grammars
  • Turing machines
  • Decidability
  • Complexity theory
  • Logic


The course is aimed at students of Applied Computer science in their 1st semester. Bachelor and master students of Computer Science cannot receive ECTS points in this course. Students of other degree programs can in certain cases participate upon prior agreement.


There will be a written exam after the lecture.