KI710 P222-0071 kim 4 V 5 1 yes German 180-minute written exam KI710 Computer Science and Communication Systems 1 mandatory course PIM-TI Applied Informatics 1 mandatory course 60 class hours (= 45 clock hours) over a 15-week period.The total student study time is 150 hours (equivalent to 5 ECTS credits).There are therefore 105 hours available for class preparation and follow-up work and exam preparation. [?] Prof. Dr. Thomas Kretschmer tk Prof. Dr. Thomas Kretschmer tk Students will learn the traditional areas of theoretical informatics: automata and languages, computability and complexity theory. Students will acquire an understanding of the fundamental mathematical properties of hardware and software systems. After completing this course, students will understand and be able to apply the theoretical concepts that are used to solve problems of practical relevance. This will allow them to generate theoretically well-grounded and properly conceived solutions. Students will also appreciate the fundamental limitations that apply to certain types of problems. They will also know how to classify problems into complexity classes with respect to runtime and memory requirements. 1. Automata and languages - Regular languages - Context-free languages 2. Computability theory - The Church-Turing thesis - Decidability - Reducibility - Defining information 3. Complexity theory - Time complexity with NP-completeness - Spatial complexity [?] HOPCROFT John E.; ULLMANN Jeffrey D.; MOTWANI Rajeev: Einführung in die Automatentheorie - Formale Sprachen und Komplexitätstheorie, Pearson Studium, München, 2. Auflage 2002 SIPSER Michael: Introduction to the theory of computation, Course Technology, Boston 1997 WS 2016/17 WS 2010/11 WS 2009/10 WS 2008/09 WS 2007/08 WS 2006/07 WS 2005/06 Mon Sep 14 11:13:26 CEST 2026, CKEY=thinfo, BKEY=kim, CID=[?], LANGUAGE=en, DATE=14.09.2026