INF.01116.07 - Komplexitätstheorie (Course overview)

INF.01116.07 - Komplexitätstheorie (Course overview)

INF.01116.07 Institut für Informatik 5 CP

Komplexitätstheorie

Courses WiSe 2025/26
Prerequisites
keine
Reference text
Vertiefungsmodul für die Vertiefungsrichtung "Algorithmen und Theoretische Informatik" im Masterstudiengang Informatik ab Version 2013.
Module prerequisite for admission to any examination
mindestens 50% der Punkte aus den Übungsblättern zur Komplexitätstheorie
Module examination
mündl. Prüfung oder Klausur
Skills to be acquired in this module
Studierende sollen durch dieses Modul die folgenden Kompetenzen erwerben:
  • Sie können beurteilen, mit welchem Aufwand algorithmische Probleme auf einer Maschine, unabhängig vom konkreten Computer, gelöst werden können.
  • Sie verstehen praktische Grenzen der algorithmischen Lösbarkeit von Problemen und können die Komplexität spezieller Probleme einschätzen und klassifizieren.
  • Sie sind in der Lage, mit Reduktions- und Simulationstechniken komplexitätstheoretische Untersuchungen anzustellen.
  • Sie verstehen abstrakte Zusammenhänge und können selbstständig mit grundlegenden mathematische Methoden umgehen.
  • Sie können verschiedene Problemlösestrategien und Beweisverfahren anwenden.
Module components Semester courses Examination
Course 1: Lecture (Vorlesung)
Course 2: Exercises (Übung)
Course 3: Course (Bearbeitung der Übungsaufgaben)