Komplexitätstheorie
Vorlesung im Wintersemester 2018/2019
Ansprechpartner
Name
- E-Mail schreiben
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