Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Frage zur Aufgabe 7.4
Hallo zusammen,
Da Deutsch nicht meine Muttersprache ist, habe ich manchmal Probleme, ganz einfache Dinge zu verstehen, deshalb habe ich ein paar Fragen zu Aufgabe 7.4.
a) Die Aufgabe sagt, dass wir die “computeValue” durch Dynamische Programmierung implementieren sollen. Ich habe auch gelesen, dass Dynamische Programmierung heißt, Rekursion zu benutzen (oder?). Wenn ja, was soll hier rekursive sein? Soweit ich es verstehe, soll computeValue nur die Matrix[row][column] updaten, oder?
c) Sollen wir hier jeweils einen Exchanger zwischen zwei Threads haben oder insgesamt nur einen Exchanger und dann irgendwie wissen, wer was geschickt hat? Und soll durch den Exchanger nur die “Erlaubnis zur Nutzung des Wertes” geschickt werden bzw. die nächste Thread sagen, dass dieser Wert schon berechnet war und schon benutzt werden kann, oder?
d) Hier müssen wir einfach die Exchangers mit Queues austauschen, oder?
Danke 
a) Rekursion brauchst du nicht. Gemeint war wohl memoization. Ja, du sollst matrix[ row ][column] updaten.
c) Vermutlich will man von uns, dass es für jede Spalte einen Exchanger gibt. Dieser soll wohl eine Queue mit den vollendeten Werten der vorherigen Spalte enthalten.
d) Hab ich mir noch nicht angeschaut. Fand das mit den Exchangern so blöd…
Nein. Bei dynamischer Programmierung wird das Problem rekursiv formuliert, damit klar wird, dass sich eine optimale Lösung aus optimalen Lösungen von Teilproblemen zusammensetzt. Die Implementierung kann auf beliebige Art und Weise erfolgen.
Nein. Nach der Definition von Cormen et al. meint Memoisation, dass eine Prozedur in jedem Schritt prüft, ob ein Wert schon berechnet wurde. Falls nicht, wird dieser berechnet. Genau das ist hier aber nicht gefragt. Es soll einfach das Schema der DP angewandt werden, demzufolge (wie oben geschrieben) sich eine optimale Lösung aus Teillösungen zusammensetzt, die (zusätzlich) mehrfach zur Berechnung der optimalen Lösung benutzt werden (können). Da es eine fixe Reihenfolge gibt, in der man in dieser Aufgabe die Teilergebnisse sinnvoll berechnet, bedarf es keiner Memoisation, da wir, wenn wir das erste Mal ein (Teil-)Problem lösen, bereits alle von dessen Teilproblemen gelöst haben.
Zu d):
Also in meiner Lösung musste ich quasi nur Exchanger durch Queues ersetzen.