Inhalt
In diesem Kapitel beschäftigen wir uns mit theoretischen Überlegungen zur “Schwere” von Problemen. Wir betrachten dabei verschiedene Komplexitätsklassen, ihre Beziehung zueinander und welche Konsequenzen es hat, wenn Probleme in einer bestimmten Klasse liegen.
Veranstaltungen
-
Übung 6
In dieser Übung beschäftigen wir uns mit dem Approximationsalgorithmus Greedyk für das Knapsack-Problem. Außerdem schauen wir uns mit Vertex-Cover noch ein neues Problem an. -
Vorlesung 9
In dieser Vorlesung analysieren wir die Komplexität einiger uns bekannter Probleme und besprechen die daraus resultierenden Konsequenzen. -
Vorlesung 8
In dieser Vorlesung beginnen wir uns mit weiterführenden Aspekten zur Komplexität zu beschäftigen. Dabei lernen wir die verschiedenen Komplexitätsklassen kennen und diskutieren deren Eigenschaften und Beziehungen.