
Content 

This block course treats the same topics as the lecture 'Theoretische Informatik' from our Bachelor program where it has to be taught in German.
Contents of the lecture:
1. Formal languages
 regular languages and finite automata, pumping lemma
 context free languages and pushdown automata, pumping lemma
2. Computability
 Recursive functions
 Turing machines
 Churchs thesis
 Undecidability of the Halting problem
 Recursion Theorem
3. Logics
 Elementary arithmetic
 Goedels incompleteness theorems
4. Complexity Theory
 Turing Machine Complexity Classes
 Hierarchy Theorems
 NPcompleteness
 Speedup and Gap theorem
 Kolmogorov complexity
 More on separation of complexity classes

Organizational information 

 Lectures will be given Mon to Thu 10:00  12:00 from Feb 17 to Mar 27 2014
 Lecture hall: LH 003 E1.3, except for 26.02, 13.03,20.03,26.03  LH 002 E1.3
 Registration for the lecture is mandatory and is now open
 Also register for the exam in the HISPOS system!
 Two exercise sheets will be handed out and collected every week: on Monday and on Wednesday.
 There will be two Tutorials every week: Monday 1315, Wednesday 1416, Room 328 E1.3
 Exam Prerequisites:
In order to be admitted to the exam you have to achieve 50% of all exercise points.
In addition each student has to present at least two exercise solutions in the tutorial.
 Exam:
You have to pass one oral exam.
 Exam will take place on March 28 2014 starting at 10:00 in Room 328 E1.3. Reexam will take place on April 28 at 10:00 in Room 328 E1.3.

News 


Lecture evaluation 
Auswertungsinformation Informatik 
Evaluation WS13/14  Theoretical Computer Science 