Iloczyn Macierzy

Przykład

Mamy trzy macierze

• A₁ rozmiaru 5X2

• A₂ rozmiaru 2X3

• A₃ rozmiaru 3X4

Mnożenie macierzy jest łączne. Zatem A₁x(A₂xA₃) = (A₁xA₂)xA₃ . Ile mnożeń między liczbami wykonamy mnożąc macierze z pierwszym rozłożeniem nawiasów, a ile z drugim?

Reguła:

Niech macierz A jest rozmiaru ixk, macierz B jest rozmiaru kxj. Liczba mnożeń między liczbami, gdy mnożymy macierze AxB równa się i*k*j.

Zatem,

• pierwsze rozłożenie nawiasów kosztuje 2*3*4+5*2*4 = 24 + 40 = 64 mnożeń liczb

• drugie rozłożenie nawiasów kosztuje 5*2*3+5*3*4 = 30 + 60 = 90 mnożeń liczb

Konkluzja: to nie wszystko jedno, jak rozłożymy nawiasy, gdy mnożymy wiele prostokątnych macierzy o pasujących rozmiarach.

Zadanie

Dana liczba n macierzy i wektor r[0,n] reprezentujący rozmiary kolejnych macierzy.

A₁ jest rozmiaru r[0]xr[1]
A₂ jest rozmiaru r[1]xr[2]
.
.
.
A_i jest rozmiaru r[i-1]xr[i]
.
.
.
A_n jest rozmiaru r[n-1]xr[n]

Obliczyć liczbę mnożeń między liczbami przy optymalnym rozłożeniu nawiasów w iloczynie

A₁xA₂x . . . xA_n

macierzy.

Podzadania

Dla 1 ≤ i < j ≤ n,

a_ij = liczba mnożeń liczb przy optymalnym rozłożeniu nawiasów w iloczynie A_ix…xA_j

Lemat

a_ij = min{a_ik + a_k+1j + r[i-1]*r[k]*r[j] | i ≤ k < j } , a_ii=0.

□

Rysunek tablicy częściowych rozwiązań i kierunek wypełniania tablicy

Funkcja, dla i < j, min(i, j) = min{a_ik + a_k+1j + r[i-1]*r[k]*r[j] | i ≤ k < j } .

Algorytm funkcji min

Wejście: i < j

Działanie:
1. m = A[i+1, j] + r[i-1]*r[i]*r[j]; // i=k < j
2. for(k=i+1;k<j; k++)
{
p = A[i, k] + A[k+1, j] + r[i-1]*r[k]*r[j];
if (p<m) m=p;
}
3. zwróć m;

Algorytm rozwiązania zadania

1. A[1..n,1..n] – tablica częściowych rozwiązań, na początku wyzerowana.

2. for(i=n-1;i>=1;i--)
   for(j=i+1;j<=n; j++)
   a[i, j] = min(i, j);

3. wyświetl A[1, n].

Zadanie indywidualne (niebanalne; bez dynamicznych struktur danych, a mianowicie drzew, beznadziejnie skomplikowane rozwiązanie tablicowe)

Napisać program obliczający liczbę mnożeń przy optymalnym rozłożeniu nawiasów i wyświetlający to optymalne rozłożenie nawiasów.

Drugi wykład

Kod Greya, początki programowania na dynamicznych strukturach danych, zadanie generowania podziałów zbioru {1,2,…,n}.