. : - , , , , . - , , -. , , , , − - , , . - , , , - , , , , - − , -.
- − , -, , , , .
-, . ( ), , , ( ) . , . , . , ∕ , - , . -, , - , , - , . , , , .
, , - , . - -, , , , ( -). - . , , , - , , . , , .
|
|
. 11 . 12 : -. , 13 - .
11.
1.
2.
3.
4.
5. 2´2 2´ n
6.
- . , , . .
(, A B). , . - , . . , A -, B, B , A. , , A , - . - , B A - ( ); A B. A , B .
, 1 m A 1 n B. A Q m ´ n: i Î{1,..., m } j Î{1,..., n }, A qij - Q, i - j - -. , B A. , B i Î{1,..., m } j Î{1,..., n } - qij. , , ). , - - .
|
|
Q A B. , i Î{1,..., m }. A , (.. j) B, , -
gi = . (1)
, A i Î{1,..., m }, gi. i *,
= . (2)
, i Î{1,..., m } , (2), j. Q. i *, - (2), A ( i * , gi i Î{1,..., m }).
, , - . , - Q, V -.
B . , -
j Î{1,..., n }. B , ,
, -
fj = . (3)
, B j Î{1,..., n }, - fj. j *,
= . (4)
, Q. j *, - (4), B ( - j * , fj j Î{1,..., n }).
, B, - . , - Q, V +.
Q
≤ (5)
, (2) (4),
V - ≤ V +.
, B.
, . V = V -= V +. .
1. 1) V -= V + , Q i* - j* - , .. i Î{1,..., m } j Î{1,..., n }
≤ ≤ . (6)
2) V ; 3) i* j* ■
á i*, j* ñ, 1, - . á i*, j* ñ Q - V. Q, i* - j* - , - Q.
, (6) - , . 1- , - 2- . , á i*, j* ñ, 1, - .
|
|
. - , 4 - .
1. :
Q = . (7)
, (1) (2), . - (1)
g 1= = min{7, 6, 5, 4} = 4;
g 2= = min{1, 8, 2, 3} = 1;
g 3= = min{8, 1, 3, 2} = 1.
(2) = max{4, 1, 1}, , i * = 1 V -= 4.
, (3) (4), . - (3)
f 1= = max{7, 1, 8} = 8;
f 2= = max{6, 8, 1} = 8;
f 3= = max{5, 2, 3} = 5;
f 4= = max{4, 3, 2} = 4.
(4) = min{8, 8, 5, 4} = 4, , j * = 4 V += 4.
, . - 1, 4 = q 14. á1, 4ñ Q ■
2. :
Q = , (8)
, q 24, 1.
, (1) (2), . - (1)
g 1= = min{7, 6, 5, 4} = 4;
g 2= = min{1, 8, 2, 5} = 1;
g 3= = min{8, 1, 3, 2} = 1.
(2) = max{4, 1, 1}, , i * = 1 V -= 4.
, (3) (4), . - (3)
f 1= = max{7, 1, 8} = 8;
f 2= = max{6, 8, 1} = 8;
f 3= = max{5, 2, 3} = 5;
f 4= = max{4, 5, 2} = 5.
(4) = min{8, 8, 5, 5} = 5, , - j * {3, 4} V + = 5.
, , 1, . Q , , ■
2. a ( ) Q , a ■
2 Q .
1. , . , ; . . 1 2
| |||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
■
|
|
. s A - t, s - , - t - . A - s, t , B. s B t, s - , t - . B s, t , A. s ( ) t, ( ) . , , .
3.
A 1 2, B 6 3, 4 5, 4 5 - . - , - :
|
|
■
3. - , . - ( ) ■
, - , . - 3 4´6 3´4.
4. :
1- 2- , . 1- :
1- 4- 3- . -
1- 2- . 2- - á28, 18, 33ñ, , B 2- , - 18, .. 1´1, - 18. , , á2, 3ñ , 18.
, , . 1-
, 1- 3- , á28, 18, 38, 33ñ, 18, - 1´1, .. 18 ■
4 .
4. , ■
2. (. 3 4)
| |||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
■