Komplexitätstheorie
Seminar im Wintersemester 2015/16
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.
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: Pascal Schweitzer
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