Komplexitätstheorie

 

Vorlesung im Wintersemester 2018/2019

 

Termine

Vorlesung
Mo, 08:30 - 10:00 Uhr (AH III)
Do, 14:30 - 16:00 Uhr (AH III)

Übung
Do, 16:30 - 18:00 Uhr (5056)

 
 

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

 

Organisatorisches

Die erste Vorlesung findet am 11.10.2018 statt.

Die Vorlesung wird in Englisch gehalten.

Prüfungen

Klausurtermine werden noch bekannt gegeben.

Dozent

Martin Grohe