Übung 5
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.
Komplexität
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.