Module label  Foundations of Theoretical Computer Science 
Module code  inf401 
Credit points  6.0 KP 
Workload  180 h 
Faculty/Institute  Department of Computing Science 
Used in course of study 

Contact person 

Entry requirements  
Skills to be acquired in this module  Introduction to the theory of automata, formal languages, computability, and complexity Professional competence The students:
Methodological competence The students:
Social competence The students:
Selfcompetence The students:

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. 
Reader's advisory   essentiell: Skript "Grundbegriffe der Theoretischen Informatik", jeweils in aktueller Ausgabe  empfohlen: Schöning: "Theoretische Informatik kurzgefasst", 5. Auflage, Spektrum, 2008  Gute Sekundärliteratur: Hopcroft, Motwani, Ullman: "Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie", Pearson, 2002 (ein Klassiker...) 
Links  
Language of instruction  German 
Duration (semesters)  1 Semester 
Module frequency  jährlich 
Module capacity  unlimited 
Modullevel  AC (Aufbaucurriculum / Composition) 
Modulart  je nach Studiengang Pflicht oder Wahlpflicht 
Lern/Lehrform / Type of program  V+Ü 
Vorkenntnisse / Previous knowledge 
Course type  Comment  SWS  Frequency  Workload attendance 

Lecture  3.00  WiSe  42 h  
Exercise or tutorial  1.00  WiSe  14 h  
Total time of attendance for the module  56 h 
Examination  Time of examination  Type of examination 

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