Sie sind hier: Startseite Lehre WS 2014/15 Theoretical Computer Science (Bridging Course)

Theoretical Computer Science (Bridging Course) - WS 2014/15

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

  • Lectures:
    • Thu, 08-10 in building 51, HS 00-031
    • Fri, 10-11 in building 78, SR 00-014
  • Exercises:
    • Fri, 11-12 in building 78, SR 00-014
  • Final Exam:
    • Tue 31st March 2015, 10-13 in building 101, HS 00-036


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 for questions available.
  • Teaching is done in English.


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