Theoretical Computer Science
Undergraduate course, ETH Zürich, D-INFK, Prof. Hromkovic, 2022
The class will take place every Wednesday from 4:15 pm to 6 pm in HG D5.3
Here you can find the material covered in class [DE].
This lecture gives an introduction to theoretical computer science, presenting the basic concepts and methods of computer science in its historical context. We present computer science as an interdisciplinary science which, on the one hand, investigates the border between the possible and the impossible and the quantitative laws of information processing, and, on the other hand, designs, analyzes, verifies, and implements computer systems.
The main topics of the lecture are:
- alphabets, words, languages, measuring the information content of words, representation of algorithmic tasks
- finite automata, regular and context-free grammars
- Turing machines and computability
- complexity theory and NP-completeness
- design of algorithms for hard problems