Komplexitätstheorie

 

Vorlesung im Sommersemester 2017

 

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 Vorlesung wird in Englisch gehalten.

Termine

Dienstag, 14:15 Uhr - 15:45 Uhr im AH II
Donnerstag, 16:15 Uhr - 17:45 Uhr im AH II

Dozent

Pascal Schweitzer

 

Übungsaufgaben

Wir werden wöchentliche Übungsaufgaben veröffentlichen. Das erfolgreiche Bearbeiten dieser Aufgaben, sammeln mindestens 50% der erreichbaren Punkte, ist erforderlich für die Prüfungszulassung.

Die Lösungen der Übungsaufgaben werden immer Freitags, 10:15-11:45 Uhr im AH VI vorgestellt.

Mündliche Prüfung

Zum erfolgrichen Absolvieren der Vorlesung gehört das bestehen einer mündlichen Prüfung.
Die genauen Details zur Prüfung werden im L2P bekannt gegeben.