Kurs:Algorithmen und Datenstrukturen/Kapitel 7

Aus testwiki
Zur Navigation springen Zur Suche springen

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

Dynamisches Programmieren

Kurze Beschreibung dessen, was in diesem Kapitel alles vorkommen wird

Von der Rekursion zum Dynamischen Programm

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

Beispiel Matrixmultiplikation

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

Beispiel String-Matching

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

Beispiel Optimale Suchbaeume

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

Beispiel Museumsdieb

  • Zeigen, wie eine Diskretisierung das Loesen mit DP moeglich macht
Abgerufen von „https://de.wikiversity.beta.math.wmflabs.org/w/index.php?title=Kurs:Algorithmen_und_Datenstrukturen/Kapitel_7&oldid=17“