Computability and Complexity

 

Lecture in Winter Term 2015/2016

 
A turing machine Copyright: © Rocky Acosta (CC BY 3.0)

Contact

Name

Sandra Kiefer

 
 

Content

What problems can be solved using a computer? And what problems can be solved efficiently? - These are the questions we try to raise during this course. We try to answer these questions mathematically. In order for this we have to define and modell the terms problem, computer and efficiency. Afterwards we will be able to make definite and far reaching statements concerning the efficiency of solving problems through calulators. Basics for this course are mathematical modells and methods. The reference to realistic computers and practical problems will be evidently explained. A highlight is the NP-complete theory, which impact on theoretical and practical applications cannot be overrated. The course is structured as:

Part 1: Computability

  • Chapter 1: Introduction to Basics
  • Chapter 2: Modelling of Machines and Program Languages
  • Chapter 3: Non computable Problems

Part 2: Complexity

  • Chapter 4: The compexity classes P and NP
  • Chapter 5: NP-Complete
  • Chapter 6: Heuristiks and approximation algorithms for NP-hard problems
 

Organization

Lecture will be held in german.

Lecturer

Martin Grohe

 

External Links