Übung 6
In dieser Übung begeben wir uns auf einen kurzen Rückblick auf das vergangene Semester und wiederholen noch ein paar typische Themen.
Vorlesung 13
In dieser letzten Vorlesung des Semesters rekapitulieren wir noch einmal das Semester und geben ein paar Ausblicke in weiterführende Themen.
Vorlesung 12
In dieser Vorlesung beschäftigen wir uns etwas näher mit Hashfunktionen und Lösungsstrategien für auftretende Probleme wie Kollisionen. Außerdem schauen wir uns weitere Anwendungen für Hashfunktionen an.
Übung 5
In dieser Übung beschäftigen wir uns mit verschiedenen Reduktionen von NP-schweren Problemen. Danach begeben wir uns noch auf einen Ausflug in die Welt des Hashings.
Vorlesung 10
In dieser Vorlesung machen wir einen Exkurs und beschäftigen und mit Optimierungsmethoden für mehrdimensionales Packen.
Übung 4
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 09
In dieser Vorlesung analysieren wir die Komplexität einiger uns bekannter Probleme und besprechen die daraus resultierenden Konsequenzen.
Vorlesung 08
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.
Vorlesung 07
In dieser Vorlesung beginnen wir uns mit Approximationsverfahren zu beschäftigen. Wir lernen dabei den Begriff der Gütegarantie kennen und schauen und einen Approximationsalgorithmus für das Knapsack-Problem an.