Formal Foundations of Computer Science


Formal concepts: sets, sequences, functions, relations, graphs,  words and alphabets.

Formal grammars, languages and automata. Chomsky hierarchy.

Computability and its limits.

The concept of NP completeness


- Lecture Notes
- Sipser: Introduction to the Theory of Computation. Course Technology, 3rd
edition, 2012
- Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languages, and
Computation. Prentice Hall, 3rd edition, 2006
- Schöning, Kestler: Mathe-Toolbox. Lehmanns Media, 2. erw. Auflage, 2011
- Schöning: Theoretische Informatik - kurz gefasst. 5. Auflage, Spektrum, 2008


Monday 10-12    in O27 - 121

Tuesday  14-16  in O27 - 2202

Weitere Informationen