AuK/Dynamisches Programmieren SS09

Wiki-Quelltext dieser Seite.

Autoren: Markus Ullrich & Norbert Baum

 '''Dev-Status'''


=="Buttom up" versus "top down"==
==Iterative Berechnung==
==Aufwandsbetrachtung==
==Rekursive Berechnung mit memoizing==
==Beispiele==


<language>Scheme</language>
===Fibonacci-Zahl===
====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>

===0/1 Rucksackproblem===
===Rundreiseproblem===
===Schnellster Weg S326 (dickes Buch) ??? ===

==Finden der optimalen Teilstruktur==
==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==
dickes Buch xD