Kurs:Algorithmen und Datenstrukturen/Kapitel 7

Aus Wikiversity

Wechseln zu: Navigation, Suche

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

Inhaltsverzeichnis

[Bearbeiten] Dynamisches Programmieren

Kurze Beschreibung dessen, was in diesem Kapitel alles vorkommen wird

[Bearbeiten] Von der Rekursion zum Dynamischen Programm

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

[Bearbeiten] Beispiel Matrixmultiplikation

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

[Bearbeiten] Beispiel String-Matching

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

[Bearbeiten] Beispiel Optimale Suchbaeume

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

[Bearbeiten] Beispiel Museumsdieb

  • Zeigen, wie eine Diskretisierung das Loesen mit DP moeglich macht
Von „http://de.wikiversity.org/wiki/Kurs:Algorithmen_und_Datenstrukturen/Kapitel_7“
Persönliche Werkzeuge