Foundations of Computing II

Lecturer: Dennis Komm

Time und Place: Fr 8.30 - 12.00, BIN-2.A.01

Language: English

Content:

This course covers topics from discrete math and formal methods building the foundation of computing. The material of this course is pervasive in the areas of algorithms, data structures and programming but appears virtually in all areas of computer science as well. The course will cover topics such as, but not limited to, proof methods, formal languages, deterministic and nondeterministic finite automata, grammars and pushdown automata, Turing machines, computability, decidability and complexity, P and NP, NP completeness.

Literature:

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automata Theory, Languages and Computation, 3rd Edition. Addison Wesley 2006.
• Additional material (not obligatory): Juraj Hromkovic. Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Springer 2007.

Teaching Materials:

Please consult the OLAT system for any further information.