Lecture Informatik 3 - Theoretische Informatik (Winter 2023/24)

Type: Lecture with Exercises
Programs: BSc CS, ITS, AI
Lecturers: Michael Walter, Eike Kiltz
Teaching Assistants: Sebastian Marks, Vladimir Lysikov, Julien Duman, Christoph Ries, Erwin Tang, Marko Schmellenkamp, Lea Thiel, Linus Mika Brandt
Time and Place: Lectures: Tue 12-14 and Thu 10-12 (HZO 30)
Exercises: See VVZ.
Help Desk: Thu 12-14 (MB 2/90)
First meeting: Oct 10
Credits: 8-9 CP
Contact time: 4+2 SWS
Language: German
Course number: 212002
Links: Moodle, VVZ

Course Description

This course will give an introduction to the theory of computation. We will be discussing how to model computational problems, formal languages, and machine models formally and gain insights into their power and limitations. We will also discuss complexity theory, which helps predict which computational problems can be expected to be solved efficiently and which one cannot. Please see Moodle for more detail.

Part A: Regular Languages

  1. Regular expression and languages
  2. Deterministic and non-deterministic finite-state automata
  3. Equivalence of regular expressions and finite-state automata
  4. Minimization of automata
  5. Properties of regular languages, pumping lemma
  6. Applications and Extensions

Part B: Context-Free Languages

  1. Context-free grammars
  2. Normal forms
  3. Push-down automata
  4. Properties of context-free languages, pumping lemma
  5. Word problem and syntactic analysis

Part C: Computability Theory

  1. Turing machines, computability, decidability
  2. Equivalence of Turing machines, GOTO programs & WHILE programs, Church-Turing thesis
  3. Undecidability of the halting problem, reductions
  4. Further undecidable problems
  5. Universal Turing machines, semi-decidability, arithmetic hierarchy

Part D: Complexity Theory

  1. Polynomial time
  2. NP and polynomial-time reductions
  3. NP-completeness
  4. Further NP-complete problems, what lies beyond NP
  5. How to deal with NP-complete problems
  6. SAT and the Exponential Time Hypotheses
  7. Probabilistic complexity classes
← Back