Vektory a matice Vektory Vektor je lineární posloupnost prvků V, která obsahuje n prvků. Každý prvek vektoru V je přístupný prostřednictvím indexu r (rank) v rozsahu [1, n]. Vektor připomíná datový typ pole, ale není to pole. V:
P1
P2
P3
Pr
Pn
1
2
3
r
n
Operace s vektorem Prvek na pozici (r) – operace vrací prvek Pr vektoru V na pozici r. V:
P1
P2
P3
Pr
Pn
1
2
3
r
n
Záměna prvku (r, Px) – operace zamění prvek Pr vektoru V na pozici r prvkem Px. V:
P1
P2
P3
1
2
3
Pr
Pn
r
n
Px
Vložení prvku (r, Px) – operace vloží prvek Px na pozici r vektoru V. Nejprve je potřeba vytvořit místo pro nový prvek přesunem prvků na pozicích r až n o jednu pozici vpravo. Rozsah vektoru (n) se zvýší o jedničku. V:
P1
P2
P3
Pr
Pn
1
2
3
r
n
Poté se vloží prvek Px na uvolněnou pozici r. V:
P1
P2
P3
1
2
3
Pr Px
-1-
r
Pn-1 n
Odstranění prvku (r) – operace odstraní prvek Pr vektoru V na pozici r. Nejprve se odstraní prvek Pr na pozici r. Poté se posunou všechny prvky na pozicích r+1 až n o jednu pozici vlevo. Rozsah vektoru (n) se sníží o jedničku. V:
P1
P2
P3
Pr
Pn
1
2
3
r
n
Odstranění vektoru – operace odstraní celý vektor V. Opakujeme operaci odstranění prvku (r) až do snížení rozsahu vektoru (n) na nulu (n=0)
Implementace vektoru Implementace vektoru se provádí obvykle pomocí pole pevné nebo proměnné délky. Implementaci je možné provést i pomocí spojového seznamu (viz spojové seznamy). Deklarace vektoru: type
Prvek = typ prvku;
var
Vektor: array [1..MAX] of Prvek; n: integer;
{integer, real, record, …}
Prvkem může být jakákoliv hodnota, tj. celé číslo (integer), reálné číslo (real), záznam (record) nebo jiná. Hodnota MAX udává maximální rozsah vektoru. Použití této hodnoty je nutné při deklaraci pole s pevnou délkou. Hodnota n udává skutečnou velikost vektoru v rozsahu n ∈ < 1, MAX >
Implementace operací s vektorem Prvek na pozici (r) function Prvek_na_pozici(r:integer):Prvek; begin Prvek_na_pozici:=Vektor[r] end; Záměna prvku (r, Px) procedure Zamena_prvku(r:integer;Px:Prvek); begin Vektor[r]:=Px end;
-2-
Vložení prvku (r, Px) procedure Vlozeni_prvku(r:integer;Px:Prvek); var i:integer; begin for i:=n downto r do Vektor[i+1]:=Vektor[i]; n:=n+1; Vektor[r]:=Px end; Odstranění prvku (r) procedure Odstraneni_prvku(r:integer); var i:integer; begin {zrušení prvku, například: Vektor[r]:=0} for i:=r to n do Vektor[i]:=Vektor[i+1]; n:=n-1 end; Instrukce pro zrušení prvku (uvolnění místa v paměti) není nutná u staticky alokovaných prvků, tj. u prvků, kterým je paměťové místo přiřazeno již při deklaraci. U dynamicky alokovaných prvků (paměť přidělena až za běhu programu) je instrukce zrušení prvku nutná. Odstranění vektoru procedure Odstraneni_vektoru; var i:integer; begin for i:=1 to n do Odstraneni_prvku(i) end; V případě staticky alokovaných prvků stačí pro zrušení celého vektoru instrukce: n:=0
-3-
Matice Maticí typu m×n nazýváme obdélníkové pole m×n prvků matice, uspořádaných do m řádků a n sloupců. Matice označujeme velkými písmeny, prvky matice odpovídajícími malými písmeny se dvěma indexy, přičemž první index udává číslo řádku, druhý číslo sloupce, ve kterém se prvek nachází. Je-li typ matice známý, lze používat stručný zápis A = (ai j). ⎛ a11 a12 a13 L a1n ⎞ ⎜ ⎟ ⎜ a21 a22 a23 L a2 n ⎟ A=⎜ M M M M M ⎟ ⎜ ⎟ ⎜a ⎟ ⎝ m1 am 2 am 3 L amn ⎠ Na základě vlastností (rozměry matice, typ prvků) matice je možné zavést následující pojmy (známé z lineární algebry): Matici typu (1×n) budeme nazývat řádkovým vektorem (o n složkách) a matici typu (m×1) budeme nazývat sloupcovým vektorem (o m složkách).
Ař = (a1
a2 L an )
⎛ a1 ⎞ ⎜ ⎟ ⎜a ⎟ As = ⎜ 2 ⎟ M ⎜ ⎟ ⎜a ⎟ ⎝ m⎠
Prvky matice se stejnými indexy (aii) tvoří hlavní diagonálu matice.
⎛ a11 ⎜ ⎜a A = ⎜ 21 M ⎜ ⎜a ⎝ m1
a12
a13
a 22
a 23
M
a ii
am2
am3
a1n ⎞ ⎟ L a2n ⎟ M M ⎟ ⎟ L a mn ⎟⎠ L
Má-li matice všechny prvky pod (respektive nad) hlavní diagonálou rovny nule, nazýváme matici horní (respektive dolní) trojúhelníkovou maticí.
⎛ a11 ⎜ ⎜ 0 AH = ⎜ M ⎜ ⎜ 0 ⎝
a12 a 22 M 0
L a1n ⎞ ⎟ L a2n ⎟ M M ⎟ ⎟ L a nn ⎟⎠
⎛ a11 ⎜ ⎜a AD = ⎜ 21 M ⎜ ⎜a ⎝ n1
0 a 22 M an2
0 ⎞ ⎟ L 0 ⎟ M M ⎟ ⎟ L a nn ⎟⎠ L
Matici, která má stejný počet řádků, jako sloupců, nazýváme čtvercovou maticí.
⎛ a11 ⎜ ⎜a A = ⎜ 21 M ⎜ ⎜a ⎝ n1
a12 a 22 M an2 -4-
L a1n ⎞ ⎟ L a2n ⎟ M M ⎟ ⎟ L a nn ⎟⎠
Matici, jejíž všechny prvky jsou rovny nule nazýváme nulovou maticí. ⎛0 0 L 0⎞ ⎟ ⎜ ⎜0 0 L 0⎟ A=⎜ M M M M⎟ ⎟ ⎜ ⎜0 0 L 0⎟ ⎠ ⎝
Čtvercovou matici, která má všechny prvky mimo hlavní diagonálu rovny nule nazýváme diagonální maticí. Diagonální matici, která má na hlavní diagonále všechny prvky rovny jedné nazýváme jednotkovou maticí a označujeme ji E. ⎛ a11 ⎜ ⎜ 0 A=⎜ M ⎜ ⎜ 0 ⎝
0 a 22 M
0
0 ⎞ ⎟ L 0 ⎟ M M ⎟ ⎟ L a nn ⎟⎠ L
⎛1 0 L 0⎞ ⎟ ⎜ ⎜0 1 L 0⎟ E =⎜ M M M M⎟ ⎟ ⎜ ⎜0 0 L 1⎟ ⎠ ⎝
Transponovanou maticí k matici A = (ai j) typu (m×n) rozumíme matici AT = (bij) typu (n×m), pro jejíž prvky platí bij = aji. Čtvercovou matici A nazveme symetrickou, jestliže pro ni platí A = AT.
⎛ a11 ⎜ ⎜a A = ⎜ 21 M ⎜ ⎜a ⎝ m1
a12
a13
a 22
a 23
M
M
am2
a m3
⎛ b11 ⎜ ⎜ b21 T A = ⎜ b31 ⎜ ⎜ ⎜b ⎝ n1
a1n ⎞ ⎟ L a2n ⎟ M M ⎟ ⎟ L a mn ⎟⎠ L
= a11
b12 = a 21
= a12
b22 = a 22
= a13
b32 = a 23
M
= a1n
M
bn 2 = a 2 n
b1m = a m1 ⎞ ⎟ L b2 m = a m 2 ⎟ L b3 m = a m 3 ⎟ ⎟ M M ⎟ L bnm = a mn ⎟⎠ L
Sčítání a násobení matic Součinem celého čísla α a matice A = (aij) typu (m×n) nazýváme matici α ⋅ Α = (α ⋅ ai j) typu (m×n).
⎛ α ⋅ a11 α ⋅ a12 ⎜ ⎜ α ⋅ a21 α ⋅ a22 α⋅A=⎜ M M ⎜ ⎜α ⋅ a α ⋅ am 2 m1 ⎝
α ⋅ a13 α ⋅ a23 M
α ⋅ am 3
L α ⋅ a1n ⎞ ⎟ L α ⋅ a2 n ⎟ M M ⎟ ⎟ L α ⋅ amn ⎟⎠
Součtem matic A = (aij) a B = (bij) stejného typu (m×n) nazýváme matici A + B = (ai j + bi j) typu (m×n).
⎛ a11 + b11 ⎜ ⎜ a +b A + B = ⎜ 21 21 M ⎜ ⎜a + b ⎝ m1 m1
a12 + b12
a13 + b13
a 22 + b22
a 23 + b23
M
M
am 2 + bm 2
-5-
am 3 + bm 3
a1n + b1n ⎞ ⎟ L a2 n + b2 n ⎟ ⎟ M M ⎟ L amn + bmn ⎟⎠ L
Rozdílem matic A a B stejného typu (m×n) nazýváme matici A + (−1) ⋅ B typu (m×n). Označujeme ji A − B.
⎛ a11 ⎜ ⎜a A − B = ⎜ 21 ⎜ ⎜a ⎝ m1
− b11
a12 − b12
a13 − b13
− b21
a 22 − b22
a 23 − b23
M
M
M
− b m1
a m 2 − bm 2
a m 3 − bm 3
a1n − b1n ⎞ ⎟ L a 2 n − b2 n ⎟ ⎟ M M ⎟ L a mn − bmn ⎟⎠ L
Součinem matic A = (aij) typu (m×n) a B = (bij) typu (n×p) nazýváme matici C = (ci j) typu (m×p), pro jejíž prvky platí: n
cij = ∑ aik ⋅ bkj
(i = 1,..., m; j = 1,..., p )
k =1
Označujeme C = A ⋅ B. Prvek ci j je skalárním součinem i-tého řádku matice A a j-tého sloupce matice B. Násobení matic není komutativní, tj. obecně A ⋅ B ≠ B ⋅ A.
⎛ a11 ⎜ ⎜a A = ⎜ 21 M ⎜ ⎜a ⎝ m1
a12
a13
a 22
a 23
M
M
am2
a m3
a1n ⎞ ⎟ L a 2n ⎟ M M ⎟ ⎟ L a mn ⎟⎠ L
⎛ b11 ⎜ ⎜ b21 B = ⎜ b31 ⎜ ⎜ M ⎜b ⎝ n1
b12 b22 b32 M bn 2
L b1 p ⎞ ⎟ L b2 p ⎟ L b3 p ⎟ ⎟ M M ⎟ L bnp ⎟⎠
⎛ c11 = (a11b11 + a12 b21 + L + a1n bn1 ) c12 L c1 p = (a11b1 p + a12 b2 p + L + a1n bnp ) ⎞ ⎜ ⎟ ⎜ c21 = (a 21b11 + a22 b21 + L + a 2 n bn1 ) c22 L c2 p = (a 21b1 p + a 22 b2 p + L + a 2 n bnp ) ⎟ C = A⋅ B = ⎜ ⎟ M M M M ⎜ ⎟ ⎜ c = (a b + a b + L + a b ) c L cmp = (am1b1 p + a m 2 b2 p + L + amn bnp ) ⎟⎠ m1 11 m 2 21 mn n1 m2 ⎝ m1
-6-
Implementace matice Implementace matice se provádí obvykle pomocí dvojrozměrného pole . Implementaci je možné provést i pomocí spojového seznamu. Deklarace matice: type
Prvek = typ prvku; {integer, real, record, …} Matice = array [1..Max_M, 1..Max_N] of Prvek;
var
m, n: integer
Prvkem může být jakákoliv hodnota, tj. celé číslo (integer), reálné číslo (real), záznam (record) nebo jiná. Hodnoty Max_M a Max_N udávají maximální velikost matice (počet řádků a sloupců). Použití těchto hodnot je nutné již při deklaraci matice. Hodnoty m a n udávají skutečnou velikost matice v rozmezí m ∈ < 1, Max_M>, n ∈ < 1, Max_N>
Implementace vybraných operací s maticemi Stanovení transponované matice AT k matici A function Transponovana(A:Matice; m,n:integer):Matice; var i,j:integer; begin for i:=1 to m do for j:=1 to n do Transponovana[j,i]:=A[i,j] end; Součin celého čísla α a matice A function Soucin(alfa:integer; A:Matice; m,n:integer):Matice; var i,j:integer; begin for i:=1 to m do for j:=1 to n do Soucin[i,j]:=A[i,j]*alfa end; Součet a rozdíl matic A a B function Soucet(A,B:Matice; m,n:integer):Matice; var i,j:integer; begin for i:=1 to m do for j:=1 to n do Soucet[i,j]:=A[i,j]+B[i,j] end;
Pro rozdíl matic stačí pozměnit tělo cyklu: Rozdil[i,j]:=A[i,j]-B[i,j] -7-
Násobení matic A a B function Nasobeni(A,B:Matice; m,n,p:integer):Matice; var i,j,k:integer; Pom: Prvek; begin for i:=1 to m do for j:=1 to p do begin Pom:=0; for k:=1 to n do Pom:=Pom+A[i,k]*B[k,j]; Nasobeni[i,j]:=Pom end; end;
Při návrhu algoritmu byla uplatněna optimalizační metoda odstranění opakovaných výpočtů (použití proměnné Pom místo opakovaného použití prvku pole Nasobeni[I,J]), přesto má algoritmus pro násobení matic obvykle kubickou asymptotickou operační složitost, tj. operační složitost roste stejně rychle jako funkce x3.
-8-
