Seminar: Komplexitätstheorie
Sommersemester 2020
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
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