Kurs:Algorithmen und Datenstrukturen/Kapitel 7

Dieses Kapitel gehoert zum Kurs Algorithmen und Datenstrukturen 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 $M_{1}M_{2}\cdots M_{n}$, 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