[DSAL] Memoization

[Robert]

Hi,

Auf Folie 483 steht, dass Memoization dazu verwendet wird, die dynamische Programmierung effizienter zu gestalten, indem Zwischenergebnisse in einer Tabelle gespeichert werden.

Anschließend folgt das MemoFibonacci(n) Beispiel, welches aber nicht iterativ und damit auch nicht dynamisch (s. Folie 471, dyn. immer iterativ) programmiert ist, sondern rekursiv.

Es macht doch auch viel mehr Sinn bei Divide&Conquer die Effizienz zu steigern, indem Zwischenergebnisse gespeichert werden und doppelte Berechnungen umgangen werden können, falls diese aufwändiger als ein Tabellenzugriff sind.
Beim dynm. Programmieren hat man ja immer eine Tabelle und somit immer ein Memoization-Prinzip.

Daher frage ich mich also grade, ob auf dieser Folie nicht eher "bei D&C" anstatt "beim dyn. Programmieren" stehen sollte...?

[aRo]

hallo Robert!

Ich denke du hast recht. Memoisation (vgl. auch wikipedia) ähnelt zwar der dynamischen Programmierung, wird in dieser aber eben nicht verwendet.
Ich denke auf Folie 483 meinten die, dass es ähnlich eben zu der dynmaischen Programmierung ist. Das soll aber nicht heißen, dass das Beispiel danach dynamisch programmiert ist.

Naja, ist etwas unverständlich aufgezogen...


PS. Wie viel Zeit hatten wir eigentlich nochmal immer für die Präsenzübungen?


EDIT:

Also, Quicksort arbeitet ja nach dem Divide and Conquer Prinzip, was im Prinzip TopDown ist.
MergeSort arbeitet nun angeblich auch nach D&C, meinem Verständnis nach würde das ganze aber eher der Bottom Up Strategie entsprechen. Denn ich fange ja erst an die Teilprobleme zu lösen und setze die dann unter Arbeit zur Gesamtlösung zusammen...
hmm...klärende Worte?