Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Aufwand bei Matrizenmultiplikation

Aufwand bei Matrizenmultiplikation

Universität / Fachhochschule

Kombinatorische Optimierung

Matrizenrechnung

Tags: Kombinatorische Optimierung, Matrizenrechnung

Susi1988 aktiv_icon

01:39 Uhr, 18.09.2010

Hallo erstmal,

mein Problem: Ich habe mehrere Matrizen die ich mit einander multiplizieren muss.

Nehmen wir an $A_{1} \cdot A_{2} \cdot A_{3} {\cdot A}_{4} {\cdot A}_{5}$ . Die Vorraussetzung der

Matrizenmultiplikation sind erfüllt und die m und n Werte sind gegeben.

Meine Aufgabe ist es, diesen Term so mit Klammern zu besetzen, dass ein

minimaler Aufwand entsteht. Nun habe ich mich gefragt, ob ich mir immer den

kleinsten Aufwand suche und um diese Multiplikation klammern setze, sprich

1) $A_{2} \cdot A_{3}$ sollen den kleinsten Teilaufwand $t_{1}$ haben

2) $A_{1} \cdot {(A}_{2} \cdot A_{3} {) \cdot A}_{4} {\cdot A}_{5}$ wird gemerkt. $A_{2} \cdot A_{3}$ wir durch B ersetzt

3) $A_{1} \cdot B {\cdot A}_{4} {\cdot A}_{5}$ wieder suche ich den kleinsten Aufwand $t_{2}$ , in dem Fall

${B \cdot A}_{4}$ und merke mir wieder $A_{1} \cdot ({(A}_{2} \cdot A_{3} {) \cdot A}_{4}) {\cdot A}_{5}$

N) ... und am Ende ist mein gemerktes mein Lösung mit dem minimalsten Aufwand der sich aus $t_{1} + t_{2} + t_{3} + ... + t_{k}$ zusammen setzt. Ist das richtig oder muss ich wirklich jede Möglichkeit durchgehen, was sich als schwierig gestaltet da ich noch mehr Matrizen habe?

Bitte helft mir!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Photon aktiv_icon

10:42 Uhr, 19.09.2010

Moin,

ich hab leider von Optimierung keine Ahnung, aber vielleicht würde es helfen, ein paar kleinere Beispiele durchzuspielen (alle Möglichkeiten durchrechnen lassen, den Aufwand jeweils ausgeben lassen und dann zu schauen, ob der Weg mit dem kleinsten Aufwand wirklich so zustande kommt, wie du vermutest). Einfach um mal ein Gefühl dafür zu kriegen, wohin der Hase läuft. :-)

MfG Photon

Susi1988 aktiv_icon

13:31 Uhr, 19.09.2010

Wie errechne ich wie viel mögliche Kombinationen es gibt?

z.B wenn ich 12 Matrizen habe, wieviele Möglichkeiten Klammern zu setzen (siehe Eintrag 1) gibt es dann?

Ist das dann iwie sowas wie $12^{i r g e n d w a s ?}$ ?

Photon aktiv_icon

14:07 Uhr, 19.09.2010

Hmm, mal überlegen: Wenn du 12 Matrizen hast, dann hast du 11 Möglichkeiten das innerste Klammerpaar zu setzen. Nach dem Ausmultiplizieren dieses Klammerpaars hast du nur noch 11 Matrizen, also 10 Möglichkeiten das nächste Klammerpaar zu setzen. Hieße also, dass es

(n - 1)!

Möglichkeiten gibt bei

n

Matrizen die Klammern zu setzen.

Susi1988 aktiv_icon

14:19 Uhr, 20.09.2010

Ohh ja ist logisch! Vielen Dank!

Falls noch jmd was zu ersten Beitrag beizufügen hat, würde mich das sehr freuen.

hagman aktiv_icon

15:55 Uhr, 20.09.2010

Es gibt natürlich viel weniger als

(n - 1)!

verschiedene Klammerungsmöglichkeiten:
Bei

a \cdot b \cdot c \cdot d

erst

x := a \cdot b,

dann

y := c \cdot d,

dann

z := x \cdot y

zu rechnen ist dasselbe wie erst

y := c \cdot d,

dann

x := a \cdot b,

dann

z := x \cdot y

.
Beide Rechenwege entsprechen der Klammerung

(a \cdot b) \cdot (c \cdot d)

.
Die Anzahl der Klammerungen berechnet sich rekursiv durch

F (1) = 1, F (n) = \sum_{k = 1}^{n - 1} F (k) \cdot F (n - k)

. So gibt es nur

42

statt

120

Klammerungen für 6 Faktoren.
Egal, das nützt für die eigentliche Aufgabenstellung leider gar wenig

. .

Photon aktiv_icon

16:10 Uhr, 20.09.2010

Oha, ich bin ja ein Trottel, hast natürlich Recht. :-)

793976

792953

	Status: nicht eingeloggt	Noch nicht registriert?