Dynamisches Programmieren WS15-16

Wiki-Quelltext dieser Seite.

Leonard Mory, Frank Ehrlich, Alexander Preuss

=Thematischer Einstieg und Motivation=
==Was ist dynamisches Programmieren?==
*Kein Algorithmus, eher eine Lösungsstrategie
*Begriff kommt aus der Zeit, wo Programmieren Tabellenmethoden bezeichnete
*Optimierungsverfahren, kein Programmieren
*"Teile und Herrsche" dient als Grundlage
**Um ein umfangreiches Problem zu lösen, wird es in kleine Teilprobleme zerlegt
**Diese werden unabhängig von einander gelöst und in eine Tabelle geschrieben
*Anders als bei "Teile und Herrsche" wird bei dem Dynamischen Programmieren ein Bottom-up-Ansatz verwendet
*
==Bottom-up==
==Optimalitätskriterium==

==Dynamisches Programmieren vs Memoizing==
*beide vermeiden wiederholte Berechnung durch Speichern
**⇒Tradeoff: Speicher statt Zeit

{| class="wikitable"
|-
! Memoization !! Dynamisches Programmieren
|-
| Top-Down, Depth-First Ansatz || Bottom-Up, Breadth-First Ansatz          
|-
| Beschreibung bleibt unverändert || Beschriebung wird verändert          
|-
| Vermeidet unnötige Berechnungen || Kann unnötige Berechnungen nicht vermeiden 
|-
| Kann Speicher leicht verschwenden || Kann Speicher einsparen, indem unnötige Resultate vermieden werden 
|-
| Muss prüfen ob Berechnung bereits vorliegt || keine Prüfung nötig durch neue Beschreibung 
|-
| Komplexität hängt von Schnelligkeit des "Nachschlagens" ab || Komplexität hängt von Speichermethode ab 
|}

=Rucksackproblem=
==Memorizing==
===rekursiver Algorithmus===

=Rundreiseproblem=

=Quellen=
*http://www.theory.informatik.uni-kassel.de/veranstaltungen/EntwurfWS2013-14/vorlesung/EAvAKap3.pdf
*http://www.mathe.tu-freiberg.de/~ernst/Lehre/AD/Folien/adKapitel11.pdf