Institut für Rechnerarchitektur
und Parallelrechner
Theoretical Computer Science
Main Page
 
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
- NP-completeness
- 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 13-15, Wednesday 14-16, 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. Re-exam 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