Modules

Prerequisites

Contents

Die Vorlesung stellt eine Einführung in die Strukturelle Komplexität dar. Die dabei zentralen Fragen sind die folgenden: • Wie misst man sinnvoll den Aufwand, der nötig ist, ein Problem algorithmisch zu lösen? • Welche Ressourcen spielen dabei eine Rolle? • Wie lassen sich Probleme hinsichtlich dieser Ressourcen sinnvoll vergleichen und klassifizieren? • Was sind inhärente Hindernisse, die der Existenz beliebig guter Lösungen gewisser Probleme entgegen stehen? Im Einzelnen werden u. a. folgende Gesichtspunke behandelt: • Turingmaschine, Zeit- und Platzverbrauch einer Rechnung • Komplexitätsklassen bzgl. Zeit- oder Platzbedarf • Hierarchiesätze • die Klassen P und NP als Formalisierung effizient lösbarer und effizient verifizierbarer Probleme • NP-Vollständigkeit, Reduktion • Satz von Cook: NP-Vollständigkeit von SAT • weitere Bsp. NP-vollständiger Probleme • Randomisierte Algorithmen und die Klassen ZPP, RP und BPP • Komplexitätsklassen innerhalb von P: Paralleles Rechnen und NC • Komplexitätsklassen jenseits von NP: die Polynomhierarchie, PSPACE und NSPACE, Zählklassen • Ausblicke auf andere Zugänge zu Komplexität

Learning outcomes

Ziel des Moduls ist es, grundlegende Methoden zu erlernen mit deren Hilfe es möglich ist, Probleme gemäß der inhärenten Schwierigkeit bei ihrer algorithmischen Behandlung zu klassifizieren. Hierzu gehören: • das Kennenlernen sinnvoller Ressourcen zur Beurteilung der Komplexität eines Problems, • das Verständnis für die grundlegende Struktur von Komplexitätsaussagen, • das Beherrschen mathematischer Methoden zur Analyse und Klassifikation von Problemen, • die selbständige Umsetzung der erlernten Methoden, um die Komplexität von Problemen richtig einzuschätzen.

Assessment

• mündliche Prüfung, 30-45 Minuten

Remarks

• Studiengang Informatik M.Sc.: Wahlpflichtmodul in Komplex „Grundlagen der Informatik“ (Niveaustufe 400) • Studiengang Angewandte Mathematik M.Sc.: Wahlpflichtmodul im Komplex „Anwendungen“, Bereich „Informatik“