|
Member since Apr 2018
14 posts
|
2019-06-14, 00:36 #1
Subject: 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 
|
|
Member since Sep 2018
288 posts
|
2019-06-14, 06:29 #2
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.... |
|
I hate Forumssignaturen
|
|
Member since Nov 2009
272 posts
|
2019-06-14, 07:15 #3
In reply to post #1
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. |
|
Member since Sep 2018
288 posts
|
2019-06-14, 09:11 #4
In reply to post #2
Zu d):
Also in meiner Lösung musste ich quasi nur Exchanger durch Queues ersetzen. |
|
I hate Forumssignaturen
|
Datenschutz |
Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev,
© 2003-2011 by Yves Goergen