Not logged in. · Lost password · Register

we35fapi
Member since Apr 2018
14 posts
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 :)
Destranix
Erfahrener Webhelfer und Um-Rat-Frager
Member since Sep 2018
288 posts
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
mkmdl
Member since Nov 2009
272 posts
In reply to post #1
Quote by we35fapi:
Ich habe auch gelesen, dass Dynamische Programmierung heißt, Rekursion zu benutzen (oder?)

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.

Quote by Destranix:
Gemeint war wohl memoization.

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.
Destranix
Erfahrener Webhelfer und Um-Rat-Frager
Member since Sep 2018
288 posts
In reply to post #2
Zu d):

Also in meiner Lösung musste ich quasi nur Exchanger durch Queues ersetzen.
I hate Forumssignaturen
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen