Logic and
Theory of
Discrete Systems

Informatik 7

Komplexitätstheorie

Seminar im Wintersemester 2016/17

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 und Anforderungen

  • 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.
  • 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.

Organisatorisches

  • Der Termin der Vorbesprechung wird auf dieser Seite und im l2p-Raum bekannt gegeben.
  • Die Termine der Vorträge werden in der Vorbesprechung vereinbart.
  • Dozenten: Martin Grohe

Themen und 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