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 ''eine'' optimale Gesamtlösung aus optimalen Teillösungen aufgebaut werden kann. Eine solche Lösung sollte bewusst nicht als ''die'' optimale Lösung bezeichnet werden, da es verschiedene Lösungen geben kann, die den optimalen Wert besitzen.

Die Anwendung Dynamischer Programmierung macht vor allem dann Sinn, wenn ein Problem aus sich überlappenden Teilproblemen aufgebaut ist, also wenn Teilprobleme ihrerseits gemeinsame Teilprobleme nutzen. 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 hidden>
(define table (make-hash-table))
  (define getprop
    (case-lambda
     [(k prop) (getprop k prop #f)]
     [(k prop def)
      (let ([al (hash-table-get table k (lambda () #f))])
	(if al
	    (let ([v (assq prop al)])
	      (if v
		  (unbox (cdr v))
		  def))
	    def))]))
  (define putprop
    (lambda (k prop nv)
      (let ([al (hash-table-get table k (lambda () '()))])
	(let ([v (assq prop al)])
	  (if v
	      (set-box! (cdr v) nv)
	      (hash-table-put! table k (cons (cons prop (box nv)) al)))))))</code>
<code>
(define fib-mem
  (lambda (n)
    (if (getprop 'fibs n)
        (getprop 'fibs n)
        (if (< n 2)             
            1             
            (let 
                ([fib1 (fib-mem (- n 1))])
                (putprop 'fibs (- n 1) fib1)
                (let ([fib2 (fib-mem (- n 2))])
                (+ fib1 fib2)))))))</code>
<eval>
(fib-mem 2000)
</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