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

Regular expression and languages
Deterministic and non-deterministic finite-state automata
Equivalence of regular expressions and finite-state automata
Minimization of automata
Properties of regular languages, pumping lemma
Applications and Extensions

Part B: Context-Free Languages

Context-free grammars
Normal forms
Push-down automata
Properties of context-free languages, pumping lemma
Word problem and syntactic analysis

Part C: Computability Theory

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

Part D: Complexity Theory

Polynomial time
NP and polynomial-time reductions
NP-completeness
Further NP-complete problems, what lies beyond NP
How to deal with NP-complete problems
SAT and the Exponential Time Hypotheses
Probabilistic complexity classes

← Back