Vorlesung 12
In dieser letzten Vorlesung des Semesters rekapitulieren wir noch einmal das Semester und geben ein paar Ausblicke in weiterführende Themen.
Ü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.
Übung 3
In dieser Übung beschäftigen wir uns mit verschiedenen Beispielen zum Branch-and-Bound Verfahren. Wir schauen uns dabei auch das euklidische Travelling Salesman Problem (TSP) an und machen einen kleinen Exkurs zum Thema Linear/Integer Programming.
Vorlesung 06
In dieser Vorlesung schauen wir uns die Branch-And-Bound Methode in der Anwendung an. Zudem geben wir einige Ausblicke zu weiteren Optimierungsproblemen.
Vorlesung 05
In dieser Vorlesung lernen wir ein alternatives exaktes Verfahren kennen: Branch-And-Bound. Wir schauen uns dabei das Verfahren in seinen Details an und wenden es dann erneut auf das Knapsack-Problem an.
Übung 2
In dieser Übung beschäftigen wir uns intensiver mit Dynamic Programming. Dafür schauen wir uns mit Longest Common Subsequence und Matrix Chain Multiplication zwei neue Probleme an und konstruieren schrittweise Dynamic Programming Ansätze, um sie zu lösen.
Vorlesung 04
In dieser Vorlesung betrachten wir weitere Dynamic Programming – Ansätze. Dabei geht es unter Anderem um das bekannte Knapsack-Problem. Zudem betrachten wir zwei geometrische Probleme.
Übung 1
In dieser Übung beschäftigen wir uns noch einmal intensiver mit Greedy-Algorithmen. Wir schauen uns dazu das Hörsaal-Belegungsproblem genauer an.
Vorlesung 03
In dieser Vorlesung lernen wir eine neue Methode zum exakten Lösen von Problemen kennen: Dynamic Programming. Wir beginnen damit dynamische Programme anhand von Beispielen für Knapsack- und Subset Sum-Probleme zu betrachten.
Vorlesung 02
In dieser Vorlesung lernen wir die Familie der Greedy-Algorithmen kennen und schauen uns je ein Beispiel für die Probleme Fractional Matching und Subset Sum an.
Übung 0
In der ersten Übung klären wir einmal grundlegende organisatorische Fragen. Anschließend gibt es eine kleine Widerholung zu AuD 1 und wir schauen uns noch einmal den Greedy-Algorithmus zu Fractional Knapsack an.
Vorlesung 01
In dieser Vorlesung geben wir eine Einführung in Knapsack-Probleme und damit verbundene Varianten.
Willkommen bei AuD2!
Hey zusammen! Hier erscheinen alle Vorlesungen und Große Übungen, immer kurz bevor oder nachdem sie stattgefunden haben.Wir wünschen euch viel Spaß mit der Veranstaltung!