Complexity Theory

 

Lecture in the summer term 2017

 

Content

The topic of the complexity theory are the principle boundaries of efficient computability. For that the complexity theorie questions "inherent dificulties" of algorithmic problems. Therefor the question is not, how efficient the algorithm solves a problem, but how efficient a problem can be solved in general. Efficencie will be measured as consumption of ressources, like computation time, used memory, or used bandwith.
Especially the comparison of the different ressource dimensions is tricky. This leads to questions like " Can every memory efficent algorithm be simulated through a time efficent algorithm?" or " Do randomized algorithm in principle work better than deterministic ones?".

Based on the lecture "Compuatbility and Complexity" is this lecture a more in-depth introduction of the central topics of the complexity theory.

Previous Knowledge

Knowledge from the lectures "Discret Structures", "Linear Algebra", "Computability and Complexity" and "Data Structure and Algorithms" is required.

 

Organization

The course will be held in english.

Time and Place

Tuesday, 2:15 - 3:45pm in AH II
Thursday, 4:15 - 5:45pm im AH II

Lecturer

Pascal Schweitzer

 

Exercises

There will be weekly exercise sets. Completing these successfully, reaching at least 50% of possible points, is necessary for admittance to the examination.

The solutions of the exercises will be presented on Friday, 10:15am - 11:45am in AH VI.

Oral Exam

There will be oral exams. The exact modalities of the exams will be announced later.