Kurs:Algorithmen und Datenstrukturen/Kapitel 7

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Dieses Kapitel gehoert zum Kurs Algorithmen und Datenstrukturen des Fachbereichs Informatik.

Dynamisches Programmieren[Bearbeiten]

Kurze Beschreibung dessen, was in diesem Kapitel alles vorkommen wird

Von der Rekursion zum Dynamischen Programm[Bearbeiten]

  • Einfaches Beispiel mit Zwischenspeicherung der Resultate
  • Bedingungen, damit das Dynamische Programmieren moeglich ist
  • Backtracking, um Resultate zurueckzuholen

Beispiel Matrixmultiplikation[Bearbeiten]

  • Wie klammert man das Produkt von Matrizen , damit die Kosten am tiefsten sind?
  • Rekursive Loesung hinschreiben
  • Bedingungen testen
  • Dynamisches Programm formulieren

Beispiel String-Matching[Bearbeiten]

  • Definition des Problems
  • Rekursive Loesung hinschreiben
  • Bedingungen testen
  • Dynamisches Programm formulieren

Beispiel Optimale Suchbaeume[Bearbeiten]

  • Definition des Problems
  • Rekursive Loesung hinschreiben
  • Bedingungen testen
  • Dynamisches Programm formulieren

Beispiel Museumsdieb[Bearbeiten]

  • Zeigen, wie eine Diskretisierung das Loesen mit DP moeglich macht