Formal Foundations of Computer Science
Inhalt
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
Literatur
- 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
Dozent
Lectures
Monday 10-12 in O27 - 121
Tuesday 14-16 in O27 - 2202