108.036 Theoretical Computer Science
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2022S, VO, 2.0h, 3.0EC


  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VO Lecture
  • Format: Distance Learning

Learning outcomes

After successful completion of the course, students are able to...

The intended learning outcome of this course is to understand the contents of the course. Among other effects, this understanding forms the basis for the capability to correctly reproduce the statements and notions covered in the course as well as for the ability to explain and apply the proof techniques used in the course.

Subject of course

The lecture starts with an introduction to the theory of finite automata and formal languages. We get to know the classes of regular and context-free languages, as well as various formalisms for defining such languages, in particular finite automata and formal grammars. In the second part, after a significant leap in expressivity, we will deal with computability theory, i.e., the question which functions are computable in principle. We use the operator representation of partial recursive functions as well as Turing-machines. We discuss the Church-Turing thesis and prove the foundational results of computability theory. In the third part we consider computational complexity theory which is obtained from computability theory by restricting the resources which are available to a computation, e.g. to polynomial time. The P vs. NP -problem belongs to this subject and will form the centre of our discussion of computational complexity.

Teaching methods

reading of lecture notes, discussion on contents

Mode of examination


Additional information

For further information please consult the TUWEL-page of this course.



Course dates

Mon18:00 - 19:0014.03.2022 Meeting Room, Freihaus, green area, 5th floorVorbesprechung

Examination modalities

Positive Absolvierung einer mündlichen Prüfung.

Course registration

Begin End Deregistration end
11.02.2022 00:00

Registration modalities

Melden Sie sich bitte zu dieser LVA an um auf den zugehörigen TUWEL-Kurs zugreifen zu können.



Lecture notes for this course are available.

Accompanying courses


if required in English