Inne, zadanie nr 4736

Autor	Zadanie / Rozwiązanie
makaron1 postów: 60	2016-06-20 16:46:33 Dane sa macierze A1, A2, A3, A4, A5 o rozmiarach odpowiednio 9 × 12, 12 × 14, 14 × 8, 8 × 11, 11 × 7. Wyznacz najmniejsza liczbe mnozen potrzebnych do obliczenia iloczynu A1,A2,A3,A4,A5: i podaj rozmieszczenie nawiasów realizujace te liczbe mnozen: Może ktoś wyjaśnić ?

janusz78 postów: 820	2016-06-20 17:44:54 Wykorzystaj algorytm MM (minimalnego mnożenia macierzy), znajdując optymalny układ nawiasowania, albo sprawdź wszystkie możliwe przypadki nawiasowania iloczynu pięciu macierzy i wybierz ten układ nawiasowania, który zawiera najmniejszą sumę ich mnożeń. $ (A_{1}(A_{2}A_{3}A_{4}A_{5}),$ $ (A_{1}A_{2})(A_{3}A_{4}A_{5}),$ $(A_{1}A_{2}A_{3})(A_{4}A_{5}),$ ...................................

makaron1 postów: 60	2016-06-20 18:11:13 Jakie będzie wyglądać działanie $ (A_{1} A_{2} A_{3}) \cdot (A_{4} A_{5}) $ bo musze robić coś zle, gdyz nie pasuje mi do odpowiedzi..

makaron1 postów: 60	2016-06-20 18:15:14 Podkreślone liczby wiem jak obliczyć, ale nie wiem jak reszte, o to mi chodzi dokładniej

makaron1 postów: 60	2016-06-20 20:06:55 Ktoś jest w stanie pomóc ?

tumor postów: 8070	2016-06-21 16:21:54 Mnożenie macierzy $a\times b$ przez $b\times c$ odpowiada abc mnożeniom współczynników. $A_1A_2$ - 91214=1512 mnożeń $A_2A_3$ - 12148=1344 mnożeń i tak dalej, podkreślone wiesz skąd się biorą. a) by pomnożyć macierze $A_1,A_2,A_3$ mamy dwa możliwe nawiasowania domnożenie $(A_1A_2)A_3$ daje 1512+1008=2510 natomiast $A_1(A_2A_3)$ daje 1344+864=2208 b) Analogicznie mnożenie macierzy $A_2,A_3,A_4$ daje zależnie od nawiasowania 2400 lub 3080 c) Mnożenie macierzy $A_3,A_4,A_5$ może dać 2310 lub 1400. d) Mnożenie macierzy od $A_1$ do $A_4$ może być domnożeniem najlepszego mnożenia z a) prawostronnie przez $A_4$, może być domnożeniem najlepszego wyniku z b) przez $A_1$ lewostronnie, a może być mnożeniem ($A_1A_2$)($A_3A_4$) Sobie policz, ile te możliwości dają. Najlepsza z nich powinna być tą z tabeli. e) Analogicznie wynik mnożenia macierzy od $A_2$ do $A_5$ jest jednym z trzech możliwych zależnie od nawiasowań. Ostatecznie wynik mnożenia macierzy od $A_1$ do $A_5$ może być jednym z ($A_1$)(to co w podpunkcie e) ($A_1A_2$)(podpunkt c) (podpunkt a)($A_4A_5$) (podpunkt d)($A_5$) W macierzy powyżej wiersz 1 kolumna 3 oznacza najlepszą liczbę mnożeń dla macierzy $A_1,A_2,A_3$, a wiersz 3 kolumna 5 oznacza optymalną liczbę mnożeń dla macierzy $A_3,A_4,A_5$. To po prostu rozwiązania pewnych podproblemów. Dla mnożenia 4 macierzy (od pierwszej do czwartej lub od drugiej do piątej) rozważamy kilka nawiasowań, używamy w nich nawiasowań dla podproblemów rzędu 2 i 3. Dla mnożenia wszystkich 5 macierzy używamy wcześniejszych podproblemów rzędu 2,3,4 i sprawdzamy, który da minimum mnożeń. Wyniki inne niż optymalne nie są zamieszczane w tej tabeli, zatem nie widzisz, że w rzeczywistości było wykonanych więcej obliczeń, po 2-4 obliczenia na jedną komórkę tabeli, w zależności od tego, jak rozkładamy na podproblemy.

makaron1 postów: 60	2016-06-21 16:40:15 DZiękuje Ci bardzo!

makaron1 postów: 60	2016-06-22 17:25:50 Z podpunktu d) "Mnożenie macierzy $ A_{1} $ do $ A_{4} $ może być domnożeniem najlepszego mnożenia z a) prawostronnie przez $ A_{4}"$ Czy mógłbyś napisać jak się to mnoży, bo nie mogę tego zrobić.. W tym przypadku, najlepszy mnożenie z a) to 1344 + $9 \cdot 12 \cdot 8 $ = 1344+864 = 2208

tumor postów: 8070	2016-06-22 21:13:37 d) napisałem kilka możliwości, jakie rozpatrujemy dla podproblemu $A_1$ do $A_4$ Najlepsza możliwość $A_1$ do $A_3$ daje $2208$, dodanie $A_4$ to $+9811$ (dlatego, że wynik mnożenia, przy dowolnym nawiasowaniu, macierzy $A_1,A_2,A_3$ ma wymiary 98, natomiast macierz $A_4$ ma wymiary 811) Najlepsza możliwość $A_2$ do $A_4$ daje 2400, dodanie $A_1$ to $+91211$ Natomiast mnożenie $(A_1A_2)(A_3A_4)$ to $1512+1232+91411$. Najkorzystniejsza jest pierwsza opcja, w sumie 3000. Taka też wartość widnieje w tabeli dla podproblemu $A_1...A_4$, czyli pierwszy wiersz, czwarta kolumna.

makaron1 postów: 60	2016-06-22 23:06:27 Ogarnąłem to, już chce obliczyć tę ostatnią liczbę i tak jak napisałeś, wezmy 1 możliwość czyli $ (A_{1}) $(to co w podpunkcie e). No i w podpunkcie e) wychodzi 2576 czyli $ A_{2}(A_{3}A_{4}A_{5}) $ To jak to się mnoży ? W odpowiedzi jest nawias ((A1(A2 A3))(A4 A5)) i nie mogę wpaść na to jakie to jest mnożenie

strony: 1 2

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj