Internal Preview! The data shown below is not valid for students! Please refer to the official Module Descriptions at the Examination Office.
Introduction to Theoretical Computer Science

General

study semester
3
standard study semester
6
cycle
every winter semester
duration
1 semester
SWS
6
ECTS
9
teaching language
English

People

responsible
Prof. Dr. Raimund Seidel
lectures
Prof. Dr. Raimund Seidel
Prof. Dr. Bernd Finkbeiner
Prof. Dr. Markus Bläser
Prof. Dr. Karl Bringmann

Assessment & Grades

entrance requirements

Programming 1 and 2 and Mathematics for Computer Scientists 1 and 2 or comparable courses in mathematics are recommended.

assessment / exams

Successful completion of the exercises entitles the student to take the exam.

grade

Will be determined from performance in exams, exercises and practical tasks. The exact modalities will be announced at the beginning of the module.

Workload

course type /weekly hours
  4 h lectures
+ 2 h tutorial
= 6 h (weekly)
total workload
   90 h of classes
+ 180 h private study
= 270 h (= 9 ECTS)

Aims / Competences to be developed

Students know various models of computation and their relative strengths and abilities.

For selected problems they can show, whether they are solvable in a certain model of computation or not.

They understand the formal notion of computability as well as non-computability.

They can reduce problems to each other.

They are familiar with basics of bounding resources (time, space) for computations and the resulting complexity theory.

Content

The language classes of the Chomsky hierarchy and their various definitions via grammars and automata; closure properties; classification of particular languages ("pumping lemmas");

determinism and non-determinism;

Turing machines and equivalent models of general computability (e.g. μ-recursive function, random acces machins), reducibility, decidability, undecidability;

the complexity measures time and space; the complexity classes P and NP;

the basics of the theory of NP-completeness.

Literature & Reading

Will be announced before the start of the course on the course page on the Internet.

Additional Information

This module is identical in content to the German-language module Grundzüge der Theoretischen Informatik.

Curriculum

This module is part of the following study programmes:

Computer Science BSc (English): Grundlagen der Informatik
study semester: 3 / standard study semester: 6
Cybersecurity BSc (English): Grundlagen der Informatik
study semester: 3 / standard study semester: 6