Seminar: Komplexitätstheorie

 

Sommersemester 2020

Ansprechpartner

Telefon

work
+49 241 80 21703

E-Mail

E-Mail
 
 

Inhalt

Thema der Komplexitätstheorie sind die prinzipiellen Grenzen effizienter Berechenbarkeit. Dabei beschäftigt sich die Komplexitätstheorie mit der "inhärenten Schwierigkeit" algorithmischer Probleme. Gefragt wird also nicht, wie effizient ein bestimmter Algorithmus ein Problem löst, sondern wie effizient sich sich das Problem prinzipiell lösen lässt. Effizienz wird dabei gemessen als der Verbrauch von Ressourcen wie Rechenzeit, Speicherplatzverbrauch oder der Kommunikationsbandbreite.
Eine besondere Schwierigkeit besteht darin, unterschiedliche Resourcenmaße miteinander zu vergleichen, daraus ergeben sich Fragen wie "Lässt sich jeder Speicherplatzeffiziente Algorithmus durch eine Zeiteffizienten simulieren?" oder "Arbeiten randomisierte Algorithmen prinzipiell effizienter als deterministische".

Voraussetzungen

Voraussetzung für eine erfolgreiche Teilnahme am Seminar sind ein sicherer Umgang mit den Themen der Vorlesungen Datenstrukturen und Algorithmen und Berechenbarkeit und Komplexität. Kenntnisse aus der Vorlesung Komplexitätstheorie sind hilfreich aber nicht obligatorisch.

 

Organisation

Die Termine der Vorträge werden in der Vorbesprechung vereinbart.

Dozent

Martin Grohe

Anforderungen

Die Teilnehmenden des Seminars erstellen jeweils eine 5-seitige Ausarbeitung und halten einen 45-minütigen Vortrag zu einem algorithmischen Thema aus der Komplexitätstheorie. Das Thema wird mit Hilfe von Lehrbüchern und Originalliteratur erarbeitet.

 

Literatur

Die Themen des Seminars werden in der Vorbesprechung ausgegeben. Einführende Literatur zu dem Thema:

Computational complexity, Christos H. Papadimitriou; Addison-Wesley 1994
Computational Complexity - A Modern Approach, Sanjeev Arora and Boaz Barak Cambridge University Press 2009
Theory of Computation, Dexter Kozen; Springer 2006

 

Externe Links