| Summer 2012 | Detailed view Komplexitätstheorie (German) | | | |
Ziel der Komplexitätstheorie ist die Quantifizierung von Rechner- und Rechenressourcen (Rechenzeit, Speicherplatz, Hardwareaufwand, Kommunikationsaufwand, ...), die zur algorithmischen Lösung konkreter Probleme bzw. von Aufgaben einer Problemklasse benötigt werden. Die Vorlesung bietet eine fundierte Einführung in die Komplexitätstheorie. Schwerpunktmäßig wird die Bedeutung komplexitätstheoretischer Aussagen für den Algorithmenentwurf herausgearbeitet.