Kapitel 2 – Dynamic Programming

Inhalt

In diesem Kapitel lernen wir das Prinzip von Dynamic Programming (zu Deutsch dynamische Programmierung) kennen und schauen uns unter anderem Dynamic Programming Ansätze für die bereits bekannten Subset Sum- und Knapsack-Probleme an.

Termine

  • Vorlesung 3 am 04.05.21: Dynamic Programming für Subset Sum
  • Vorlesung 4 am 11.05.21: Dynamic Programming für Knapsack; Dynamic Programming für zwei geometrische Probleme
  • Übung 2 am 12.05.21: Dynamic Programming für Longest Common Subsequence und Matrix Chain Multiplication.

Veranstaltungen

  • Ü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 4
    In dieser Vorlesung betrachten wir weitere Dynamic Programming – Ansätze an. Dabei geht es unter Anderem um das bekannte Knapsack-Problem. Zudem betrachten wir zwei geometrische Probleme.
  • Vorlesung 3
    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.