AuK/Dynamisches Programmieren SS09

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
Autoren: Markus Ullrich & Norbert Baum

 '''Dev-Status'''


=="Bottom up" versus "top down"==
 '''ToDo - Markus'''
Genau wie die Teile-und-Herrsche-Verfahren, löst auch die Dynamische Programmierung Probleme, durch die Kombination der Lösungen von Teilproblemen. Allerdings nutzt die dynamische Programmierung einen Bottom-up-Ansatz, bei dem alle Teillösungen "von unten her" berechnet werden. Dabei wird erwartet, dass die optimale Gesamtlösung aus optimalen Teillösungen aufgebaut werden kann.

Die Anwendung Dynamischer Programmierung macht vor allem dann Sinn, wenn ein Problem aus sich überlappenden Teilproblemen aufgebaut ist. In diesem Fall würde ein Teile-und-Herrsche-Verfahren die gemeinsamen Teilprobleme wiederholt lösen und somit mehr Arbeit als notwendig ausführen. Bei einem dynamischen Programm werden die bereits berechneten Teillösungen in einer Tabelle gespeichert, womit deren erneute Berechnung entfällt.

Das bedeutet, dass sich der Begriff "Programmierung" hier nicht auf das schreiben von Code bezieht, sondern vielmehr auf eben diese tabellarische Methode zum Lösen von Optimierungsproblemen. Demnach sollte die Methode besser "Dynamisches Optimieren" heißen.

==Iterative Berechnung==
 '''ToDo - Norbert'''
==Aufwandsbetrachtung==
 '''ToDo - Norbert'''
==Rekursive Berechnung mit memoizing==
 '''ToDo - Markus'''
==Beispiele==



===Fibonacci-Zahl===
 '''ToDo - Norbert
 Fib-mem fertig bauen!
 '''
====ohne memoizing====
<code>
(define fib
 (lambda (n)
  (if (< n 2)
   1
   (+ (fib (- n 1)) (fib (- n 2))))))</code>
<eval>
(fib 20)</eval>

====mit memoziing====
<code>
(define fib-mem
  (lambda (n)
    (if (< n 2)
        1
        (let* ([fib-1 (nimm-oder-berechne fib-mem (- n 1) 'fibs)]             
               [fib-2 (nimm-oder-berechne fib-mem (- n 2) 'fibs)]
               [fib (+ fib-1 fib-2)])
          (putprop 'fibs n fib)
          fib))))

(define nimm-oder-berechne
  (lambda (fkt n tabelle)
    (let ([resultat (getprop tabelle n)])
      (if resultat resultat (fkt n)))))
</code>
<eval>
(fib-mem 20)
</eval>

===Rundreiseproblem===
 '''ToDo - Markus'''
===(Ablaufkoordination von Magnetbändern)===
 '''ToDo - ?'''

==Finden der optimalen Teilstruktur==
 '''ToDo - Markus'''
==Java, C# und F# Versionen==
[[Dynamisches Programmieren/Beispiele in Java | Beispiele als Java Version]]

[[Dynamisches Programmieren/Beispiele in CSharp und FSharp | Beispiele als C# und teilweise in F#]]

==Files==
Folien, Beispiele...

==Links==
[http://msdn.microsoft.com/en-us/fsharp/default.aspx MSDN F#]

[http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/release.aspx F# Compiler Download (auch für Mono)]

[http://msdn.microsoft.com/de-de/magazine/cc164244.aspx Einführung F#]

== Literatur ==
* Th. H. Cormen, Ch. E. Leiserson, R. Rivest, C. Stein: ''Algorithmen - Eine Einführung'', 2.Auflage, Oldenbourg Wissenschaftsverlag GmbH 2007, ISBN 978-3-486-58262-8

* Gessner, Wacker: ''Dynamische Optimierung - Einführung-Modelle-Computerprogramme'', 1.Auflage, Carl Hanser Verlag 1972, ISBN 3-446-11539-0

* Ch. Wagenknecht: ''Algorithmen und Komplexität'', 1.Auflage, Carl Hanser Verlag 2003, ISBN 3-446-22314-2

* A. Iwainsky: ''Dynamische Optimierung - Gegenstand-Methoden-Möglichkeiten'', 1.Auflage, VEB Verlag Technik Berlin 1984

* J. Hinrichsen: ''Branch- and Bound-Verfahren zur Lösung des Rundreiseproblems'', Vandenhoeck & Ruprecht Göttingen 1975, ISBN 3-525-12432-5

* S. Wolfgang, U. Gerhard: Dissertation ''Duale Entartung in der lineare Optimierung, Transportproblem mit zusätzlichen Nebenbedingungen und Rundreiseproblem'' TU Dresden und Bergakademie Freiberg, 21.02.1975