Complexity Theory

 

Vorlesung im Sommersemester 2016

Kontakt

Telefon

work
+49 241 80 21717

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

Basierend auf der Grundvorlesung "Berechenbarkeit und Komplexität" ist diese Vorlesung eine tiefergehende Einführung in die zentralen Themen der Komplexitätstheorie.

Voraussetzungen

Kenntnisse aus den Modulen Diskrete Strukturen, Lineare Algebra, Berechenbarkeit und Komplexität, Datenstrukturen und Algorithmen

 

Organisation

Vortragssprache in Englisch.

Dozent

Pascal Schweizer