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 1214 and Thu 1012 (HZO 30)
Exercises: See VVZ.
Help Desk: Thu 1214 (MB 2/90)

First meeting: 
Oct 10 
Credits: 
89 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 nondeterministic finitestate automata
 Equivalence of regular expressions and finitestate automata
 Minimization of automata
 Properties of regular languages, pumping lemma
 Applications and Extensions
Part B: ContextFree Languages
 Contextfree grammars
 Normal forms
 Pushdown automata
 Properties of contextfree languages, pumping lemma
 Word problem and syntactic analysis
Part C: Computability Theory
 Turing machines, computability, decidability
 Equivalence of Turing machines, GOTO programs & WHILE programs, ChurchTuring thesis
 Undecidability of the halting problem, reductions
 Further undecidable problems
 Universal Turing machines, semidecidability, arithmetic hierarchy
Part D: Complexity Theory
 Polynomial time
 NP and polynomialtime reductions
 NPcompleteness
 Further NPcomplete problems, what lies beyond NP
 How to deal with NPcomplete problems
 SAT and the Exponential Time Hypotheses
 Probabilistic complexity classes
← Back