Jedes Modul umfasst 3 ECTS. Sie wählen insgesamt 10 Module/30 ECTS in den folgenden Modulkategorien:
- 12-15 ECTS in Technisch-wissenschaftlichen Modulen (TSM)
TSM-Module vermitteln Ihnen profilspezifische Fachkompetenz und ergänzen die dezentralen Vertiefungsmodule.
- 9-12 ECTS in Erweiterten theoretischen Grundlagen (FTP)
FTP-Module behandeln theoretische Grundlagen wie die höhere Mathematik, Physik, Informationstheorie, Chemie usw. Sie erweitern Ihre abstrakte, wissenschaftliche Tiefe und tragen dazu bei, den für die Innovation wichtigen Bogen zwischen Abstraktion und Anwendung spannen zu können.
- 6-9 ECTS in Kontextmodulen (CM)
CM-Module vermitteln Ihnen Zusatzkompetenzen aus Bereichen wie Technologiemanagement, Betriebswirtschaft, Kommunikation, Projektmanagement, Patentrecht, Vertragsrecht usw.
In der Modulbeschreibung (siehe: Herunterladen der vollständigen Modulbeschreibung) finden Sie die kompletten Sprachangaben je Modul, unterteilt in die folgenden Kategorien:
The aim of this module is to deepen some basic theoretical aspects of computer science. The master students will learn that ...
- formal languages and automata are essential concepts to describe different types of problems and computations;
- Computability/decidability are central to explain that for many problems seem to have an intuitive solution, although they can not be solved by algorithms;
- Complexity deals with the amount of time required to solve a problem, and there are many very practical problems that can not be solved in reasonable time or space.
Good knowledge of programming, algorithms and discrete mathematics.
- The students understand that three different mathematical formalisms (finite state automata, regular grammars, regular expressions) are equivalent and define the set of regular languages. Finite state automata and regular expressions are widely used and will be explained using examples from lexical analysis, modeling of simple state-based systems, telecommunications protocols and program verification.
- The students realize that programming languages with regular languages can not be fully described. Context-free grammars, on the other hand, are suitable for developing all modern programming languages. Parsing is closely linked to the context-free languages. Using parser generators, students can explain top-down and bottom-up parsing.
- The students know that many problems are undecidable, i.e. that there are no algorithms to solve them, or rather that not everything is predictable. Such intuitively difficult to understand problems occur e.g. in the case of operating systems (deadlock problem), object-oriented programming languages (subtype decision) or program verification.
- The students understand that decidable problems are classified according to the resources needed to solve them (time or space) and know the major complexity classes (P, NP, EXP, PSPACE), their differences, and interrelationships (e.g., hierarchy).
- The students understand the concept of nondeterminism, which plays an essential role in the study of complexity. The complexity class NP (nondeterministic polynomial time) includes a subclass of very practical problems that are not solvable in reasonable time. Cryptology, machine vision, various optimization problems and many other areas are affected by such problems. Students can demonstrate that such problems are indeed unsolvable in reasonable time, and know some ways to circumvent this limitation through approximation techniques. Many problems known as NP-complete are presented and investigated.
The module is divided into three parts:
- Languages and automata (about 36 %)
- Alphabets, words, formal languages, grammars
- Finite state automata, regular languages/grammars, regular expressions, nondeterminism
- Pushdown automata, context-free languages/grammar
- Turing machines
- Computability/decidability (about 21 %)
- Various computation models, Church-Turing thesis
- Reduction of a problem to another
- Decidable/undecidable problems
- Computable/uncomputable functions
- Complexity (about 43 %)
- Types of complexity (time, space)
- Complexity classes, polynomial time complexity, NP, polynomial time reductions, NP-completeness
- Approximation methods
Lehr- und Lernmethoden
- Frontal teaching
- Presentation and discussion of theoretical topics
- Discussion of practical examples to reduce the gap between theory and practice
- Exercises and self-study of selected topics
Introduction to the Theory of Computation, Michael Sipser, Cengage Learning, 3rd International Edition, 2013.
Reference: www-math.mit.edu/~sipser/book.html (Homepage of author of the book)
Computers Ltd.: What They Really Can't Do, David Harel, Oxford University Press, 2000.
Introduction to automata theory, languages, and computation, J.E. Hopcroft and J.D. Ullman, Addison-Wesley Publishing Company, Reading, MA, 1979.