Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.intsys.msu.ru/magazine/archive/v10(1-4)/andreev-095-140.pdf Äàòà èçìåíåíèÿ: Thu Jun 21 03:34:12 2007 Äàòà èíäåêñèðîâàíèÿ: Tue Oct 2 00:06:17 2012 Êîäèðîâêà: Ïîèñêîâûå ñëîâà: m 74

. . , . .



, . , . , . .


. A, - qi , i {1, 2, . . . , m}. - x j , j {1, 2, . . . , n}. , = (a 1 , a2 , . . . , an ) qi . Ti . T , T i , A. , , , , Ti . , . Ti , , , qi . , T i , , , ,


06-01-00240.


96

. . , . .

, . . : T Ti , , A, . , A. , A. . , , . , A , . , -. , T i . , T , = (a 1 , a2 , . . . , an ), , , q A. . . . . [1] , , , T , . T . , Ti, Ti , , , T Ti, . T , Ti, Ti , i = i . , T . , T . (T ) T . .




97

. A , T T , T T , , . . . , . . . . [2] (T ). p j xj , ,
n


j =1 n

pj xj , di Ti -


j =1

pj xj di

= (a1 , a2 , . . . , an ) Ti . . . . [3] , n


j =1

pj xj -

. . [4], . . , q A. , (T ), T , , T i , (T ) (T ). , Tj , , Ti, . , (T ). (T ) , () = (k1 , . . . , km , km+1 ), ki , Ti i = 1, 2, . . . , m, km+1 .


98

. . , . .

, , (T ). kl T l l m, km+1 T ; , (T ) (T ) . , . . . , , . , . T . . , , T T , K T M T , . K T . , , . , , , [5], , , , , [6]. . . , . , r , [7].




99

,

, T T , K T M T , . .

1) T , T i . 2) . 3) , T T . 4) 3. 5) , T . 6) T , . 7) T . 8) 1­7 T i T . 9) 1­8 T . 1 2 , T Ti , [8] [9], . , T , , . . [10] , T ; , . , . . 1, 2, 6, 7, 9.


100

. . , . .

. . . . . . . [11]. , : · ; · ; · 4, Ti , (T ) (T ) ; · ; · ; · 1, 2, 6, 7 T . , . . , 1, 2, 3, 6, 7, 8 9, . . . , , , , . . . [12]. , . T m , T log m - log log m. . . , T , , : · T1 T2 ;




101

· T1 T2 1 ; 2 · T1 T2 ; · , , , .

, , , T1 T2 . 7. , 3 5. . . , , T : · · · ; ; .

, 2 9. 1­9 T . , . 6 7 . . [13]. . . . , . . . . . . . [14] , T .


102

. . , . .

, , , . . , T , , 20. . . T . . . 200 50 . . . 200 200 . . . 500 500 . . , T i T . . . A r . Q a E k = {0, 1, . . . , k - 1}, f (a1 , . . . , ar ) k - . , , (a 1 , . . . , ar ) (a1 , . . . , ar ). (a 1 , . . . , ar ) f . , f , , A. , . , f r , L K (r, ), f LK (r, ) , f , A, f , . . . . [15], LK (r, ) , -




103

, , . . . [9]. . . [16], L C (r, ), 2 LC (r, ), C . . , , . [17]. , , . T . T . , k - . , .

1.
. . 6 7. T m n , a ij
s

Ek = {0, 1, . . . , k - 1}, k

2. m =
i=1 m1 ,

mi , m

i

-

mi 1; m ~ m2 , . . . , ms . (k ) Mm,n,s T , s Ti ~ mi , T .
l

l {1, 2, . . . , s} m (l) =
i=1

mi , m (l) = m (l) - ml + 1.

, M

(k ) m,n,s ~

Tl


104

. . , . .

m (l), m (l + 1), . . . , m (l). t (T ) T . = (aj1 , aj2 , . . . , ajn ) = (aj1 , aj2 , . . . , ajn ) T , = (aj1 aj1 , aj2 aj2 , . . . , a
s-1 s-l j
n

ajn ).
T

(1)

h =
l=1 t=1

ml m

l+t

, L

buv ,

u {1, 2, . . . , h}, v {1, 2, . . . , n} , Ti Ti , , i < i . LT , , , , T j1 , j2 , l1 , l2 , , , j1 < l1 , j2 < l2 . LT T . buv Lt N (u, v ) = (v - 1) · h + u. A , T . a A . = {R1 , R2 , . . . , Rg }, RW LT , W = {1, 2, . . . , g }. R, B1 , B2 , . . . , Bp p 2. Q . , Q t (T ) - , Q t (T ). Q(t) , t {1, 2, . . . , p} , B1 , B2 , . . . , Bt-1 , Bt+1 , . . . , Bp . {B1 , B2 , . . . , Bp } : Q(t) Q . 1. g = u RW LT W . L T B1 B2 : · H LT B1 , LT H , 1;




105

· H LT B2 , H H , H B1 . L T , B1 B2 . t (T ). j1 , j2 , . . . , jr T , L T , B 1 B2 . 2. b uv bu v LT , buv = bu v = 0. D r LT , : 1) r = 1; 2) r > 1 D . L T S (LT ). g = h · n, RW LT W {1, 2, . . . , g } (D ) LT , D R. , D B1 , D S (LT ). D = {bu1 v1 , bu2 v2 , . . . , bur vr }, D B2 , : 1) (D ) B1 ; 2) {b
u1 v
1

,b

u2 v

2

,...,b

ur v

r

} S (LT ), u

t

pt t {1, 2, . . . , r }.

D L T , D B1 B2 . B (LT ) LT . B (LT ). T = (j1 , j2 , . . . , jr ) D B (LT ) , (D ) LT j1 , j2 , . . . , jr . , B (LT ) t (T ) ,


106

. . , . .

. , B (L T ) t (T ). Q A . B = {B1 , B2 , . . . , Bp } B = {Bi1 , Bi2 , . . . , Bij } , B B . Qi1 ,i2 ,...,il , Bi1 , Bi2 , . . . , Bil . A Qi1 ,i,...,il Q , Qi1 ,i2 ,...,il B t , t {1, 2, . . . , p} \ {i1 , i2 , . . . , il }. Qi1 ,i2 ,...,il A. |M | M , M (a, T ) = |Qi1 ,i2 ,...,il |, (k ) Nm,n Mm,n,s . ~ A N m,n , T Nm,n µ(A, T ) |
t

(T )|

(2)

m, n . , T . , t (T ), , [10], A 1 . A1 t (T ) , 1 B1 . µ(A, T ), T , | t (T )|. t (T ) 1 . A1 B1 µ(A, T ) = |S (T )|. , A 1 |S (T )| | t (T )|. .




107


k = (a, b), b = 1 log 2 m, n

1. > 1, < 1 , (m1 , m2 ) n k (m1 ,m2 ) , 2 1 1 a = 2 log k (m1 m2 n) - 2 logk logk (m1 m2 n) - logk log k log k n, 1 k (m1 m2 n) - 2 log k log k (m1 m2 n) + log k log k log k n, T Mm |S (LT )| |
t

(T )|
r
k

[m1 m2 n(k - 1)]r . r !k k2 n k
(m1 m2 )


(3)
1 2

, (m1 m2 )



, > 1, <
(k )

A1 F m1 ,m2 ,n . (k ) 1 F m1 ,m2 ,n , (k ) T Fm1 ,m2 ,n (k)1 .
|F

|S (LT )| | t (T )|. , 1 |S (L T )| | t (T )| , , , |S (L T )| | t (T )| . , | t (T )| (2) T Mm,n,s , s = m, ~ . . . . [8], [9], | t (T )| , 1, , | t (T )| . (T ) . . , t A1 . T , , , , , , 6 7, . , .

m1 ,m2 ,n

|


108

. . , . .

. . [13] (k ) T Mm,n,s ~ . q , 1 q < n ( q n ). W q {j1 , j2 , . . . , jq }, jt {1, 2, . . . , n} t {1, 2, . . . , q } j1 < j2 < . . . < jq . Wq . W = {j1 , j2 , . . . , jq } TW T , j1 , j 2 , . . . , j q . TW A2 , TW . Wq t (T ). i {1, 2, . . . , h}, h LT Tu , Ui {l 1 , l2 , . . . , li }, lt {1, 2, . . . , h} t {1, 2, . . . , i} l 1 < l2 < . . . < li . u Ui . T , = {j1 , j2 , . . . , jr }, u-, u l 1 , l2 , . . . , lr , N [l1 , j1 ], N [l2 , j2 ], . . . , N [lr , jr ] LT . u- T (T , u). A1 , . T Wq , Ui . u = {l1 , l2 , . . . , li } LT (u) LT , l 1 , l2 , . . . , li . LT (u) A 1 , (T , u). U i t (T ). . . , , .




109

. t,j (T ) , xj , j (T , u) (T , u), xj , : p(xj ) = pi (xj ) = 1 i Cn | (T )| , | (T )| | i (T , u)| , | (T , u)|
t,j
i

(4) (5)

uU
i

| p (xj ) = ¯
i uU uU

i

(T , u)| , (6)

| (T , u)|
i

pi (xj , u) = ¯ u Ui .

| i (T , u)| , | (T , u)|


(7)

2. u Ui , n k (m1 m2 ) , < 1 , m, n 3 : logk (m1 m2 ) log3 n 0, 0, (8) logk n i T M
(k ) m,n,s ~

n

logk n . (9) 2n , . ¯ p(xj ) pi (xj ) pi (xj )

2.
. . 1, 2, 6, 8, 9, . . .


110

. . , . .

, , , . . A B AB = {f |f : B A}. f AB C B , f (c) = {b|b = f (a), a C }; a A C A, f -1 (a) = {b|f (b) = a} f -1 (c) = f -1 (a).
aC

AB = {f |f AB , f (b) = a}. f AB , g B C , f g AC (f g )(x) = f (g (x)). A B (a, b), a A, b B ; A â B {(a, b)}, a = b. A (2) A â A. A , 1 A 0A , A , 1 0 E 2 ; x, y A, A (y ) = 1, x = y , 1A (y ) = 0, x = y ; , 0 A (y ) = 1x x x 1A 1A , x A. A = {1A |x A}, A = A {1h }. ~ ~ x x < E A . a, b E A , a b = a b 1A ; |a| = |a-1 (1)|; (a, b) = |a b| = |A| - |a b|. m 1 Lm = {1, 2, . . . , m}. n E2 , n- , F Lm . , i- a a(i), n A A
L
m

. E =



En,

n Er = {x|x E n , |x| = r }. 1n = 1Ln , 0n = 0Ln ; 1n = 1Ln , i i n = 0Ln , i L ; n = Ln , n = Ln . a E n , 0i ~ n~ i

n=1

a L

L n

|a|

k -1 j =1

k

, a (i) = k ,

a(j ) < i, i =
j =1

a(j ).

. a, b E n , b , n a, b a . a E2 a (E |a| )En , , P a (b) = b . Pr a r , . V (G) X (G) , , G. , X (G) V (G)(2) . G (x) x, (G) , (G) -




111

, d(r, G) r - . k (G) , k (G) , . p(G) = |V (G)|, q (G) = |X (G)|, p (G) = p(G) - k (G) + 1. U M = {V1 , V2 , . . . , Vk }
k

, M U ,
i=1 k (2) i

Vi = U .

G(M ) U U
(2)

\
i=1

V

.

U -, n , n (E2 )U . M U , M ,n n (T , M ), T (E2 )U ; V (G) = U , G,r (T , G) , T (E n )U . G-, . U , M = {V 1 , n V2 , . . . , Vk } G U . a E 2 : 1) (T , M ) M ,n , a1 , a2 U , T (a1 ) T (a2 ) a, i Lk , a1 , a2 Vi ; 2) (T , G) G,n , a1 , a2 G T (a1 ) T (a2 ) a; 3) T (E n )U , b U T (b) a. a (T , M ) ( (T , G), T ) , b E n , b a, (T , M ) ( (T , G), T ). T (E n )U U (2) T (2) , (2) ({a , a }) = T (a ) T (a ). (T , G) T 12 1 2 G,n TG = T (2) X (G) ; (T , M ) M ,n , T U -, M U , TM = TG(M ) (T , M ). .


112

. . , . .

3. : 1) a ( ) (T , M ), T U -, M U ; 2) a (T , G(M )); ( )

3) a ( ) T M . N , R R+ , , , , M R R ++ , lim (x) = 0,
1 B = {D |D = , M}. , , = n n n , , n 0 . , M , B (1 + (n))A, n B n A ( n ); B n A A n B , A n B ( n ). c1 A B c2 A ( c1 A B c2 A), c1 , c2 R+ , n n B A ( B n A). M , A (n)B , n A n B . , (G, n) n (T , G) (G,n) , M , (T , G) (G,n) ( (G, n) ), , (n). AG,n BG,n , (G,n) , AG.n .. BG.n ( , n M , (T , G) (G,n) , AG.n (T , G)(1 - (n)) BG.n (T , G) (1 + n (n)). AG.n (T , G) (n)). .. , =.. , .. . . n n n T ,T T ,T T , G,n G,n,r , r (T , G). log x log 2 x. (x) = -r (log x - log log x)/2 (x) = (log x - log log x)/2, H (m, r ) = e -m·2 (1 - -r r e-mr·2 ) . x, m n ^ , 0 x n, H (n, m, r ) = n H (m, r ). 0 x n x x



n x

113

(n+1) = (x+1)(n-x+1) , -, n , x = 0. , , ^ ^ x, H (n, m, x + 1) = H (n, m, x - 1) (1, n - 1), r (n, m) , r (n, m) = 1. 1 (0, 16 ) D B , D (n) log log log n. n D (G, n) :

1)

d(p (G) - 1, G) · (p (G) - 1)!2-(p (G)-1) , q (G) < D (n) log 2 n, P (G) - 1 (n) - D (n);

n p (G)-1



2

2) ] min(P (G) - 1, (n · q (G)) + D (n))[, n -r 2 r = [(n) - D (n)], r d(r, D )r !2 q (G) D (n) log 2 n. : ^1 1) rD (G, n) = rD (G, n) = p (G) - 1, ^2 q (G) < D (n) log 2 n, p (G) - 1 2) rD ^1 rD ^2 (n) - D (n);

(G, n) = [(n) - D (n)], (G, n) = ] min(P (G) - 1, (n · q (G)) + D (n))[, q (C ) < D (n) log 2 n, p (G) - 1 > (n) - D (n);

3) rD (G, n) = [(n)(nq (G) - D (n))], ^1 rD (G, n) = [(n)(nq (G) + D (n))], ^2 q (G) D (n) log 2 n. :
1 1) rD, (n, m) = [r (n, m) - D (n))], 2 rD, (n, m) = [r (n, m) + D (n))], m < n1+ ;

2) r 3) r

1 D ,

(n, m) = r
1+

2 D ,

(n, m) - 1 = [r (n, m)],
4 ln2 W

n
1 D ,

m 2

m<2
2

;

(n, m) = r

m

2 D , 4 ln n .

(n, m) - 1 = [(m)],


114

. . , . .

r

2 D ,

(n,m)



2 D ,

(n, m) =
r =r
1 D ,

(n,m)

n H (m, r ). r

(10)

rD, (G, n) = rD (G, n) ~1 ^1 rD, (G, n) = rD (G, n) ~2 ^2
1-

,

(11)

q (G)

n

; rD, (G, n) = r ~1 rD, (G, n) = r ~2
1 D , 2 D ,

(n, q (G)) (n, q (G))

,

(12)

q (G) > n

1-

. 1 (G, n), q (n) n1- D 1 ,(n, q (G)), q (n) > n D

D ,

(G, n) =

1-

(13)

.
1 4. (0, 16 ), c1 , c2 , 1 < c1 < c2 , D B , D (n) log log log n, : n

1) 1

q (G)
T .T . G,n

2

n(1-)

,
T .T . G,n,r

rD , (G,n) ~2 .. n r =rD , ~1 (G,n)



.. n



D ,

(G, n);

2) q (G)

2n D (n),
T .T . G,n

=

.. n

0;

3) f , (G, n), G n N , T .T : c1 2n q (G) c2 2n , G,n. .. f (G, n) ( n T .T G,n. =.. f (G, n)). n




115

(E n ) 1) L 2) L
min G,n min G,n

V (G)

L

min G,n

, :

(T ) = n + 1, (T , G) ; (T ) = min{r |
T .T . B ,n,r

(T ) = 0}

.

a a S (b, a) = log b - log ln log b S1 (b, a) = log b - log ln S (b,a) . 1 (0, 16 ) ( 1 , 1) 2

(1 - ) + log l + (1 - ) log (1 - ) = 0, D B , D (n) L
D , n

(14) (15)

log log n.

(G, n)1 :

1) ] log (G)[, p (G) (ln n) log ln n , (ln n) log ln n < p (G) (log n) 2) S
1 (G) 2

D (n)

(G) < 2((ln n) log ln n) 4 ;
3

3

,n + ,
D (n)

(ln n) log ln n < p (G) (log n)

(G) 2((ln n) log ln n) 4 ; (16)

3) [S ((G), n) + ], (log n)D(n) < p (G), q (G) < 2 (G) >

n-



(1 - )q (G)(ln q (G)) ; ln log n(G) q
n·


4) [S (q (G), n) + ], (log n)D(n) < p (G), q (G) < 2 (G) (log n)
D (n)

(17)
2n (log n)D

(1 - )q (G)(ln q (G)) ln( log n(G) q
n-


< p (G) 2
2 D ,

q (G) <

(n)

.

L

(G, n) : log n - D (n); log n + D (n);


1) ] log (G)[, p (G)


2) ] log max((G), 2D (n))[, log n - D (n) < p (G) 3) ] log p (G)[, log n + D (n) < p (G)

(ln n) log ln n;


116 4) S 2·
p (G) 2

. . , . .

1

, n + +1, (ln n) log ln n < p (G) (log n)
D (n)

D (n)

;

5) [S1 (q (G), n) + ] + 1, p (G) > (log n)

, q (G) )

2n (log n)D

(n)

.

x , 1 x 2 log n q (G) = ^ L1 , (G, n) D 1) [n - x + ], 2n (log n)D 2) n - 1, 2n ln n 3) n, q (G)
(n)

2n ·ln (n 2x -1

. -

q (G) q (G)

2n ln n; 2n (ln n + D (n));

2n (ln n + D (n)).
2 D ,

^ L ^ 1) L1 , (G, n) + 1, D 2n (log n)D(n) ^ 2) L1 , (G, n), D q (G)

(G, n), : 2n (ln n + D (n));

q (G) .

2n (log n)D

(n)

. 5. (0, 1) 1 q (G) L 2) (log n)
2 (log n) 1 D ,
n D (n)

1 16

) B B , D (n) ¢ log log n,

,
.. n

(G, n) q (G)
.. n

L

min D ,n
(n)

.. n

L

2 D ,

(G, n); p (G)
1+

(18) , (19)

D (n)

2n (log n)D

q (G)

[S (q (G), n) + ] 3) q (G)
2n (log n)D
(n)

L

min b,n

.. n

[S (q (G), n) + ] + 1;

,
.. n

^ L

1 D ,

(G, n)

^ L

min D ,n

.. n

^ L

2 D ,

(G, n).

(20)




117

. Lm,n = Lm Ln . T , m n , , T : Lm,n E . , m,n = E Lm,n , = m,n .
(m,n)N
2

^ T m,n , T Lm ,n , ^ (k ))(l) = T (k , l) (k , l) L m,n . x (T T m,n , ^ , , T .
m,n

= (E

m

\ {0m }) (E n \ {0n }).

(21)

(a, b) m,n a-1 (1) b-1 (1) Lm,n . T m,n (a, b) m,n , , , a, , b, T (a , b ) |a|,|b| , (T (a , b ))(i, j ) = T (a (i), b (j )). , T (a,b) , T (a,b) = T |a-1 (1)b-1 (1) . x E n , x b T(a,b) , x b , , T (a,b) . , , . A = (, F ), (m, n) (m, n), (m, n) m,n , F E , , :
n 1) {1m } (E2 \ {0n }) (m, n), (m, n) N 2 ; 2) F (T ) = 1, T , ; 3) (a, b) (m, n) x T (a, b), c, c a, ,

(c, x) (m, n); F (T
(c,x)

(22) (23)

) = 1.


118

. . , . .

A = (, F ) , (a, b) (m, n) : c a, x b, (c, x) (m, n) , (c a , x b ) (|a|, |b|). (24) GA (T ) VA (T ) = {(a, b)|(a, b) (m, n), F (T
(a,b)

) = 1} {(0m , 0n )}

(25)

XA (T ), {(a1 , b1 ), (a2 , b2 )}, a1 < a2 , b1 < b2 , |b2 | a1 < a < a2 , (a, b1 ) (m, n), b1 T (a, b1 ). A = (, F ) , T GA (T ) . 1) µ(A, T ) = |VA (T )|,

= |b1 | + 1; ,

2) µ (A, T ) x, c , (c, x) VA (T ). A B , A T µ(A, T ) µ(B , T ). B , (26)

A B . , , . . , § 1. , A = ( , F ), (m, n) = m,n , F (T ) = 1 , T . A . f H = {g |g N N , g (n) n}. k Cf ,p E k , p Lk , k N , 1k = C
k ,k k ,k -1 > ... > f > Cf k k (Cf ,p - Cf ,p-1 )(C k,p f

C

k ,1 f

>C

k ,0 f

= 0k ,

(27) (28)

(f (p))) = 1.




119

D (f ) : (k , n) = {(C
D (f ) k ,p f

, x) | p Lk , x E n \ {0n }};

(29)

T T
(C
k,k-1 f

k ,n

,F

D (f )

(T ) = 1, T

,

. D (f ) .

,1n )

6. A f H , D (f ) A, D (f ) A. f H D (f ) D = D (f0 ), f0 . T GD (T ) . , ^ ^ D . S LLl , S E n , S -1 (1) = n S (Ll ). D - T m,n t , t N , (t, K t , St , lt , At ), lt N , Kt Lmlt , St Ln lt , At lt ,n . ^ 1) T (1) 1n , T . . ^ ^ 2) t = 1, lt = 1, Kt (1) = 1, At (1) = T (1) 1n , St (1) = ^ (1))-1 (0). . 3). min(T ^ m~ ~ 3) = (T (1 ,St ) )-1 (1lt ). = , St , . 5); = , . 4); ^ 4) k = min ; i = (T
l i=1 r
i

L

L

(C

m,k f0

~ ,St ) -1 )

(1lt ); i (30)

t ^ ^ y = ( & ( T (r )))&(T (k ) 1n ).

y = 0n , . 5). t 1 : lt = l
t-1

^ + 1, At (lt ) = y , kt (lt ) = k ;
L

(31) (32) (33)

^ (Kt , St , At )

= (K
lt-1

t-1 -1

,S

t-1

^ , At-1 );

St (lt ) = min y . 3).

(1);


120

. . , . .

^ 5) Cr = (At (r ))-1 (Ln \ LSt (r) ). r Llt Cr = , . j0 = min Cr0 , r0 = min{r |Cr = }; t 1 : St (lt ) = min y St |
L
r0 -1

-1

(1);
r0 -1

(34) ; (35) (36)
L

=S

t-1 |L

St (r0 ) = j0 , lt = r0 ; ^ (Kt , At ) = (K
t-1

^ , At-1 )

;
r0

(37)

. 3). G ( X (G) L q(G) ), (A, ), A , (T , G) b,n A T G -1 . µ((A, ), (T , G)) = µ(A, TG -1 ), ^ µ . T T . 7. G G log q (G) n log2 n, µ((D , G ), (T , G)) = µ ((D , G ), (T , G))
.. n



TT G,n

(T , G).

(38)

3.
. . , . . . , T T1 T2 , . T , , : 1) , 2) ,




121

3) r , 4) r . , T i . , , 1 . 2 , . r , r , , r r , , , , . . , T (T ). , , (T ), , |(T ) (T )| |(T ) (T )| (39)

T T . ) , , . ), ) ) . , T , . , , , . , T1 T2 , .


122

. . , . .

. . D 1 D2 , , . D1 . . , D 2 , r . v1 ,v2 ,n T = (T1 , T2 ), Ti vi , i = 1, 2, . . . ^ T1 T2 n. T T . T n \ {on } v1 ,v2 ,n,x , x E2 ~ ~ , ~ v1 ,v2 ,n 1, x ~ T , 0 . r T1 ,v2 ,n,x , v ~ r T v1 ,v2 ,n , T1 ,v2 ,n , v n,r n E2 T , E2 r ,
n



T v1 ,v2 ,n,r

=
xE ~
n r



T v1 ,v2 ,n,x ~

,

T v1 ,v2 ,n

=
i=1



T v1 ,v2 ,n,r

.

(40)

T1T 2 ,n,x , 1, v ,v ~ x ~ T , 0 . T1T 2 ,n,r , r , T1T 2 ,n v ,v v ,v , K T 2 ,n,r v1 ,v r , K T T r . v1 ,v2
n



TT v1 ,v2 ,r

=
xE ~ r
n,r 2



TT v1 ,v2 ,x ~

,

TT v1 ,v2 ,r

=
r =1 r



TT v1 ,v2 ,n,r

,

(41)



KT v1 ,v2 ,n,r

=
j =1



T v1 ,v2 ,n

,

KT T v1 ,v2 ,n,r

=
j =1



TT v1 ,v2 ,n,j

.

(42)

{T , T T }, {T , T T , K T , K T T }, i L n , r Ln ,




123



,i v1 ,v2 ,n,r

=
xE ~
n,r 2


,x(i)=1 ~ n

v1 ,v2 ,n,x ~

,

(43)



,i v1 ,v2 ,n

=
r =1 r


j =1

,i v1 ,v2 ,r

, .

(44) (45)

K, ,i v1 ,v2 ,n,r

=

,i v1 ,v2 ,n,j

v1 ,v2 ,n v1,i 2 ,n,r , v1,i 2 ,n , ,v ,v , i- , ,i v1 ,v2 ,r



= =



v1,i 2 ,n ,v v1 ,v2 ,n , : · · · · ·
T ,i v1 ,v2 ,n TT v1 ,v2 ,n T ,i v1 ,v2 ,n,r T T ,i v1 ,v2 ,n,r K T T ,i v1 ,v2 ,n,r

,i v1 ,v2 ,n

,i v1 ,v2 ,n,r v1 ,v2 ,n,r v1,i 2 ,n ,v v1 ,v2 ,n

,

(46) (47)



.

,i v1 ,v2 ,n,r

i- T

; ; r ; r ; r .

, i = 1 i . n x E2 \ {on } |x| x. ~ ~ ~ ~ x : L|x| Ln , x (i) = ki , i L|x| , ki i- ~ ~ ~ ~ x. ~ n y E2 , ~ x, y x . ~ ~~ ~ n : E n E |x| , x E2 ~ x ~ 2 2 x (y ) = y x . ~~ ~~


124

. . , . .

n l, l Ln , x E2 1, ~ 0, x n,l . ~ (0, 1), (0, 1 ) , 2 ,n v1 ,v 2 T v1 ,v2 ,n ,

m

i

|(

n,1

Ti )

-1

(1)|

(1 - )mi ,

i L2 ,

(48) (49)

|(

n,1

Ti )

-1

(1)| = m1 m2 .

, , 2 ,n . , v1 ,v (0, 1 ) [2 - 22 , 1 - 2 + 22 ], 2 I . ,i ,T ,T ,T ,K T ,K T T v1 ,v2 ,n , v1 ,vT,n , v1 ,v2 ,n,r , v1 ,vT,n,r , v1 ,v2 ,n,r , v1 ,v2 ,n,r 2 2 , 2 ,n . v1 ,v r r
1,k

(m) = ] log m - (1 - ) log log m[,

(50) (51) (52)

2,k (m) = [log m - (1 + ) log log log m], r1,k (m) = [log m - (1 + ) log log m]. ~

, 8. c1 , c2 , c1 1 0, min( 32 , 20c2 ) , nc1 m1 m , 1 , 2 I

2

0 < c 1 < 1 < c2 , n c2 , m 1 n m 2 ,

1) (n, m1 m2 ),
,T T v1 ,v2 ,n

(n, m1 m2 ),

(53)

1 < 2 1 (n, m1 m2 ) 2)
,T v1 ,v2 ,n n

2 (n, m1 m2 );

(54)



.. 1 n 2

;

3) k (n, m1 m2 , r ),

r [r1,k (m1 m2 ), r ~

2,k

(m1 m2 )]

(55)




125


,K T v1 ,v2 ,n,r



.. n



,K T T v1 ,v2 ,n,r





.. ,T v1 ,v2 ,n,r .. n n .. ,T T .. v1 ,v2 ,n,r n k n 2,k

(n, m1 m2 , r ); (56)

1 < 2 r [r1,k (m1 m2 ), r ~
k 1 (n, m1 m2 , r )

(m1 m2 )], (57)

n

k 2 (n, m1 m2 , r );

1 <

1 2

r [r1,k (m1 m2 ), r2,k (m1 m2 )], ~ ~
k (n, m1 m2 , r ) n 1.

(58)

8 , . : 1) . 2) 1 . 2 3) ( ) . 4) , , , . , , (log m - log log m, log m - log log log m), . .


126

. . , . .

21 ,v2 ,n = v1 ,v2 ,n v1 ,v2 ,n v p{(T , T )} = 2 · p (T , T )
(T ,T ) ~

(1 - p)

(|V1 |+|V2 |)n-(T ,T )-(|V1 |+|V2 |)n ~ v1 ,v2 ,n

,

(59)

T T
r

, (60)

(T , T ) = ~
i=1 aV
i

(Ti (a), Tj (a)).

, T p , T . T T T T 21 ,v2 ,n v1T ,& , v1T ,,n , v1T ,&,n,r , v1T ,,n,r , ,v2 ,n ,v2 ,v2 ,v2 v K T T ,& K T T , T ,& T , K T ,& K T , v1 ,v2 ,n,r , v1 ,v2 ,n,r , v1 ,v2 ,n,r , v1 ,v2 ,n,r , v1 ,v2 ,n,r , v1 ,v2 ,n,r , n & E 2 , , , , . , ,& .. , , , n .
c 1 9. (0, min( 32 , 201 2 )), 0 < c1 < 1 < c2 , n c nc2 , (log m1 m2 )-2 p (log m1 m2 )-(1+) , n , K T , K T T }, c
1

m 1 m2 {T , T T ,

1) r = ] log m1 m2 - log log m1 m2 [ r = ] log m1 m2 - b log log m1 m2 [, b > 1 + n
,& v1 ,v2 ,n,r



.. n



, v1 ,v2 ,n,r



.. n

r (Cn )e

(-

m1 m2 2r

)

;

(61)

T T 2) v1T ,&,n .. v1T ,,n ; ,v2 ,v2 n 3) r = ] log m1 m2 - a log log m1 m2 [, a (1 + , 2 - ) n



,& v1 ,v2 ,n,r

.. n



, v1 ,v2 ,n,r

.

(62)




127

v1 ,v2 ,n , p. T , , , . , ( ), , . , , , . . . . : x(G ^ ^ T = T =
-1
2

v1 ,v

2

)L

m1 m

2

.

(63)

S , S : Lm E n , m,n . S A m,n

(m,n)N

( ). µT (A, S )(µT T (A, S )) , n . . , E 2 , ( ) S . . D1 (r ) r . . . D2 (r ) r . S S : L l Ln . s E n , ^ -1 (1) = S (L ) T s = T . T L ^^ ^ ^ s ^ m+1 l s ^ ^ , T (m + 1) = on . D 2 (r ) ~ t, kt , St , lt , St , Mt , t n, l E t . ~ t , St E n , ^ St : Llt Ln , T . Kt , Kt : Llt Lm+1 At , Mt lt ,n .


128

. . , . .

^ D2 (r ) T , r > 1, : ^ ^ ~ 1) T (1) = 1n , T , . 7). . 2). ^ 2) t = 1, lt = 1, Kt (1) = 1, At (1) = T (1) ~n , Mt (1) = on , 1 ~ -1 (0). . 3). St (1) = min At (1) ^ ^s 3) (T t )-1 (~lt ), Kt (lt ) < m + 1 m + 1 1 . Lm = , st ^ . lt = r - 1, . 5). . 4). ^ ~ 4) k = min y = (T (k ) Mt (lt )) 1n . y = on , ~ ~~ . 6). t = t + 1, l t = lt-1 + 1, At (lt ) = y , St (lt ) = min y -1 (1), Kt (lt ) = K , Mt (lt ) = Mt-1 (lt - 1), ~ ~ (Kt , St , At , Mt )|Ll -1 = (Kt-1 , St-1 , At-1 , Mt-1 ), . 3).
t

^ 5) y = (( T (i)) Mt (lt )) ~n . ~ 1 i y -1 (1) st (+)on ~ ^ ~j t = t + |y|, (lt , St , At , Mt ) = (l ~ . 6). 6) i L
l
t

i

t-|y | ~

. , St-|y| , K ~

t-|y | ~

,M

t-|y | ~

).

cj = At (j )

-1

(1) (Ln \ L

St (j )

).

(64)

cj = j Llt , . 7). t = t + 1, lt = max{j |cj = }, Mt (lt ) = Mt-1 (lt ) ont-1 (lt ) , St (lt ) = min clt , (St , Mt )|Ll -1 = (St-1 , Mt-1 )|Ll -1 , ~S
t t

(Kt , At ) = (K . 3). 7) .

t-1

,A

t-1 )|L

lt

.

(65)

10. Pv1 ,v2 Gv1 ,v2 , T v1 ,v2 ,n , :




129

1) c > 1, log m

(log m)c , a (0, 1 ) c (66)
KT v1 ,v2 ,n,r

µ

TT

r = ] log m - a log log m[ ^ ^ (D1 (r ), T ) .. µT (D2 (r ), T ) .. n n 2
(log n)
1-

;

(67)

2) (0, 1), log m

, b (1,

1 1-

), (68)

r = ] log m - b log log log m[ µ
TT

^ (D1 (r ), T )

.. n

^ µT (D2 (r ), T )

.. n



KT T v1 ,v2 ,n,r



.. n



KT v1 ,v2 ,n,r

. (69)

4. k -
, . . , . , . , , , , . . . , . . ,


130

. . , . .

, . . . . . n f : E k Ek , k - . f (x1 , x2 , . . . , xn ), xi , , Ek . xn = {x1 , x2 , . . . , xn } Nn = {1, 2, . . . , n}. n P k , ,


Pk =
n=1

n Pk . n k n Ek . -. n=1 , xn )

: E
n k

- n k =

n . k

- f f (x1 , x2 , . . . = f ((x1 , x2 , . . . , xn )), - f . n = {1 , 2 , . . . , s }. k , f = f i i = 1, 2, . . . , s. , . n T Ek n f Pk , n f () = f (()) E k , T f ( ) = f (( )). M (f , ) f L(f , ) =
T M (f ,)

min

|T |.

(70)

T M (f , ) , |T | = L(f , ). , L(n, ) = max L(f , ). n
f P
k

(71)




131

Fck , ,

Fck = { : E

n k +1

\ (k , k , . . . , k ),
n Ek ( () = (c1 a1 , . . . , cn an ))}, (72)

= (c1 , . . . , cn ), = (1 , . . . , n ), ci ai = ci , ci E ci ai = ai , ci = k . 11. n L(n, Fck ) = 1k 2 k t + t;

n k



2n - 2t, (2n - 2t) + 1,

k t-1 + t < n n = k t-1 + t.

(73)

Fck = (c1 , . . . , cn ), k . F ck , , p, F ck (p). M Ek . F
k M

= { Fck : i Nn (ci M {k })},
k M

(74)

= (c1 , . . . , cn ). |M | = 1 M = {µ}, F k Fµ . 12. n 1, k

2, p Nn (75)

L(n, Fck (p)) = L(n, Fck ). 13. n 1, k 2, µ Nn

k L(n, Fµ ) = n.

(76)

14. n 1, k 2 M Ek , |M | 2,
k L(n, Fµ ) = L(n, Fck ).

(77)


132

. . , . .
k Fst x n q Nn-1 . = = (b1 , . . . , bn ), : xj Zl ()},

k Fst . S () Z1 (), . . . , Zq (), n Ek () i Nn bi = max{aj xj Zl (), l Nq .

15. n

2, k

2, µ Nn (78)

k L(n, Fst ) = n - 1.

k Fst p() = n - q , k q xn S (). Fst (p) k , , p. Fst

16. n

2, k

2 pN

n-1

(79)

k k L(n, Fst (p)) = L(n, Fst ).

, k = 2,
n n Jn = { : E2 , E2 ( () = + )},

(80)

+ , 2. a E 2 . Jn +, · 2. n o E2 , . ~ 2 Fin : F
2 in

= Jn \ {o }. ~ 1
2 L(n, Fin )

(81)

17. n 2·[

n-1 ]+1 2

n.

(82)




133

n E2 , i- , . 2 Fin (1) = {1 , . . . , n }.

(83)

18. n

1 (84)

2 L(n, Fin (1)) = n - t,

t 2
t-1

+t

n

2t + t.

(85)

, . n , f P 2 2 ) T M (f , F 2 (1)), , T M (f , Fc in
2 L(n, Fc2 Fin (1)) = L(n, Fc2 ).

(86)

n f Pk n , Ek f () = f (()), f . f () , () . k 2 , {Fck , Fst , Fin } n . Pk

5.
. , P 2 , § 4, P 2 . . .


134

. . , . .

1921 . . . 2 L(n, Fst ) K . Lk (n). . . [16]. . , C 1 . f (x1 , . . . , xn ) = f (x1 , . . . , xn ) ¯ ¯ f (x1 , . . . , xn ) C1 , f (x1 , . . . , xn ) = f (x1 , . . . , xn ). f (x1 , . . . , xn ) , = (a1 , . . . , an ) = (b1 , . . . , bn ) , bi , , , i = 1, 2, . . . , n ai f () f ( ). f (x1 , . . . , xn ) , f (x1 , . . . , xn ) =
n

ci xi + d( mo d 2).
i=1

, C1 aµ , µ 2, µ , , ; a , , , . xj xj , , j =1 j =1 n m

. f (x 1 , . . . , xn ) -, f (x, . . . , x) = x -, f (x, . . . , x) = 1. . A1 ; D 3 µ ; F4 aµ ; F4 a ; L1 ; C2 , A2 , L2 , , µ C1 , A1 , L1 ; D2 , F3 , F3 , µ µ µ , D3 , F4 , F4 ; C4 , A4 , D1 , L4 , F1 , F2 , F1 , F2




135

µ µ -, C 1 , A1 , D3 , L3 , F1 , F4 , F3 , F4 ; L4 ; C 3 , A3 , µ L3 , F 1 , F 1 , , µ , C2 , A2 , L2 , F1 , F1 , µ = 2, 3, . . . S1 : S3 = S1 {1}, S5 = S1 {0}, S6 = S1 {0, 1}. P1 , P 3 = P1 {1}, P5 = P1 {0}, P6 = P1 {0, 1}. Si , Pi i = 1, 3, 5, 6, Lj j = 1, 2, 3, 4, 5, Dl l = µ 1, 2, 3, Am , Cm m = 1, 2, 3, 4, Fs , Fs s = 1, 2, . . . , 8, µ = 2, 3, . . . , , , S , P , L, D , A, C F .

19. : 1) Lk (n) = 2 K L; 2) Lk (n + 1) = 2 K S P ; 3) Lk (n) 2n n K D , M , C F . ¯ Lk (n) K . 20. : ¯ 1) Lk (n) = 2 K L; ¯ 2) Lk (n) = n + 1 K S P ; ¯ ¯ 3) LD2 (n) = 4 n ; LD2 (n) {4, 6} n ; ¯ 4) Lk (n) {2, 3, 4} D1 , D2 ; ¯ 5) Lk (n) = 4 K A; ¯ 6) Lk (n) = 3 K C ; µ ¯ 7) Lk (n) {4, 5} K {F1 , F4 , F5 , F8 , F1 , µ µ µ F4 , F5 , F8 } µ = 3, 4, . . . ;
2 2 2 2 8) 3 Lk (n) 8 K {F1 , F4 , F5 , F8 }; µ µ ¯ 9) Lk (n) = 5 K {F2 , F3 , F6 , F7 , F2 , F3 , µ µ F6 , F7 } µ = 3, 4, . . .


136

. . , . .

¯ ¯ 10) Lk (n) = 4 n , Lk (n) {4, 5} n 2 , F 2 , F 2 , F 2 }. K {F2 3 6 7 . 2 L(f , F st ) Lk (f ), , f K . 21. : 1) Lk (f ) = 2 f K L, n 1 ; 2) Lk (f ) = n + 1 f S P , n ; 3) ) t(n) = 2n - 4(p + 1) 2p + 2p < n 2p+1 + 2(p + 1); ) Ck = 2 K C D 1 D3 ; µ µ ) Ck = 3 K {F1 , F4 , F5 , F8 , F1 , F4 , µ µ F5 , F8 }, µ = 2, 3, . . . ; ) Ck = 4 K A, D2 K 2 2 2 2 3 3 3 3 {F2 , F3 , F6 , F7 , F2 , F3 , F6 , F7 }; µ µ ) Ck = 5 K {F2 , F3 , F6 , F7 , F2 , F3 , µ µ F6 , F7 }, µ = 4, 5, . . . , n r , C k k t(n), a K , n , Lk (f ) = r , r D2 . 1 . Lk (f ) , n , . : r - : ·+ f , L(f ) = r , ;




137

1. . ·- f , L(f ) = r ; + - ri , r
i+1

,...,r

i+k

:

· , f ri L(f ) ri+k ;


138

. . , . .

· , f ri L(f ) ri+k . , : . . , , , n , 2n, , , , 2n, . , , 2n . : L 2, S P f n + 1, n . , , D2 , , , .


[1] . ., . . // . . . . . 51. 1958. . 270­360.




139

[2] . ., . ., . . // . . 173, 5. 1967. [3] . . . . - . . . 1958. . 1­80. [4] . . . . - . . . 1958. . 1­126. [5] . ., . ., . . - // . . 31. .: , 1976. . 25­41. [6] . . . . . . 1977. . 1­143. [7] . . // . . 31. .: , 1978. . 5­68. [8] . . // . . 14. , 1969. . 28­43. [9] . . , // . . 18. 1. 1975. . 137­150. [10] . . . . . . 1979. . 1­127. [11] . . . . . - . . . 1981. . 1­145.


140

. . , . .

[12] . . T - , . . . - . . . 1988. . 1­153. [13] . . // . . 23. . : , 1973. . 8­23. [14] . . . . . - . . . 1989. . 1­80. [15] . . . . . . 1982. . 1­73. [16] . . . . . . 1991. . 1­101. [17] . . (, , ). . : , 1978. [18] . ., . ., . . . . .: , 1966. . 1­98.