Free Printable Optimalno matrično množenje

1.

Pomnožimo matrike $A_0\cdot A_1\cdot A_2$ . Pri tem je $A_{0\ }:\ 1\ \times3$ dimenzionalna matrika, $A_{1\ }:\ 3\ \times\ 1$ dimenzionalna matrika in $A_2\ :\ 1\times2\$ dimenzionalna matrika. Kaj je najmanjše število množenj, ki ga potrebujemo za to?

a)

5

b)

12

c)

6

d)

18

2.

Kakšna je časovna zahtevnost algoritma, ki optimalno postavitev oklepajev pri množenju matrik najde tako, da preizkusi vse možne postavitve?

a)

linearna

b)

logaritmična

c)

kvadratna

d)

eksponentna

3.

Pri množenju matrik $A_0\cdot A_1\cdot...\cdot A_{n-1}$ je dimenzija matrike $A_i$ enaka $d_i\times d_{i+1}$ . Matrike razdelimo na 2 dela:

$B\ =\ A_0\cdot...\cdot A_i$ ,
$C\ =\ A_{i+1}\cdot...\cdot A_{n-1}$ .

$R_2$ je najmanjše število množenj, ki jih potrebujemo, da pomnožimo matrike v $C$ , $R_2$ pa je najmanjše število množenj, ki jih potrebujemo, da pomnožimo matrike v $C$ . Koliko množenj potrebujemo, da pomnožimo vse matrike ( $A_0\cdot...\cdot A_{n-1}$ )?

a)

$R_1\cdot d_0\cdot d_{i+1}\cdot d_{n-1}\cdot R_2$

b)

$R_1+d_0\cdot d_{i+1}\cdot d_{n-1}+R_2$

c)

$R_1+d_0+d_{i+1}+d_{n-1}+R_2$

d)

$R_1+R_2$

4.

Množimo matrike $A_0\cdot...\cdot A_{n-1}$ , pri tem je $A_i\ :\ d_i\ \times\ d_{i+1}$ dimenzionalna matrika. $N_{i,k}$ je najmanjše število množenj, ki jih potrebujemo za $A_i\ \cdot...\cdot\ A_k$ . Kaj je karakteristična enačba za $N_{i,j}$ ?

a)

$N_{i,j}=\min_{i\le k<j}\left\{N_{i,k}+N_{k+1,\ j}+d_i\cdot d_{k+1}\cdot d_{j+1}\right\}$

b)

$N_{i,j}=\max_{i\le k<j}\left\{N_{i,k}+N_{k+1,\ j}+d_i\cdot d_{k+1}\cdot d_{j+1}\right\}$

c)

$N_{i,j}=\min_{i\le k<j}\left\{N_{i,k}\cdot N_{k+1,\ j}\cdot d_i\cdot d_{k+1}\cdot d_{j+1}\right\}$

d)

$N_{i,j}=\min_{i<k\le j}\left\{N_{i,k}+\ N_{k+1,\ j}+\ d_i\cdot d_{k+1}\cdot d_{j+1}\right\}$

5.

Naj bo $M_{0\ }:\ 2\ \times5$ dimenzionalna matrika, $M_1\ :\ 5\times3$ dimenzionalna matrika, $M_2\ :\ 3\ \times\ 6$ dimenzionalna matrika in $M_{3\ }:\ 6\ \times\ 7$ dimenzionalna matrika. Čemu je enak $N_{0,2}$ ?

a)

150

b)

66

c)

231

d)

30

6.

S katerim številom dopolnimo osenčeno mesto?

a)

18

b)

28

c)

29

d)

60

e)

20

7.

Najmanj koliko množenj realnih števil potrebujemo, da zmnožimo vse matrike?

a)

82

b)

100

c)

230

d)

Nič od tega

8.

Vsaj koliko množenj potrebujemo, da zmnožimo od 1. do vključno 3. matrike.

(Matrike začnemo šteti z 0)

a)

36

b)

56

c)

70

d)

82

9.

V kakšnem vrstnem redu moramo postaviti oklepaje, da za izračun produkta vseh 5 matrik porabimo optimalno število množenj realnih števil?

a)

$\left(\left(A_0\cdot A_1\right)\cdot\left(A_2\cdot\left(A_3\cdot A_4\right)\right)\right)$

b)

$\left(\left(A_0\cdot A_1\right)\cdot\left(\left(A_2\cdot A_3\right)\cdot A_4\right)\right)$

c)

$\left(\left(\left(A_0\cdot A_1\right)\cdot A_2\right)\cdot\left(A_3\cdot A_4\right)\right)$

d)

$\left(\left(A_0\cdot\left(A_1\cdot A_2\right)\right)\cdot\left(A_3\cdot A_4\right)\right)$

Optimalno matrično množenje

Total questions: 9

Worksheet time: 7mins

Similar Resources on Wayground