Optimale Matrix-Kettenmultipli < Matrizen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:40 Mo 08.02.2010 | | Autor: | Tobus |
Im Bezug auf folgendes Skript:
http://theorie.informatik.uni-ulm.de/Lehre/SS3/Al/tsx8a.pdf (letzte Seite)
Die Matrix m[i,j] habe ich bereits vollständig berechnet. Hier kann ich ja noch nicht ablesen, wie genau ich die Matrizen multiplizieren muss. Ich kann nur durch das Addieren der Werte in der obersten Reihe berechnen, wieviele Operationen ich haben werde, richtig ?
Nun erstellt man ein neues Array (Skript letzte Seite). In diesem Array stehen nun die Zahlenwerte für k drin.
Daraus sollte ich jetzt ablesen können, wie genau ich die Matrizen multiplizieren kann, dass die Operationen minimal werden, aber wie genau ? Ich sitze schon das ganze We dran, aber ich komme leider nicht drauf.
VIELEN DANK
|
|
| |
|
Hallo,
ich nehme an, dass du dich auf die Tabelle beziehst. Denn die Abschätzung der Komplexität erklärt noch weniger, was du rechnen musst.
Die Tabelle gibt an, wie viele Multiplikationen nötig sind, wenn du die i-te Matrix mit der j-ten Matrix multiplizierst. In dem Beispiel wäre das [mm] M_1 [/mm] multipliziert mit [mm] M_2 [/mm] ergibt 1440 Multiplikationen. Das ist recht viel nehme ich an. [mm] M_2 [/mm] x [mm] M_3 [/mm] ergibt 720 Multiplikationen. Das wäre in der Summe recht viel. Der Algorithmus liefert aber bei [mm] M_1\times M_2\times M_3 [/mm] 936 Multiplikationen. Nun musst du nur herausfinden, was in dieser Matrix s an dieser Stelle steht. Denn offenbar wurde [mm] M_1\times (M_2\times M_3) [/mm] gerechnet. (Dabei ergeben sich 936 Multiplikationen, wie man leicht nachrechnen kann.)
> Die Matrix m[i,j] habe ich bereits vollständig berechnet.
> Hier kann ich ja noch nicht ablesen, wie genau ich die
> Matrizen multiplizieren muss. Ich kann nur durch das
> Addieren der Werte in der obersten Reihe berechnen,
> wieviele Operationen ich haben werde, richtig ?
So wie ich das verstehe hast du leider nicht recht. In deiner obersten Zeile steht meines Erachtens nach die Anzahl der Rechenoperationen im minimalen Fall. So steht es auch unter "Optimaler Algorithmus". Was leider nirgendwo steht ist, wie geklammert wurde. Dazu wird am Ende s eingeführt. So weit warst du sicher auch schon.
>
> Nun erstellt man ein neues Array (Skript letzte Seite). In
> diesem Array stehen nun die Zahlenwerte für k drin.
> Daraus sollte ich jetzt ablesen können, wie genau ich die
> Matrizen multiplizieren kann, dass die Operationen minimal
> werden, aber wie genau ? Ich sitze schon das ganze We dran,
> aber ich komme leider nicht drauf.
>
Da du m bestimmt hast, sollte es doch auch ein leichtes sein s zu bestimmen, oder? Schreib dir das doch auch erstmal auf. Vielleicht erstmal am Beispiel von [mm] M_1 [/mm] bis [mm] M_3. [/mm] Dann wird sich schon etwas erkennen lassen. Ich komme darauf, dass s[1;3]=1 ist. Das besagt [mm] M_2 [/mm] und [mm] M_3 [/mm] müssen zu erst multipliziert werden.
Würde die natürliche Reihenfolge der Multiplikation beibehalten werden können (also ohne Klammern), dann stehen in der ersten Zeile von s die Zahlen 0,1,2,3,4,5 in dieser Reihenfolge. Wird von hinten nach vorn multipliziert stehen nur 1en in der ersten Zeile.
Was dazwischen herauskommen kann und wie dann gerechnet wird, kannst du sicher selbst lösen.
Hoffentlich war das jetzt nicht zu viel drumherum geredet...
Viel Erfolg,
Roland.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Mo 08.02.2010 | | Autor: | Tobus |
Ahhh super, ich habs nun kapiert !!
VIELEN DANK !! ;)
|
|
|
|
