inf401  Foundations of Theoretical Computer Science (Complete module description)
Module label  Foundations of Theoretical Computer Science 
Modulkürzel  inf401 
Credit points  6.0 KP 
Workload  180 h 
Institute directory  Department of Computing Science 
Verwendbarkeit des Moduls 

Zuständige Personen 

Prerequisites  
Skills to be acquired in this module  Introduction to the theory of automata, formal languages, computability, and complexity
Methodological competence
Social competence
Selfcompetence

Module contents  In the first part of the course, different classes of languages are introduced (regular and contextfree languages). For each class a matching automata model is presented (finite automata, pushdown automata). Various properties are proven for the introduced classes of languages and models of automata. In the second part of the course, we examine which functions are computable and which problems are decidable. To this end, the concept of algorithm is formalised. Turing machines and grammars turn out as equivalent approaches. We show that there are problems that are undecidable. Many of these problems are of practical interest. The third part of the course deals with the complexity of algorithms, i.e. how much time and space is required to solve a problem. In particular, we consider problems that are solvable in polynomial time, either deterministically or nondeterministically. These problems are classified as P and NP. 
Literaturempfehlungen  Essential:
Recommended:
Good secondary literature:

Links  
Language of instruction  German 
Duration (semesters)  1 Semester 
Module frequency  annual 
Module capacity  unlimited 
Teaching/Learning method  V+Ü 
Previous knowledge  Useful prerequisites: set theory, functions, relations, propositional and predicate logic 
Form of instruction  Comment  SWS  Frequency  Workload of compulsory attendance 

Lecture  3  WiSe  42  
Exercises  1  WiSe  14  
Präsenzzeit Modul insgesamt  56 h 
Examination  Prüfungszeiten  Type of examination 

Final exam of module  At the end of the lecture period 
Written or oral exam 