Inhalt
In diesem Kapitel diskutieren wir einige grundlegende Fragen auf Basis des Knapsack(Rucksack)-Problems. Dabei geht es vor allem darum in welchen Varianten sich so ein grundlegendes Problem betrachten lässt und wie sich schließlich Lösungen für die verschiedenen Probleme finden lassen.
Termine
- Vorlesung 1 am 20.04.21: Einführung: Knapsack-Problem und Varianten
- Übung 0 am 21.04.21: Organisation, Wiederholung AuD1, Greedy für Knacksack-Probleme.
- Vorlesung 2 am 27.04.21: Greedy-Algorithmus für Fractional Matching; Subset Sum
- Übung 1 am 05.05.21: Greedy-Algorithmen, Hörsaal-Belegung
Veranstaltungen
-
Ü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 2
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 1
In dieser Vorlesung geben wir eine Einführung in Knapsack-Probleme und damit verbundene Varianten.