Computability and Complexity

Module Code
TI5001
Module Coordinators
Bettina Just
Teachers
  • Wolfgang Henrich
  • Bettina Just
  • Hans-Rudolf Metz
  • Albert Schneider
  • Short Description
    The lecture discusses: Computability, Decidability, Reconizability; Halting problems; Goedels incompleteness theorem; Time complexity classes; P-NP-problem; Cook's theorem.
    Learning Objectives

    Students have in-depth knowledge about characteristics of dynamical systems. In particular, students are able to describe and analyze technical systems of different application domains by mathematical models. They have knowledge of major control design methods. Students are familiar with tools to simulate continuous and discrete time control systems. Students are able to independently acquire new skills and knowledge in control theory and can use this purposefully to develop solutions for control problems.

    The capacity for abstraction is increased.

    Students can present and discuss complex issues in the group.

    Contents

    Students have in-depth knowledge about characteristics of dynamical systems. In particular, students are able to describe and analyze technical systems of different application domains by mathematical models. They have knowledge of major control design methods. Students are familiar with tools to simulate continuous and discrete time control systems. Students are able to independently acquire new skills and knowledge in control theory and can use this purposefully to develop solutions for control problems.

    The capacity for abstraction is increased.

    Students can present and discuss complex issues in the group.

    Duration in Semester
    1
    Instruction Language
    German
    Total Effort
    6 CrP; an estimated 180 hours, of which approximately 60 are spent in class.
    Weekly School Hours
    4
    Method of Instruction
    Lecture 3 sppw Exercises 1 sppw
    Requirements for the awarding of Credit Points

    Prüfungsleistung: Elaboration and presentation on a scientific question

    Together100%

    Evaluation Standard
    according to examination regulations (§ 9)
    Availability
    Yearly
    References
    • M. Sipser: Introduction to the Theory of Computation PWS Publishing Company
    • S. Arora, B. Barak: Computational Complexity - A Modern Approach, Cambridge University Press
    • V. Vazirani: Approximation Algorithms, Springer
    • I. Wegener: Komplexitätstheorie, Springer
    Prerequisites
    None
    Prerequisite for Modules