Sommersemester 2017

<< WS2016    WS2017 >>
Archiv
Lehrveranstaltung und -termine, Stand: 18.08.17 07:06
Komplexitätstheorie - Prof. Klaus Reinhardt
0 Termine

Ziel der Komplexitätstheorie ist die Klassifizierung algorithmischer Probleme bezüglich des Ressourcenverbrauchs und mttels der Reduktion.
Der Begriff der Vollständigkeit eines Problems wird am Beispiel von NP nochmals gründlich untersucht und es werden auch für andere Komplexitätsklassen, wie P, NL und PSPACE, vollständige Probleme vorgestellt.
Es werden auch alternative Berechnungsmodelle wie Schaltkreise, PRAM's und augmentierte Kellerautomaten betrachtet.

Ab 19.4. immer in Raum 3325 im Informatikinstitut Ernst-Abbe-Platz 2.