Logic and
Theory of
Discrete Systems

Informatik 7

Complexity Theory

Vorlesung im Sommersemester 2016

Allgemeine Informationen zu Vorlesung und Übung (V3+Ü2) findet man auch im Campus-System der RWTH.
Diese Vorlesung wird auf Englisch gehalten.

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

L²P-Lernraum

Virtueller Lernraum zur Vorlesung (Anmeldung über Campus erforderlich)

FaLang translation system by Faboba