DynProg
2010-02-22, 11:12:50
Ich sitze hier gerade vor einem Uni-Skript, und kann einen Schritt einfach nicht nachvollziehen. Eventuell kann mir jemand von euch weiterhelfen. Es dreht sich um Codegenierung mittels dynamischer Programmierung. Folgender Ausdruck (oder besser gesagt der DAG dazu) ist gegeben: e*(c/d) .
Maschinenmodell:
• Instruktionssatz
Ri := Mj
Ri := Ri op Rj
Ri := Ri op Mj
Ri := Rj
Mj := Ri
• zwei Register vorhanden
Dies ist die Lösung nach Skript:
http://img62.imageshack.us/img62/8388/dynprog.png (http://img62.imageshack.us/i/dynprog.png/)
Der Kostenvektor C=(5,5,4) leuchtet mir nicht ein. Warum kann ich bei einem Register nicht einfach, den linken Teilbaum aus dem Speicher (Kosten 0) und den Rechten Teilbaum aus dem Register (Kosten 2) nehmen? Dann würde man doch nur auf Kosten von 4 (0+2+1 für Berechnung) kommen, also 5,4,4?
Maschinenmodell:
• Instruktionssatz
Ri := Mj
Ri := Ri op Rj
Ri := Ri op Mj
Ri := Rj
Mj := Ri
• zwei Register vorhanden
Dies ist die Lösung nach Skript:
http://img62.imageshack.us/img62/8388/dynprog.png (http://img62.imageshack.us/i/dynprog.png/)
Der Kostenvektor C=(5,5,4) leuchtet mir nicht ein. Warum kann ich bei einem Register nicht einfach, den linken Teilbaum aus dem Speicher (Kosten 0) und den Rechten Teilbaum aus dem Register (Kosten 2) nehmen? Dann würde man doch nur auf Kosten von 4 (0+2+1 für Berechnung) kommen, also 5,4,4?