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.

2019S, VO, 2.0h, 3.0EC

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VO Lecture

Aim of course

Knowledge of the central notions, results, and methods of theoretical computer science

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. In a final fourth part we will consider the
theoretical foundations of program verification which allows the application
and combination of several results from the previous parts.

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Mon14:15 - 15:4504.03.2019 - 24.06.2019 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Theoretical Computer Science - Single appointments
DayDateTimeLocationDescription
Mon04.03.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mon11.03.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mon18.03.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mon25.03.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mon01.04.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mon08.04.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mon29.04.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mon06.05.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mon13.05.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mon20.05.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mon27.05.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mon03.06.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mon17.06.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mon24.06.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung

Course registration

Not necessary

Curricula

Literature

Lecture notes for this course are available.

Accompanying courses

Language

if required in English