Sie sind hier: Startseite Lehre SS 2015 Theoretical Computer Science (Bridging Course)(Tutorial)

Theoretical Computer Science (Bridging Course)(Tutorial) - SS 2015

Aims of the lecture

The participants should get a foundational knowledge of the theoretical aspects of computer science.

Contents of the lecture

This course will address theoretical aspects of computer science. It comprises the fundamental mathematical properties of computer hard- and software. We will see what can be computed and how efficiently, as well as what cannot. More specifically, the following topics will be included:
  • Automata
  • Formal languages
  • Formal grammars
  • Turing machines
  • Decidability
  • Complexity theory
  • Logic


Rooms and Times

There will be no classical face to face lectures. Instead, the participants are supposed to follow the video recordings themselves. We provide exercise sheets and tutorials every week, to make sure the material is understood properly.
  • Lecture:
    • Mon 20 April 2015, 10-12 in building 52, SR 02-017: Introduction
  • Tutorials:
    • Mon, 10-12 in building 52, SR 02-017: By appointment
  • Final Exam:
    • Mon 31st August 2015, 10-12 in building 101, SR 01-016


Lectures are held in English, course material and exercise sheets are in English. Students may ask questions and submit exercise sheets in English.

Credit Points

6 ECTS points

Course Book

Michael Sipser. "Introduction to the theory of computation". PWS Publishing Co., Boston, MA, 1996

Additional Information

  • There is a QnA forum from the last semester for questions.
  • Teaching is done in English.


Topic Slides Videos Homework Assignment Solutions
Introduction 00.pdf n/a --- ---
Mathematical Preliminiaries 02.pdf MP4 Sheet0 Sheet0
DFA, NFA, Regular Languages 03.pdf MP4 Sheet1 Sheet1
Regular Languages and closure wrt elementary operations --- ---
Regular expressions MP4 Sheet2 Sheet2
Non-regular languages MP4 --- ---
Context Free Grammars 04.pdf MP4 Sheet3 Sheet3
Context Free Grammars MP4 --- ---
Pushdown Automata MP4 Sheet4 Sheet4
Pumping Lemma for Context Free Grammars MP4 Sheet5 Sheet5
Turing Machines 05.pdf MP4 --- ---
Turing Machines MP4 Sheet6 Sheet6
Decidability and decidable languages. 06.pdf MP4 --- ---
Decidability, mathematical backgrounds on cardinality, Cantor's diagonal argument MP4 Sheet7 Sheet7
Decidability and the halting problems. MP4 --- ---
Complexity 07.pdf MP4 Sheet8 Sheet8
Complexity MP4 --- ---
Complexity MP4 Sheet9 Sheet9
Complexity MP4 Sheet10 Sheet10
Propositional Logic and basic definitions, CNF/DNF, logical entailment. 08.pdf MP4 --- ---
Propositional Logic. Deduction/Contraposition/Contradiction Theorems and Derivations. MP4 Sheet11 Sheet11
Propositional Logic. Derivations, Soundness and Completeness of calculi. MP4 --- ---
Propositional Logic. Refutation-completeness and Resolution. MP4 Sheet12 Sheet12
First Order Logic. Derivations. 09.pdf MP4 --- ---
First Order Logic. Satisfaction, closed formulae and brief overview on Normal Forms. MP4 --- ---
Review of some old exam questions. QnA. Revision Sheet n/a --- Solutions
Benutzerspezifische Werkzeuge