Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Matrix-Kettenmultiplikation
Autor
Universität/Hochschule Matrix-Kettenmultiplikation
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Themenstart: 2021-12-05

https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/54010_Unbekjdghknannt.PNG Hallo zusammen, Könnte mir jemand bitte unbedingt dabei helfen? Wie kann ich die Rekursion beweisen? Danke im Voraus!


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1890
  Beitrag No.1, eingetragen 2021-12-06

Hallo s-amalgh! Vieleicht kannst Du erst mal versuchen, mit 3 Stück 2x2 Matrizen zu arbeiten. Manchmal hilft bei solchen Aufgaben vollständige Induktion. (Ich habe für die Aufgabe bisher noch keine Lösung.) Viele Grüße Ronald


Wahlurne Für Delastelle bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.2, vom Themenstarter, eingetragen 2021-12-06

Danke erstmal für deine Antwort! Ich glaub ich muss so ungefähr machen aber ich weiß nicht wie https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/54010_57508EB6-9C28-4AEC-A593-45727AEA319B.jpeg


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.3, vom Themenstarter, eingetragen 2021-12-06

Diese Bemerkung ist in der Aufgabe https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/54010_E2A8F428-BD10-40F2-BE72-FCA195BA7A52.jpeg Ich glaub wir müssen das durch Widerspruch beweisen Der Widerspruch geht in etwa so: würden wir von den zwei Teilen nicht die minimale Klammerung nehmen, könnten wir die Summe verkleinern, in dem wir den minimalen m(i,k) oder m(k+1,j) nehmen. Also für ein Minimum müssen auch die Teilprobleme optimal sein. Könntest du mir bitte dabei helfen?


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1890
  Beitrag No.4, eingetragen 2021-12-06

Ich glaube, Du brauchst schnell eine Antwort. Ich muss mir den Sachverhalt aber erst durchdenken. Vielleicht hat ja noch jemand anderes Zeit!


Wahlurne Für Delastelle bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.5, vom Themenstarter, eingetragen 2021-12-06

Ja sie könnten dir natürlich den Sachverhalt durchdenken :)


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.6, eingetragen 2021-12-06

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Hallo, die Rekursion ist eigentlich recht leicht einzusehen: Um das Produkt $A_i\cdots A_j$ zu berechnen, muss man an irgendeiner Stelle $k$ aufspalten, d.h. man muss zunächst $B:= A_i\cdots A_k$ und $C:= A_{k+1}\cdots A_j$ berechnen und anschließend noch $BC$. Überlege Dir, dass man für die Berechnung von $B,C$ und $BC$ insgesamt $m(i,k) + m(k+1, j) + p_{i-1}p_kp_j$ skalare Multiplikationen berechnen muss. $m(i,j)$ erhält man dann natürlich, wenn man $k$ optimal wählt.\(\endgroup\)


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.7, vom Themenstarter, eingetragen 2021-12-06

Danke erstmal für deine Antwort! Wie kann ich B und C berechnen?


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.8, eingetragen 2021-12-06

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Wie man $B$ und $C$ konkret berechnet, ist eigentlich irrelevant (man könnte sich auch das aber rekursiv überlegen). Wichtig ist erstmal nur, wie viele Skalarmultiplikationen jeweils bei der optimalen Berechnung von $B$ bzw. $C$ benötigt werden. Und genau diese Frage lässt sich mit der Funktion $m$ beantworten.\(\endgroup\)


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.9, vom Themenstarter, eingetragen 2021-12-06

Könnten Sie mir bitte den ersten Schritt von der Lösung schreiben ? Ich weiß nicht wie ich anfangen soll Dann kann ich wahrscheinlich alleine weiter machen..


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.10, eingetragen 2021-12-06

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Sieh Dir die Definition von $m$ nochmal an. Diese Funktion ist extra dafür gemacht Fragen der Art "wie viele skalare Multiplikationen benötigt man zur Berechung von $B:= A_i\cdots A_k$?" zu beantworten. Da gibt es ehrlich gesagt nicht viel zu erklären.\(\endgroup\)


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.11, vom Themenstarter, eingetragen 2021-12-06

k skalare Multiplikationen ? 🤔


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.12, eingetragen 2021-12-06

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Es ist wirklich nur pures Buchstaben substituieren: Für alle $i,j$ braucht man zur optimalen Berechnung von $A_i\cdots A_j$ per Definition $m(i,j)$ skalare Multiplikationen. Wie viele skalare Multiplikationen braucht man also zur Berechnung von $A_i\cdots A_k$?\(\endgroup\)


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.13, vom Themenstarter, eingetragen 2021-12-06

meinst du m(i,k) ?


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.14, eingetragen 2021-12-06

👍


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.15, vom Themenstarter, eingetragen 2021-12-06

Und was soll ich jetzt machen ?


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.16, eingetragen 2021-12-06

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Siehe No.6. Du wirst Dir noch überlegen müssen, welche Dimensionen $B$ und $C$ haben.\(\endgroup\)


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.17, vom Themenstarter, eingetragen 2021-12-06

wie kann ich das bestimmen?


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.18, eingetragen 2021-12-06

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Versuche es doch erstmal selbst. In der Aufgabe steht, welche Dimensionen die Matrizen $A_i$ haben. Wenn Du Matrizenmultiplikation verstanden hast, dann kannst Du damit die Dimensionen von $B$ und $C$ angeben.\(\endgroup\)


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.19, vom Themenstarter, eingetragen 2021-12-06

p_i−1 × p_k für B ?


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.20, vom Themenstarter, eingetragen 2021-12-06

Ich habe eine Frage.. Ist der Beweis eins davon oder nicht? https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/54010_Unbenakjgbnlkjbrgrnnt.PNG https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/54010_Unbenanjkghtrlkghrnt.PNG


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.21, eingetragen 2021-12-06

\quoteon(2021-12-06 02:10 - s-amalgh in Beitrag No. 19) p_i−1 × p_k für B ? \quoteoff Korrekt.


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.22, vom Themenstarter, eingetragen 2021-12-06

Ist keiner Beweis von den zwei was wir brauchen?


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.23, eingetragen 2021-12-06

Lies es Dir halt durch und entscheide selbst.


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.24, vom Themenstarter, eingetragen 2021-12-06

Ich habe gelesen aber ich habe nicht zu 100% verstanden weil ich englisch nicht gut kann deswegen frage ich..


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.25, eingetragen 2021-12-06

Was hast Du denn nicht verstanden?


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.26, vom Themenstarter, eingetragen 2021-12-06

Ich glaube der erste Beweis kann auch der Beweis für meine Aufgabe sein aber ich weiß es nicht ob das reicht oder ob was fehlt [Die Antwort wurde nach Beitrag No.20 begonnen.]


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.27, eingetragen 2021-12-06

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Das ganze Ding ist nur ein Beweis, nicht zwei. Um die Gleichheit zu zeigen, wird zuerst $\leq$ gezeigt und anschließend $\geq$. Im Prinzip steht in den zwei Folien genau das gleiche wie in No.6. Ist Dir mittlerweile klar, woher der Term $m(i,k)+m(k+1,j)+ p_{i-1}p_kp_j$ kommt?\(\endgroup\)


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.28, vom Themenstarter, eingetragen 2021-12-06

Ja der Term kommt aus B , C und BC oder?


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.29, eingetragen 2021-12-06

Genau. Gibt es noch ein Problem, dass Dich daran hindert, die Beweisidee aus No.6 genauer auszuführen?


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.30, vom Themenstarter, eingetragen 2021-12-06

Achso, ich dachte dass sie zwei Beweise sind.. Ich glaube dann dass dieser Beweis reicht für meiner Aufgabe [Die Antwort wurde nach Beitrag No.28 begonnen.]


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.31, vom Themenstarter, eingetragen 2021-12-06

Eigentlich ich habe verstanden was du erklärt hast aber mein Problem ist das zusammen als Beweis zu schrieben


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.32, eingetragen 2021-12-06

Dann fang doch zumindest mal damit an und poste das Resultat. Dann können wir ggf. immer noch nachbessern. Ich werde nicht die Lösung Deiner Übungsaufgabe ausformulieren, ich beantworte aber gern Deine Fragen.


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.33, vom Themenstarter, eingetragen 2021-12-06

Um zu der minimalen Anzahl an skalaren Multiplikationen für Produkt A_i · · · A_j zu kommen, müssen wir das Produkt A_i · · · A_j brechnen. Dafür müssen wir an irgendeiner Stelle k aufspalten, d.h. wir müssen zunächst B:= A_i⋯A_k und C:= A_k+1⋯A_j berechnen und anschließend noch BC. wir benötigen m(i,k) Skalarmultiplikationen bei der optimalen Berechnung von B, und m(k+1,j) Skalarmultiplikationen bei der optimalen Berechnung von C und p_(i−1)*p_k*p_j Skalarmultiplikationen bei der optimalen Berechnung von BC daraus folgt m(i,k) + m(k+1,j) + p_(i−1)*p_k*p_j = m(i,j) so vielleicht ?


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.34, eingetragen 2021-12-06

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Ist doch schonmal ganz gut! \quoteon(2021-12-06 10:04 - s-amalgh in Beitrag No. 33) Um zu der minimalen Anzahl an skalaren Multiplikationen für Produkt A_i · · · A_j zu kommen, müssen wir das Produkt A_i · · · A_j brechnen. \quoteoff Soll das letzte Wort "berechnen" oder "brechen" sein? Ersteres ist redundant, letzteres klingt etwas komisch ist aber ok. \quoteon Dafür müssen wir an irgendeiner Stelle k aufspalten, d.h. wir müssen zunächst B:= A_i⋯A_k und C:= A_k+1⋯A_j berechnen und anschließend noch BC. wir benötigen m(i,k) Skalarmultiplikationen bei der optimalen Berechnung von B, und m(k+1,j) Skalarmultiplikationen bei der optimalen Berechnung von C \quoteoff Der Teil ist gut. \quoteon und p_(i−1)*p_k*p_j Skalarmultiplikationen bei der optimalen Berechnung von BC \quoteoff Das solltest Du noch genauer begründen. (Welche Dimensionen haben $B$ und $C$?) \quoteon daraus folgt m(i,k) + m(k+1,j) + p_(i−1)*p_k*p_j = m(i,j) \quoteoff Nicht ganz. Wenn man bei $k$ spaltet, dann braucht man $m(i,k) + m(k+1,j) + p_{i−1}p_kp_j$ skalare Multiplikationen. $m(i,j)$ erhält man erst, wenn man $k$ so wählt, dass dieser Ausdruck minimal wird.\(\endgroup\)


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.35, vom Themenstarter, eingetragen 2021-12-06

Um zu der minimalen Anzahl an skalaren Multiplikationen für Produkt A_i · · · A_j zu kommen, müssen wir das Produkt A_i · · · A_j berechnen. Dafür müssen wir an irgendeiner Stelle k aufspalten, d.h. wir müssen zunächst B:= A_i⋯A_k und C:= A_k+1⋯A_j berechnen und anschließend noch BC. wir benötigen m(i,k) Skalarmultiplikationen bei der optimalen Berechnung von B, und m(k+1,j) Skalarmultiplikationen bei der optimalen Berechnung von C und p_(i−1)*p_k*p_j Skalarmultiplikationen bei der optimalen Berechnung von BC (da C die Dimension p_k × p_j und B die Dimension p_i−1 × p_k) \showon Nicht ganz. Wenn man bei k spaltet, dann braucht man m(i,k)+m(k+1,j)+pi−1pkpj skalare Multiplikationen. m(i,j) erhält man erst, wenn man k so wählt, dass dieser Ausdruck minimal wird. \showoff Wie formuliere ich das?


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3195
  Beitrag No.36, eingetragen 2021-12-06

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Ich finde den ersten Satz immer noch seltsam, aber sei es drum - ist schließlich eine Mathe- und keine Deutschaufgabe. Man versteht, was Du meinst. \quoteon Wie formuliere ich das? \quoteoff Z.B. so wie ich es geschrieben hatte: Wenn man bei $k$ spaltet, benötigt man also ... skalare Multiplikationen. Wählt man $k$ so, dass dieser Ausdruck minimal wird, dann erhält man $m(i,j)$. \(\endgroup\)


Wahlurne Für Nuramon bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.37, vom Themenstarter, eingetragen 2021-12-06

Das habe ich so geschrieben wie du gesagt hast und habe das jetzt abgegeben 👍😁 Danke für alles du hast mir sehr geholfen!


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 328
  Beitrag No.38, vom Themenstarter, eingetragen 2021-12-06

Ich habe da kleine Frage https://www.matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=256616&start=0&lps=1863867#v1863867 Könntest du mir bitte da helfen wenn du eine Idee hättest? Danke! 😄


Wahlurne Für s-amalgh bei den Matheplanet-Awards stimmen
   Profil
s-amalgh hat die Antworten auf ihre/seine Frage gesehen.
s-amalgh hatte hier bereits selbst das Ok-Häkchen gesetzt.
s-amalgh wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]