Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage

• grundlegende Komplexitätsklassen und ihre Intuition zu erklären
• Komplexitätsanalysen von Problemen (insbesondere in der polynomiellen Hierarchie)  durchzuführen...

Grundlegende Begriffe der Komplexitätstheorie, deterministische und nicht-deterministische Komplexitätsklassen, NP-vollständige Probleme, logarithmischer Speicherbedarf, die Polynomielle Hierarchie, exponentiell schwierige Probleme, Anwendungen.

Der Stoff (inklusive Übungsbeispielen) wird vom Vortragenden präsentiert.

Aufwandsabschätzung

  2 h Eingangstest
 30 h Vorlesung (12 Termine inclusive Vorbereitung)
 40 h Prüfungsvorbereitung
  3 h schriftliche + mündliche Prüfung
-----------------------------------------------------------

 75 h = 3 Ects

Die Beurteilung setzt sich aus 3 Teilen zusammen:

• Eingangstest
• Übungsbeispiele
• schriftliche und/oder mündliche Prüfung am Ende (Details werden in der Vorbesprechung fixiert)

• Grundkenntnisse in mathematischer Logik und Grundkenntnisse in Komplexitätstheorie (entsprechend der Vorlesung "Formale Methoden der Informatik") werden vorausgesetzt.
• Die TeilnehmerInnen müssen grundlegende mathematische Fertigkeiten (wie das Ausführen von Induktionsbeweisen) entsprechend den Mathematik-LVAs im Bachelor Studium mitbringen.