Theoretische Informatik II
| Content: |
| First we consider the question, whether there exist problems which are not solvable algorithmically. In connection with this question we introduce a model of a computer, which is close to reality (Turing maschine). Having done this, we consider some computable algorithmic problems, and investigate these according to their algorithmic complexity. In particular, we investigate the complexity classes P and NP as well as NP-complete problems. Furthermore, we discuss other models of computers like finite automata and their "computing powers". Finally, we consider grammers and formal languages, the Chomsky hierarchy and corresponding programming languages. |
| Literature: |
|
| Participants: |
| students of computer science and mathematics |
| Prerequisites: |
| It is a good idea to have participated in the course "Theoretical Computer Science 1" |
| Exam: |
| oral or written exams as required for the individual student. |
| Exercises: |
