Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.intsys.msu.ru/science/books/Inf_poisk_Gasanov.pdf Äàòà èçìåíåíèÿ: Sun Sep 1 20:19:00 2013 Äàòà èíäåêñèðîâàíèÿ: Thu Feb 27 21:40:30 2014 Êîäèðîâêà: Windows-1251 Ïîèñêîâûå ñëîâà: m 77

..

-

..



Mo c 2005


..

" " " ", - . ... , - , . - . . , , , .

-- - , , . . .

c - , 2005 .

-



1 - 1.1 () . . . . . . . . . . . . . . . . . . . . . . . 1.2 . . . . . . . . . 1.3 . . . 1.4 . . . . . . . . . . . . . . . . . . . . . 1.5 . . . . . . . . . 1.6 . . . . . . 1.7 . . . . . . . . . . . . . . . 5 11 .... .... .... . . . . . . . . . . . . . . . . 11 31 35 38 46 49 50 52 52 53 60 68 70 73 80 81 3

2 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 . . . . . . . . . 2.3 c 3 3.1 . . . . . . . . . . . . . . . . . . . 3.2 . . . . 3.3 3.4 . . . . . . . . . . . . . . . . . . .

. . . .


4 4.1 - . . . . . . . . . . . . . . 4.2 . . . . . . . . . . . . . . . . . 4.3 4.4 4.5 . . . . . . . . . 4.6

88 . 88 . 91 . 95 . 102 . 104 . 105

5 111 5.1 . . . . . . . . . . . . . . . . . . . . . . . . 113 5.2 . . . . . . . . 113 5.3 . . . 121 5.4 126 5.5 . . . . . . . . . . . . . . . . . 131 138

4



, , . . , , , , . : , , . . , , , , , - . , . . , . -- , , -- , .., -- , , .. . "5


" , -- "". . , [3]. - , , . . . : , , . , : , , . , , . , , , . , , , , . . ( ) , , 6


. , , ( ), , , , . . , , . . -, . . . , , , . -- , .. , . -- , . , . , . , , , , ( ). , , 1, -- . , , , -- . 7


-, , , . , , , , . - ( ), , . , , , . , , . . , . , , . , , . , , -- , . , , , . 8


. , . , -, , , , , . , -- . , , , . - (). , . . , , , . , ( , , ). , . - , . , , 9


, , . , . .. - . ( ) - - " "( "", 431, 2.1). .. . . , , . - . . . , , .

10


1


1.1 ()

, , -- . : , (), , . , , . : , , . , , -- , -- . , . () -- , . 60- 20 11


. , , , . . . . , . , , , . , . [21] , . . 3 . () ( ) . , -- , . . . , , , , . [30] . . [14]. ., . " "[2]. . . , 12


, . , . , , , . . -- , " " . ., . " "[18]. . . , . . , . , , . "" , . , , . , . -- , . , , , , . . "" , , . "" , , . 13


, , : . , , . . , , . , . , , , , . , ( ). . . . () -. . , [0, 1] . , [0, 1]. [u, v ] , [u, v ]. . , . (). [4, 26, 27, 40] . [40] , 14


. [40] : , T 1, T 2, -- T 3, , T 3 , , "" "", T 3 T 2, , T 3 T 2, . Q T 1 T 2 T 3, Q : T 1 × 2T 2 T 3. , , . . , . , , ( ). , -- [0, 1] . Y , Y, , . . , , [0, 1], {(u, v ) : 0 u v 1}. X . X × Y , , Y X . . (), , . 15


, int , (1.1) (u, v )int y u y v, (u, v ) X, y Y . S = X, Y , , X -- , Y -- , -- , X × Y , , . I = X, V , , X -- ; V -- Y , ; -- , X × Y , () S = X, Y , . , I = X, V , x X V , x, x. . , V , , . , -- . , , "", " "( " ", . [20, . 44-45]), , , . , , , , . . 1) , ++ [29]. , 16


. -- , , , , . , . 2) [17, 33, 64]. , , , . 3) [13, 34] [16]. , , . , , -- . 4) , [4] . , , , , , , . , , . , , [36, 46, 60, 61]. R -- . () [36, -] W = {x1 ,x2 ,...,xn }, xi R, -- D, . 1. v , (17


), fv := fv1 #fv2 , fv := fv1 #c, fv := fv1 , vi (i = 1, 2) -- v D, fvi W, # {+, -, ×,/}, c R . 2. v , ( ), fv1 > 0, fv1 < 0, fv1 = 0, v1 -- v D, fv1 W . 3. . , , I = X, V , = , X = [0, 1] R V [0, 1]. x X D P (x), . , , , . . , D I , x X . D, C (D), cost(x, D) x, cost(x, D) -- , P (x) D. I , C (I ), C (D) D, I . () d [63]. d -- , f (x)?0, f d ? {>, <, =}. , d 1, , [46, 61, 66]. . . [23]. 18


- d ? , . -, - d . ( ) I = X, V , = , X = [0, 1] R V [0, 1], O(log2 n), n -- V . - [43]. -- n log2 n. , O(log2 n) . , , . O(n log2 n) n [4]. , O(n log2 n) - n , . . - , I = X, V , = , , , . V = {y1 ,...,yn } -- . . d. [0, 1] m =]1/d[ , i- (i = 0,m - 1) (i/m, (i +1)/m]. V . A m, i- 19


(i = 0,m - 1) 0, i- V , j , i- yj V . x [0, 1] . j = [x ž m]. j , x. Aj = 0, x V , yAj x , x . -, , - [43]. 5) , . I = X, V , . , X V , . y Y . 1, xy , y, (x) = 0 1 , y . , , I = X, V , , V = {y1 ,...,yk }, -- , {y1 , ,...,yk , }. , , , I = X, V , , , {y1 , ,...,yk , }. X = B n -- n- . yi , , , [19] , {y1 , ,...,yk , } . n- ? ? , {x1 ,...,xn , x1 ,..., xn } F , X . F 20


F yi , (i = 1,k ). ( ), , , . , , -. , , , , yi , (i = 1,k ) , yi . x X , x [13, 16]: , , , , , , . . , . , x. , , , , x 1 , ( , " ", -- " "). , . , x , , , 1 x, 21


, . x, x , -, , , . x. . -, , - -- . , [13, 16], . , x , , , , x , , 1, , 0, . , , . , , , , . - , . . G , , 22


X . , . , , G , 1, , . , , . F . , , , , . , , , , x, , , , , , . (). , . M -- . |M | M , M . {1,m} {1, 2,... ,m}. , , . ? (n) = o(1), lim (n) = 0; A(n) = o(B (n)), ? A(n) = B (n) ž o(1). , A(n) ? B (n) n A < B , (n) = o(1) , n0 , ? A(n) (1 + (n)) ž B (n). A < B B < A, , A B n 23
n


A B . A < B , c, , n0 , A(n) c ž B (n). A < B B < A, , A B n A B A = O(B ). n n k k . r -- , [r] , r, ]r[ -- , , r. = " ". M, Mx x. - . . (, ) , -- . , ( ), -- () . , , . () , ( ). . , 0. . (1 ,2 ), (2 ,3 ),..., (m
-1 def

,m )

1 m . f -- , X , f : X {0, 1}, Nf = {x X : f (x) = 1} f . O(y, ) = {x X : xy } y Y. y, : X {0, 1} , Ny, = O(y, ), y . 4 : 24


ž X ; ž Y ; ž F , X ; ž G , X ( -- , ). F = F, G . . () , -- . . . , . ( ). -- , . G. . , , {1, }. , -- . , , . F. . Y. . F = F, G . 25


. , x X , , , 1 x; , n, x X , , , n x; x X , x; x X , , , x; y , , x X , x . U x , x, JU (x). JU (x) : X 2Y U U . . . 4 , , : ž X
int

= {(u, v ) : 0 u v 1};

ž Yint = [0, 1]; ž 1 F = F1 F2 , F1 = {f [0, 1]},
1 f,a (u, v ) = 2 : a [0, 1]}, F2 = {f

,a

,a

:a (1.2) (1.3)

1, 0, 1, 0,

u a , u > a v a , v < a

2 f,a (u, v ) =

ž G = G1 G2 G3 , G1 = {gž,m : m N}, G2 = {g-,m : m N}, G3 = {g,a : a (0, 1]}, gž,m (u, v ) = max(1, ]u ž m[), 26 (1.4)


2 2 2 2 2 1 1 y1f,y2y2f,y3y3f,y4y4f,y5y5f,y6y6 y1f,y1y2 y3f,y3y4 r Er Er Er Er Er r ' r r ' r } } T2 T2 T T ? ? T T 2 2 2 2 f,y1 f,y2 f,y3 ? ? f,y4 f,y5 f,y6 ? ? p p p p p p ? ? u e ! ? u e ! ? e u ! ? 1 ?2 ? e e e ? 1 ?2 1 ?2 ? ? p g,y ep? e? p ep? 2 5 g,y1 ? f,y5 ?f 1 s T s d g,y3 d d 1 f 2 ?f 1 d 2 1 2 ? ,y4 dp ,y3 ? ,y2 dp p? p g,y2 Q k g,y6 s d d 1 2 1 2 p d p B Ågž,3 r g,y4 r ÅÅ r Å2 1rr Å Å rp g-,3

. 1.1: g-,m (u, v ) = g,a (u, v ) = 1, 2, v - u < 1/m , v - u 1/m 1, 2, u a . u > a

(1.5) (1.6)

, 1.1, . , , , -- y . 8 ( g ) 17 ( f ). n -- , g (x) -- , n g (x) , X , , n Ng = {x X : g (x) = n}.
n G = {g : g G, n N},

N -- . c -- , [c] . . 27


(, ) , [(, )] [(, )], , g , , g -- , . . x, , x 1, x. f : ž = , f (x) 1 (x X ); ž = , f (x) 0; ž = , f (x) . (x). R(U ), P (U ), L(U ) ( R, P , L) , U . N -- ( ) U . N , ( -- U, , ). , U JU (x) = { L(U ) : (x) = 1} . , , , , . 28


, G , , (). , , (). , , , (). , , , . . I = X, V , = -- , V = {y1 ,...,y7 } , y1 y1 žžž y7 . F = {f=,a (x) = 0, 1, 1, 2, x = a : a X }, x = a x a : a X }. x > a (1.7)

-- G = {g,a (x) = (1.8)

(., , [4, 15, 21]) , , . 1.2 F = F, G , I , [44, c. 214], . , , . 29


f=

y1 p T
,y
1

y3 y4 y5 y6 p p p p ! ? ! ? u e u e ? ? e e f=,y2e ? f=,y3 f=,y4e ? f=,y5 f=,y6e ? ep? ep? p ep? u e s d e d d 2 1e 2 1 p e dp B Åg,y5 grr ,y1 ÅÅ r Å rr Å2 1r rpÅÅ g,y3

y2 p u e e

y7 p ! ? ? f=

,y

7

. 1.2:


1.1. , n- . 1.2. , n , n- , , . ? 1.3. , - n- n- () , , R . , . 1.4. , . , , ( ) . , , .

30


1.5. , , , . () n {0, 1}. . , , , , . , . (. 1.2).

1.2



I = X, V , . , U I = X, V , , x X V , x, JU (x) = {y V : xy }. U , I , I . U -- , y -- Y . LU (y ) U , y. [6]. 1. U I = X, V , , y V , , O(y, ) = , = y, , LU (y ) = y V , , O(y, ) = , LU (y ) = , 0.
LU (y ) LU (y )

. . x X . y V . O(y, ) = , , x O(y, ), LU (y ) = , 0. ,
LU (y )

31


y JU (x). , O(y, ) = . xy , y, (x) = 1, (x) = 1.
LU (y )

, L(U ) , (x) = 1. , y JU (x). x O(y, ), y, (x) = 0, (x) = 0. , y JU (x).
LU (y )

, , JU (x) = {y V : xy } . . y V . O(y, ) = , , x X x O(y, ), , x X y JU (x). , LU (y ) = , 0. , O(y, ) = . , y , x, (x) = y, (x).
LU (y ) LU (y )

, y JU (x) {y V : xy }. , x JU (x) = {y V : xy }, , , U I . . 1 , I = X, V , , , , , y, , y V . 32


2 2 2 2 2 1 1 1 y1f,y2y2f,y3y3f,y4y4f,y5y5f,y6y6 y1f,y1y2f,y2y3f,y3y4 r Er Er Er Er Er r ' r ' r ' r } } T2 T2 T T ? ? T T 2 2 2 f,y1 f,y2 f,y3 ? ? f,y6 f,y4 ? ? 2 p p p p f,y5 ? ? u e ! ? u e ! ? ? e e ? 1 ?2 1 ?2 ? ? ep? e? p p p 2 g,y1 ? f,y5 ?f 1 s d g,y3 u e ! ? ,y4 d e 1 1 2 1 ?2 ,y f 2 ?f,y2 ? 3 dp e? p p? ? p g,y2 Q k g,y5 s d d 1 2 1 2 p d p B Åg,3 r g,y4 r ÅÅ r 1rr ÅÅ2 Å rp g-,3

. 1.3:


1.6. S = X, X, = -- , F (1.7), F = F, , V = {y1 ,y2 ,...,yk } X . F , I = X, V , = . 1.7. S = X, X, = -- , G = {g
=,a

(x) =

1, 2,

x = a : a X }, x = a

(1.9)

F = ,G , V = {y1 ,y2 ,...,yk } X . F , I = X, V , = . 1.8. X = {1, 2, ..., N }, S = X, X, = -- , 1, x < a 2, x = a : a X }, (1.10) G = {ga (x) = 3, x > a F = ,G , V = {3, 5, 7, 11, 13, 17, 19}. F , -

33


I = X, V , = . 1.9. X = {1, 2, ..., N }, S = X, X, = -- , V = {y1 ,y2 ,...,yk } X . , y1 < y2 < žžž < yk . m, I = X, V , = , . x X , , i = 1 i = k/m, yižm . x > yižm , i 1, y(i-1)m+1 ,y(i-1)m+2 ,...,yižm x. , , x . , I = X, V , = . 1.10. X = {1, 2, ..., N }, V X , c -- , X × V xc y (y V )&(x y )&(ƒ(y )((y V )&(x y )&(y < y ))), (1.11) .. xc y , y V , x. I = X, V , c . F = ,G , G (1.8). F , I = X, V , c , V = {3, 5, 7, 11, 13, 17, 19}. 1.11. Sdom1 = [0, 1], [0, 1], . V = {y1 ,y2 ,...,yk } [0, 1]. - , I = [0, 1],V , . 1.12. Sint = Xint ,Yint ,int -- , int (1.1), V = {y1 ,y2 ,...,y6 }, y1 = 1/6, y2 = 1/4, y3 = 3/8, y4 = 2/5, y5 = 3/4, y6 = 7/8. , 1.3, (1.2)- (1.6), I = Xint ,V ,int ? . 1.13. , , 1.1, I = Xint ,V ,int , V = {y1 ,y2 ,y3 ,y4 ,y5 ,y6 } -- , 1.4. 1.14. Sint = Xint ,Yint ,int -- , int (1.1),

34


q 0

y1 r

y2 r

q 1/3

y3 y4 rr

q 2/3

y5 r

y6 r

q 1

. 1.4: y1 y2 yk q q q B Å r Å rr d s y1 ,rd y2 , ÅÅ yk , Å r rÅ d . 1.5:
V = {1/8, 1/7, 1/5, 3/7, 3/5, 4/5, 7/8}. - , I = Xint ,V ,int .

1.3



I = X, V , F = F, G , , F , I ? yi V = {y1 ,...,yk } yi , F , , , 1.5, I . . S = X, Y , , X -- , Y -- , -- , X × Y , F = F, G . , F S = X, Y , , I = X, V , S U F , I . , [6]. 35


2. X , Y , X × Y F = F, G , , 1 F . F S = X, Y , , y Y , O(y, ) = , y, (x)
n m
i



y,

(x) =
i=1 j =1

fij (x),

fij F G. . . I = X, V , , V = {y1 ,...,yk } Y . yl , (x) (l = 1,k )
nl m
li



yl ,

(x) =
i=1 j =1

flij (x),

flij F G, l = 1,k . , mli j =1 flij (x) F , . 1. , I , . k +1 , , 1 k . l {1,k } . l- ( l ) yl . O(yl ,) = , l nl , i- (i = 1,nl ) mli . i (i {1,nl }) . flij F , j - i- n flij . flij G ( flij = g , g G, n N), , j - i- , g , j - i- n, 36


r - 1 , r -- g , {1,r}\{n}. ,
nl m
li

l (x) =
i=1 j =1

flij (x) =

yl ,

(x).

, 1 I . . F . y Y , O(y, ) = . V -- , y . F , U , I = X, V , . LU (y ) U , y . U I , 1 (x) y, (x).
LU (y )

(x) , F G, , .


1.15. S = X, X, = -- , F = ,G , G (1.8). F S ? 1.16. , 1.4, S
b bool

= B n ,B n ,
n

b n

, B

n

-- n-

-- B × B , , (x1 ,...,xn ) (y1 ,...,yn ) xi yi , i = 1,n.
b

(1.12)

37


, Sbool . , Sbool .

1.4



, U . , () U . . . x. U . : ž -- , , , ; ž , x , , , , , , ; ž , , , x. , , 1, , ; ž . 38


. , I , , , U , x. I = X, V , , V = U , , , . , , , , . , , . , , , [15, 22, 25, 37, 38, 39, 41, 45, 48, 55, 56], (., , [12, 15, 42, 47, 57, 58, 62, 65]) , , , , . [25, .20]: " , , , : - , ; -, , . ." . , G a, F -- b. U x X. 39


U x T (U, x) = a ž
P

(x)+ b ž
R\P

ž (x).

T (U, x) , U , T (U, x) , x, a, , b. . -, T (U ) = max T (U, x)
xX

( max, sup, T (U, x) , , , sup ). ee - ( ). , . -, , . X , X, , P , -- X , P -- , , , P(X ) = 1. , , . , S = X, Y , , , X X, , P . , X , S = X, Y , , , P . , F = F, G , Nf , f F G. . 40


1. F = F, G , U F T (U, x), x, . . , U F r {x X : T (U, x) < r} . , ( R(U )) (N ). R(U ). C -- U , . C -- , c -- . (c) c. , =
C C cC

(c).
f g

, Nf N

g


= Nf N g , N =
C C cC

= Nf Ng ,



N

( c)

.

: Mr = {B R(U ) : |{B P }| +
B\P

< r}.

, , {x X : T (U, x) < r} =
BMr

((
B

N





)

(
R\B

(X \N





))) .

. , . U T (U, x), T (U ) = Mx T (U, x). (, ) -- , ž b ž P(N ) -- (, ) -- ; ž a ž P(N



)/ -- . 41


-- , P(N ) . , . T (U ) = Mx T (U, x) =
X

T (U, x)P(dx) = (x))P(dx) =
P

=
X

(b ž
R\P

ž (x)+ a ž (x)P(dx)+ a ž
X

= bž
R\P



(x)P(dx) =
P X


= bž
R\P

P(N





)+ a ž
P

P(N

).

, a = b = 1. U . Q(U ) U U . U , 1.5. , Q(U ) = k T (U ) = k , , . , U . I . I F q T (I, F ,q ) = inf {T (U ) : U U (I, F ) Q(U ) q }, U (I, F ) -- F , I . - I F q T (I, F ,q ) = min{T (U ) : U U (I, F ) Q(U ) q } ( min, inf , T (U ) , , , inf ). T (I, F ) = inf {T (U ) : U U (I, F )} I F . 42


- I F T (I, F ) = min{T (U ) : U U (I, F )}. k -- , S -- , I (k, S ) = {I = X, V , S : |V | = k }. , I (k, S ), : T (k, S, F ) = max T (I, F ),
I I (k,S )

T (k, S, F ) =

sup
I I (k,S )

T (I, F ),

( max, sup, T (I, F ) , , , sup ). U U (I, F ), T (U ) = T (I, F ), U I . T (U ) = T (I, F ), U - I . , . X = Y = [0, 1] X . "" . V = {3/4}. F = F, , 2 F = {f 1 }{fa : a (0, 1/2)}, f 1 (x) =
2 fa (x) =

0, 1, 0, 1,

x [0, 1/2] , x (1/2, 1]

x (a, 3/4) . x [0,a] [3/4, 1] 0, 1, x [0, 3/4) , x [3/4, 1] 43

I = X, V , . 3
/ 4,

(x) =


2 3/4, = f 1 &fa , a (0, 1/2). Ua , , , -- , 3/4, 2 fa , -- f 1 . , T (Ua ) = 1+ a +1/4 = 5/4+ a. , T (I, F ) = inf {T (Ua ) : a (0, 1/2)} = 5/4, , 5/4.

, x X x X , x 1. , , , . , , ž , ž , ž , , ž , , , ž , , , , , ž . . , . , , -- . 44


3 ( ). X , I = X, Y , F = F, G , U (I, F ) = , F . . , X F G . , |X | = m, , X , 2m . , |F | 2m . , X m , |G| < mm . U N (U ) U , , . U0 U (I, F ). U = {U U (I, F ) : T (U ) T (U0 )}, N = {N (U ) : U U }. , T (I, F ) =
U U (I,F )

inf

T (U ) = inf T (U ) = inf T (U ).
U U U N

I N . |F G| = n. M -- , , F G n . , |M | min(2m , 22 ). M = {f M : P(Nf ) > 0}. min P(Nf ) = r. r > 0. F M , F , r, r/m. N T (U0 ) ž m/r. F G , , , N . . 45
f M



1.17. X = {1, 2, ..., N }, S = X, X, =, P, -- , = 2X , P -- , x X P(x) = 1/N . 1. , - , 1.6. 2. , - , 1.7. 3. , - , 1.8. , 1.8, , , 1.48. 4. , - , 1.9, N = 100. m . m - . m . 1.18. X = {1, 2, ..., N } X , , - , 1.10. 1.19. X = [0, 1] . , - , 1.11. 1.20. Xint = {(u, v ) : 0 u v 1} . , , 1.1.

1.5



[25, . 92] , , . 46


. (., , [25]). X , Y X × Y . X, , P . , F I , F , I . , , . , , . [6]. 4 ( ). I = X, V , -- , , y V , O(y, ) = , F -- , I , T (I, F ) max(1,
y V

P(O(y, ))),

T (I, F ) max |JI (x)|.
xX

. U , I . , U (I, F ) = . x X . U I , x JU (x) = JI (x) = {y V : xy }. y JU (x). y , , , U , y , (x) = 1. (x) = 1 , , , 1, , , 1. 47


y . , JU (x) , . , , , , . , , , . JU (x) , , , , 1. , JU (x) , . . , T (U, x) |JI (x)|. , T (U ) = max T (U, x) max |JI (x)|,
xX xX

T (U ) = Mx T (U, x) Mx |JI (x)| = =
X

|JI (x)|P(dx) =
X

|{y V : xy }|P(dx) = P(O(y, )).
y V

=
y V O (y,)

P(dx) =

U U (I, F ), T (I, F ) max |JI (x)|,
xX

T (I, F )
y V

P(O(y, )),

V y , O(y, ) = , , I , , . , T (I, F ) 1. . 48



1.21. X = {1, 2, ..., N }, S = X, X, =, P, -- , = 2X , P -- , x X P(x) = 1/N , V = {3, 5, 7, 11, 13, 17, 19}. I = X, V , = . 1.22. Sdom1 = [0, 1], [0, 1], , P, -- , P -- [0, 1], V = {y1 ,y2 ,...,yk } [0, 1]. I = [0, 1],V , . 1.23. Sint = Xint ,Yint ,int -- Xint = {(u, v ) : 0 u v 1} . V = {y1 ,y2 ,...,yk } [0, 1]. I = Xint ,V ,int . .

1.6



5. I = X, V , -- F = F, -- , , y V y, F O(y, ) \ ( Nf ) = ,
f F \y,


T (I, F ) = T (I, F ) = |V |. . V = {y1 ,y2 ,...,yk }. i {1,k } xi O(y, ) \ ( Nf ).
f F \y,


, i, j {1,k }, i = j , xi = xj . , U U (I, F ) = , , 1.5, , I . U0 . U U (I, F ). U I , i {1,k } i , yi , Ci , i , xi . , 49


i, j {1,k }, i = j , Ci Cj , , , Ci , Cj , 1 xi , xj , xi xj F . , U k , , , x X T (U, x) k , T (U ) k T (U ) k , U T (I, F ) k T (I, F ) k . U0 T (U0 ) = T (U0 ) = k , T (I, F ) = T (I, F ) = k , .

1.7



: 1. , , ; 2. , , , , ; 3. , , , ( -, ); 4. , , -. , , . , 50


, , ( ). , .

51


2


-- , . , . .

2.1



, , (). , -- , , , . , , , (), , , , 52


(). , , , . . , ( ) . . , , , 0. X , Y X × Y . X, , P . , I = X, V , A-, ž y V O(y, ) P(O(y, )) = 0; ž y, y V , , y = y P(O(y, ) O(y ,)) = 0. , A-, .

2.2



, A-. , , . -- . V , , . 53


, C -, , = y, . I = X, V , -- , V = {y1 ,y2 ,...,yk },
m I F0 = { j =1 I , F = F0 , DI -, I , C , , 1. DI , DI . [7]. 6. I = X, V , -- , F = F, -- , I , U -- F , I . , y V



yij ,

: m = 1,k , 1 i1 < i2 < žžž < im k }.

ž I A-, D DI , , T (D) T (U ), ž I B1 -, D DI , , T (D) T (U ). . O (y, ) = O(y, ) \ (
y V y =y

O(y ,)).

, I B1 -, O (y, ) = O(y, ), I A-, P(O (y, )) = P(O(y, )). F1 F1 = {fA : NfA = A, A }. , F , F F1 . I I A-, -- , F0 F1 . 54


, F1 , E -, I 0. , U0 , E -, , T (U0 ) T (U ). C = (1 ,2 )(2 ,3 ) žžž (r-1 ,r ) -- , 1 -- . , 1 ,2 , ..., r-1 , C , , 2 ,...,r-1 -- C . r -1 i=2

n =



i



C . V = {y1 ,y2 ,...,yk }. y1 . Cy1 = {C1 ,C2 ,...,Cm } -- , LU (y1 ). f1 ,...,fm C1 ,...,Cm .
m m

U I , 1
i=1

fi = y

i

,

,
i=1

N

f

i

=

O(yi ,). Cy1 , , O (y1 ,).
s

, s (s m),
i=1

N

f

i



O (y1 ,), . Ni Nfi (i = 1,s), , Ni Nj = , i = j
s

(i, j {1,s})
i=1

Ni = O (y1 ,).

, Ni (i = 1,s) . ni Ci (i = 1,m). c , [c] , , . c U [c] 55


fN[c] \O (y1 ,) . N[c] O (y1 ,) , fN[c] \O (y1 ,) F1 . , LU (y1 ), , LU (y1 ) fO(y1 ,)\O (y1 ,) ,
s

nj = min ni .
1is i=1

ni ž P(Ni ).

Cj 1 LU (y1 ). LU (y1 ), 1 , y1 . LU (y1 ) 1 . c Cj [c] [c] y1 , . 1 1 = y1 , . , I . nj ž P(O(y1 ,)). ,
s s

ni ž P(Ni ) nj ž
i=1 i=1

P(Ni ) = nj ž P(O (y1 ,)) = nj ž P(O(y1 ,)).

, T (U ). Cj C1 . yi , i = 2,k , yi Ci , i ( i LU (yi )) yi , . , C1 ,...,Ck . U , , I , T (U ). U , . , U 0. 56


, . U , C1 ,...,Ck , , , Cj (j {1,k }) m , m {1,k } m = j . U I , m = ym , . , fj Cj , Nfj O(ym ,). , Nfj = O(yj ,) P(O(yj ,) O(ym ,)) = 0, P(O(yj ,)) = 0. , , U E - , , U0 . U0 . c , , Ci1 ,...,Cim ,
m


j =1



yij ,

I F0 . , yi ,

i ,

.

C1 ,...,Ck , . , , U1 . T (U1 ) T (U0 ), U0 , Ci (i {1,k }), yi , yi , .
I U1 F0 , T (U1 ) T (U ), U1 E -, U1 , , U1 , , Ci1 ,...,Cis , s

=
j =1



yij ,

. -

, , V = {yi1 ,...,yis }, , U1 C -. , U1 1. m . , 1. s Ci1 ,...,Cis . 57


s

=
j =1



yij ,

.

, , , Ci1 ,...,Cis . Cij Cij Cij (j {1,s} ij , nij -- Cij . G U1 , Ci1 ,...,Cis ,
s

O =
j =1

O (yij ,).

c G [c] fN[c] \O . , Cim , , m {1,s}, , , , I F0 .
s


i=1

nij ž P(O (yij ,)).

nil = min nij .
1j s

c Cil (j = 1,s) s

[c] [c]
j =1



yij ,

.
s

nij ž P(O(yij ,)),
j =1

nij ž

P(O (yij ,)), T (U1 ). Cij , Cil Cij (j = 1,s). , Cij - yij , . , Cj (j = 1,k ). , , , Cil , , . U2 . , T (U2 ) T (U1 ), U2 I , 58


1 U2 1 U1 , , 1 . , T (U2 ) T (U1 ). , x X \ O T (U2 ,x) = T (U1 ,x), j {1,s} x O(yij ,) T (U2 ,x) = T (U1 ,x) - nij + nil T (U1 ,x). U2 , U3 1. , Ur (r m +1), 1. Ur 0, Ur . Ur = y, . , Ur y V

, 1. , , . , , , . , 1. Ur , DI -. T (Ur ) T (U ) T (Ur ) T (U ) , Ur D. . 1. I A- F = F, -- , I , , I F0 F , U I , DI . I . F0 F , DI U (I, F ), , , 6 DI . , , DI -- . , DI -- k ( k -- 59


I I ), F0 , I , D -- . .

2.3

c

6 , , , , . . , I = X, V , F -, A- y, y V P(O(y, )) = P(O(y ,)). R(k ) = 3k [log3 k ]+4(k - 3[log
3

k]

) + max(0,k - 2 ž 3[log

3

k]

),

k 1. [7]. 7. I = X, V , -- , F -, F = F, -- , I , T (I, F ) P(O(y, )) ž R(|V |), y V . , . 2. 0 t t1 t2 , t1 - t 1 R(t1 )+ R(t2 ) R(t1 - t)+ R(t2 + t). . , R(k ) , 60


, 3l 2 ž 3l (l = 0, 1, 2,...) . . N -- . 3. k N, k 2, l = [log3 k ], min{R(t1 )+ R(t2 ) : t1 + t2 = k ; t1 ,t2 N} = R(k )+4 ž 3l-1 - 3k, 3l k 4 ž 3l-1 R(k ) - 2k, 4 ž 3l-1 k 2 ž 3l = R(k ) - k - 2 ž 3l , 2 ž 3l k 3 ž 3l . . 2 , 2 ž R(k/2), k -- r1 (k ) = R((k - 1)/2) + R((k +1)/2), k -- . l = [log3 k ], c = k - 3[log3 k] , k = 3l + c, 0 c 2 ž 3l , R(k ) 3 ž l ž k +4 ž c, 0 c 3l R(k ) = l 3 ž l ž k +5 ž c - 3 , 3l c 2 ž 3l . k . 1) 0 c 3l-1 , r1 (k ) = = 2 ž R(k/2) = 2 ž R(3l-1 +(3l-1 + c)/2) = 2 ž (3 ž (l - 1) ž k/2+2 ž (3l-1 + c)) = r1 (k )
def

=

= 3 ž l ž k +4 ž c - 3 ž k +4 ž 3l-1 = R(k )+4 ž 3l-1 - 3 ž k, (3l-1 + c)/2 3l-1 . 2) 3l-1 c 3l , 3l-1 (3l-1 + c)/2 2 ž 3l-1 r1 (k ) = 2 ž R(k/2) = = 2 ž (3 ž (l - 1) ž k/2+5 ž (3l-1 + c)/2 - 3l-1 ) = = 3 ž l ž k +5 ž c - 3 ž k +3l = R(k ) - 2 ž k. 3) 3l c 2 ž 3l , k/2 = 3l +(c - 3l )/2, (c - 3l )/2 l 3 r1 (k ) = 2 ž R(k/2) = 2 ž (3 ž l ž k/2+2 ž (c - 3l )) = = 3 ž l ž k +4 ž c - 4 ž 3l = R(k ) - k - 2 ž 3l . k . . 61


2. r1 (k ) R(k ) - 2 ž k , 4 ž 3[log3 k]-1 k 2 ž 3[log3 k] . 4. k N, k 3,
3

r2 (k )

def

=

min{R(t1 )+ R(t2 )+ R(t3 ) :
i=1

ti = k ; t1 ,t2 ,t3 N} =

=

R(k ) - 3 ž k. k = 3s, k = 3s +1, k = 3s +2.

. 2 , 3 ž R(k/3), 2 ž R((k - 1)/3) + R((k +2)/3), r2 (k ) = R((k - 2)/3) + 2 ž R((k +1)/3),

k = 3s. l = [log3 k ], c = k - 3[log3 k] , k = 3l + c, k/3 = 3l-1 + c/3. 1) 0 c 3l , r2 (k ) = = 3 ž R(k/3) = 3 ž (3 ž (l - 1) ž k/3+4 ž c/3) = 3 ž l ž k +4 ž c - 3 ž k = R(k ) - 3 ž k.
-1

2) 3l c 2 ž 3l , r2 (k ) = 3 ž R(k/3) = 3 ž (3 ž (l - 1) ž k/3+5 ž c/3 - 3l ) = R(k ) - 3 ž k. k = 3s + 1 k = 3s + 2 . . M (D) =
R(D )

| | ž , D D0 ,

D0 -- , , - , | | -- , . N (k ) = min{M (D) : D D0 |D| = k }, |D| -- D. D D0 , M (D) = N (|D|). 5. k k , 2, 3. 62


96 6 96 9 D1 D2 Dl %

& %? % p & ?  &  ?  pp r B Å r Å u rr e e ÅÅ rre ÅÅ e rÅ

. 2.1: 96 96 6 96 9 D1 Dr Dr
+1

Dl %

& % & %? % & ?  ?  &  ?  ppp ppp k Q k Q B Å r Å r Å rr Å rr ÅÅ rÅ . 2.2:

. , D D1 2.1, l 4. D2 , 2.2, r = [l/2]. , M (D2 ) M (D1 ). ti = |Di | (i = 1,l), ti 1. : 1) l -- , l = 2 ž r, r 2,
l l l

M (D2 )

=

2ž
i=1 l

ti + r ž
i=1 l

ti +
i=1

M (Di ) M (D1 ) =

= lž
i=1

ti +
i=1

M (Di ),

r = 2. 63


96 D4 0 ?  T q . 2.3: 96 96 96 D1 D2 D3 ) )

0 )? )? ?  0  0  B Å r Å rr T Å rr ÅÅ rÅ . 2.4: D1 2) l -- , l = 2 ž r +1, r 2,
l r l l

M (D2 ) = 2 ž
i=1

ti + r ž
i=1

ti +(r +1) ž
i=r +1

ti +
i=1

M (Di ) < M (D1 ).

, , D1 , D2 , . , D3 , 2.3, D4 , . . 6. k N (k ) = R(k ). . k . . k = 1; N (1) = 0 = R(1). k = 2; N (2) = 4 = R(2). k = 3; N (3) = 9 = R(3). . t < k N (t) = R(t). 64


9 69 6 D1 D2 )

0 )0 ?  ?  Q k . 2.5: D2

5, k , D1 , 2.4, D2 , 2.5. , 4 2, M (D1 ) = 3 ž k + M (D1 )+ M (D2 )+ M (D3 ) 3 ž k + R(|D1 |)+ R(|D2 |)+ R(|D3 |) 3 ž k + min{R(t1 )+ R(t2 )+ R(t3 ) : t1 + t2 + t3 = k, t1 ,t2 ,t3 N} = 3 ž k + R(k ) - 3 ž k = R(k ), M (D2 ) = 2 ž k + M (D1 )+ M (D2 )

2 ž k + R(|D1 |)+ R(|D2 |) 2k + min{R(t1 )+ R(t2 ) : t1 + t2 = k, t1 ,t2 N} R(k ). , D1 , D2 , D3 -- , ( ) 1, M (D1 ) = R(k ) D1 -- , 4 ž 3[log3 k]-1 k 2 ž 3[log3 k] D1 D2 -- , ||D1 |-|D2 || 1, M (D2 ) = R(k ) D2 -- . . 7. U U (I, F ). 6 D DI , 65


T (U ) T (D). D. T (D) =
R(D )

ž P(N ž P(
R(D )





)
R(D )

ž P(N



y V

y,



)=

= =
R(D )

O(y, )) =

y V

ž|V |ž P(O(y ,)) = ž|V | =
R(D )

= P(O(y ,)) ž

= P(O(y ,)) ž M (D) P(O(y ,)) ž N (|V |) = = P(O(y ,)) ž R(|V |), y V . U . 3. 7 T (I, F ) c ž [log3 |V |], c 3. , k ž P(O(y, )) 1. , , 4 , F -, , 1. 3 - [43], : , , , -, , . 4. I = X, V , -- , F -, F = F, -- , I I , , F0 F , P(O(y, )) ž R(k ) T (I, F ) P(O(y, )) ž R(k )+1, k = |V |, y V . 66


. 7, , 2.3, D4 -- k , , V , , 6, , C -. .

67


3


, . , -. , ( ) - - [43]. , , , , [1, 4, 35, 44, 50]. , -, , -, , , ( [15]), ( [15]), . , 68


, [12, 47, 53, 57, 58, 62, 65]. , . -. - h(y ) X {1,m}, m -- -. . -- . [47] , m . x ( ) h(x), i, i- x. , x i- . . . [12] . m . x - h(x), i, i- x . , x. , -, , . . [15, . 641-642] . ) , , , . ) -. , , "". , . ) ", , 69


, !-- . [15, . 642]. , , , . , , , . , , , , , , ), , . . X , , X × X , x, y , z X ž x ž (x x; y )&(y z ) (x z );

ž (x ž (x y ) (y

y )&(y x).

x) (x = y );

Sid = X, X, id , id , xid y x = y. S
id

.

3.1


y V

V -- X , max y ymax V , y V y ymax , min y ymin V , y V ymin y .
y V

70


g
,a

(x) =

1, 2

x a ,a X, 0, 1, x = a ,a X. x = a
,a

(3.1) (3.2) (3.3) (3.4) (3.5)

f=,a (x) =

G1 = {g F

(x) : a X },

F = {f=,a (x) : a X },
bin

= F, G1 .

. 8. I = X, V , id -- , Sid , Fbin -- , (3.1)-(3.5), T (I, Fbin , 2|V |- 1) ] log2 |V |[+1, T (I, F
bin

, 2|V |- 1) ] log2 |V |[+1.

: |V | = k . D1 (V ), , . k , ] log2 k [, . , , , ( , ), , , . D. V . ( , , "", "" .) -- D. V , , . -- , ( , ) . y = max y.
y V

71


D, , , , , 1, -- 2, g ,y (x). D, , , y , f=,y (x). , D , D1 (V ) . , D1 (V ) I = X, V , id . y V . -- D1 (V ), y . , ] log2 k [ , , , . -- f=,y (x), y f=,y (y ) = 1. , y 1. (, ). (, ) -- , , y V , , g ,y (y )=1, y y = max y . (, ) -- , , y y g ,y (y ) = 2, (, ) 1. , (y ) = 1. , , f=,y , x = y (x) = 0. , , (x) = f=,y (x). 1, , D1 (V ) I = X, V , id . D1 (V ). D1 (V ) , 2, , , , D1 (V ) 1, D1 (V ) 2 ž k - 2 , D1 (V ) 1, D1 (V ) 2 ž k - 1 . , Q(D1 (V )) 2k - 1. 72 (3.6)
y V


D1 (V ). x X . , D1 (V ) ( , (x) = 1) . ] log2 k [-1 , . T (D1 (V ),x) ] log2 k [+1. (3.6) , T (I, F
bin

, 2k - 1) ] log2 k [+1,

T (I, Fbin , 2k - 1) ] log2 k [+1. . , [44, c. 214].


3.1. I = X, V , c -- , X = {1, 2, ..., N }, V X , c -- , X × V (1.11). , I . .

3.2


-

N0 = N {0} -- . 0, ] log2 l[+1, L1 (l) = log2 l +2,

l = 0 l = 1, 2, 3 - l 4

(3.7) 73


, N0 . . 7. L1 (l) -- , , k, m N,
m m

r1 (k, m) = max{
i=1

def

L1 (li ) : l1 N0 ,...,lm N0 ,
i=1

li = k }.

r1 (k, m) = k k ž m ž L1 +1 + m m k k ž m ž L1 . + m-k+ m m k-

: L1 (l) , , : L1 (x) = x, log2 x +2, 0 x 4 , x 4

. , , . . , ,
m

r1 (k, m)

=
i=1

L1 (li ) > + m-k+

k-

k ž m ž L1 m k m

k +1 + m , (3.8)

k ž m ž L1 m

li (i = 1,m) 2 , . , l1 - l2 2. l + l2 l + l2 l1 = 1 , l2 = 1 . 2 2 l1 + l2 = l1 + l2 l1 - l2 1. 74


L1 (x) , L1 (l1 )+ L1 (l2 ) L1 (l1 )+ L1 (l2 ). (3.9) (3.9) ,
m

,
i=1

L1 (li ) -- ;

, li = li (i = 3,m)
m m

L1 (li ) =
i=1 i=1

L1 (li ) = r1 (k, m).

li (i = 1,m) , 1, (3.8), , , , , , (n) (n) (3.9), l1 ,...,lm , ,
m

L1 (li ) = r1 (k, m),
i=1

(n)

1, (3.8), 7. X X, , P . 1 gm (x) -- ,
1 gm (x) = i, x Xi (i = 1,m),

(3.10)

X1 ,...,Xm -- X ( X = X1 žžž Xm Xi Xj = , i = j ) , P(Xi ) c/m (i = 1,m), c -- , m.
m

(3.11)

P(X ) =
i=1

P(Xi ) c,

, c 1. 75



1 G2 = {gm (x) : m N},

(3.12) (3.13)

F = F, G1 G2 .

. 9. I = X, V , id -- , Sid , |V | = k , F -- , (3.1)-(3.4), (3.10)-(3.13), m -- , c -- , (3.11), L1 (l) -- , (3.7). 1 T (I, F , 2 ž k + m - 1) k k c k- ž m ž L1 +1 + m m m k k ž m ž L1 +1. + m-k+ m m 1 T (I, F , (2 + c) ž k ) 2 T (I, F ) 1 k . , U U (I, F ), , T (U ) 2+] log2 k [. 0 : Um , , . 0 0 Um . 0 m , 1 m, 0 1 gm (x). Vi = Xi V, li = |Vi |, i = 1,m. i i . i, Vi = , i , 3.1, D1 (Vi ). 0 |V | = k Um . F . 0 , Um I = X, V , id . y V . y Vi (i {1,m}), , y , 1 D1 (Vi ). gm (y ) = i, y 76

,


i- , , D1 (Vi ). D1 (Vi ) Vi , y . , , (x) = f=,y (x). 0 y 1, , Um I = X, V , id . 0 Um .
m 0 Q(Um ) m + i=1 0 Um . x X . x X (i = 1,m). m T (U0 ,x) = 1 + T (D1 (Vi ),x) 2+] log2 li [ 1+ L1 (li ),

max(0, 2 ž li - 1) 2 ž k + m - 1.

i

(3.14)

L1 (l) -- , (3.7). 7,
m m T (U0 ) = Mx T (U0 ,x) = X m m m T (U0 ,x) P(dx) i=1 Xi m i=1 m T (U0 ,x) P(dx) =

= = 1+
i=1

(1 + L1 (li )) ž P(Xi ) = c m
m

L1 (li ) ž P(Xi ) 1+

L1 (li )
i=1

c = m k k c = k- ž m ž L1 +1 + m m m k k ž m ž L1 +1. + m-k+ m m 1+ r1 (k, m) m =]c ž k [.
m Q(U0 ) 2k +]c ž k [-1 (2 + c) ž k.

c 1, m k . m = k , k/m = 1 r1 (m, k ) = 0 ž L1 (2) + k ž L1 (1) = k ž L1 (1). m > k , k/m = 0 r1 (m, k ) = k ž L1 (1) + (m - k ) ž L1 (0) = k ž L1 (1). 77


,
m T (I, F , (2 + c) ž k ) T (U0 ) 1+

c k ž L1 (1) 2. ]ck [

m =]k ž (k )[, (k ) k (k ) > 1 k , cžk < 1. T (I, F ) 1+ ]k ž (k )[ , T (I, F ) 1, , k > 0. m , - U0 , (3.14),
m m T (U0 ) = max T (U0 ,x) 2 + max ] log2 li [ 2+] log2 k [. xX 1im

. 5. F -- , (3.1)-(3.4), (3.10)-(3.13), k -- , 1 T (k, Sid , F ) T (k, Sid , F ) 2 k T (k, Sid , F ) T (k, Sid , F ) 1. 1. Sid1 = X, X, id , X = [0, 1], X, , P X , p(x). X
1 i

. -- P

X

= {x X : 0 x 1/m}. i i-1 < x }, i = 2,m. = {x X : m m

(3.15)

1 gm (x) = max(1, ]x ž m[) (3.10). p(x) c = const, P(Xi ) c/m, 9.

78


, 9, I = X, V , id Sid1 , |V | = k . [0, 1] m (3.15). V , , . - x V , , . , x. max(1, ]x ž m[). , , . 7 , V m . m m = k , , V , . 1 1 , 2 ( ) . , . , , , - , - . 2. Sid2 = X, X, id -- , X = {1,...,N }. X, , P -- X , -- , P X , x X P(x) = 1/N . m N. r = N - m ž [N/m]. 79


X1 ,...,Xm -- , X X
i

= {x X : 1 + (i - 1) ž ([N/m]+1) x i ž ([N/m]+1)}, i = 1,r, = {x X : r ž ([N/m]+1) +1+(i - 1 - r) ž [N/m] x r ž ([N/m]+1) +(i - r) ž [N/m]}, i = r +1,m, P(Xi ) ([N/m]+1)/N < 2/m,

i

1 gm (x) = i, x Xi , i {1,m}.

9 c = 2.


3.2. I = X, V , c -- , X = {1, 2, ..., N }, V X , c -- , X × V (1.11). , I .

3.3



10. I = X, V , id -- , F = F, G2 -- , (3.2),(3.4),(3.10),(3.12), , m, 1 1 y, y V gm (y ) = gm (y ), 1 T (I, F ) 2. : U , . , . m -- , . m , 1 , 1. gm . 1 y V gm (y ) f=,y , y . , 80


U I , x X T (U, x) 2. , T (I, F ) 2. , T (I, F ) 1. . 6. F = F, G2 -- , (3.2),(3.4),(3.10),(3.12), , V 1 m, y, y V gm (y ) = 1 gm (y ), k 1 T (k, Sid , F ) T (k, Sid , F ) 2.

3.4



, . V = {y1 ,..., yk } [0, 1] . , x [0, 1) ( ) V , x ( V ), , : (, , , , ), . , ( V ), . , , , , ( V ) k 2 , , 81


. , , , [0, 1). 1 . [11]. . V = {y1 , y2 ,...,yk }, . . . V , , , y1 < y2 < žžž < yk . dV = min (yi - yi-1 ). m =]1/dV [ -- , , 1/dV . m, ni (i = 0, 1, 2,... ,m - 1). [0, 1] m : Ai = [i/m, (i +1)/m), i = 0, 1,... ,m - 2, Am
-1 2ik

= [(m - 1)/m, 1].

V . ni : -1, Ai V ni = q , q -- V , Ai , i = 0, 1, 2,... ,m - 1. , . x [0, 1). j = [x ž m] -- x ž m. , x Aj . nj -1, V x. ynj x , nj , . , , , , 6 . , , 82


m k . , m. k -- , 1 1 ,2 ,...,k -- [0, 1] . d(1 ,...,k ) =
1i
min

|i - j |.

r -- f (k, r) = P(d(1 ,...,k ) r) -- , i (i = 1, 2,... ,n) r. , V k [0, 1], , f (k, r) k - , r, k . . 11. r < 0 1 (1 - (k - 1) ž r)k 0 r 1/(k - 1) f (k, r) = 0 r > 1/(k - 1). : l -- [0, 1], r -- , k -- , 1, n -- , 1 n k . x1 ,x2 ,...,xk -- [0, 1] . B (n, r, l) , x1 ,x2 ,...,xn [0,l], xi (i = 1, 2,... ,n), r. f (n, r, l) = P(B (n, r, l)). , r < 0, f (n, r, l) = ln , r > l/(n - 1), f (n, r, l) = 0. , 0 r l/(n - 1). 8. 0 r l/(n - 1), f (n, r, l) = (l - (n - 1) ž r)n . 83


n. . n = 2. : x1 < x2 , x2 < x1 , . x1 0 l - r, x2 -- x1 + r l, f (2,r,l) = 2
0 l -r l

dx

1 x1 +r

dx2 = 2
0

l -r

(l - x1 - r)dx1 = (l - r)2 .

. q < n l [0, 1]. Ai , xi , x1 ,...,xn , i = 1,...,n. , i, j {1,...,n} i = j , Ai Aj = , P(Ai ) = 1/n, i {1,...,n}. ,
n

P(B (n, r, l)) =
i=0

P(Ai B (n, r, l)) = n ž P(An B (n, r, l)).

An B (n, r, l) xn (n - 1)r l, n - 1 [0,xn - r] r, f (n, r, l) = P(B (n, r, l)) = n ž P(A1 B (n, r, l)) =
l

=n
(n-1)r l

P(B (n - 1,r,xn - r))dxn = (xn - r - (n - 2)r)n-1 dxn =

=n
(n-1)r

=

(l - (n - 1)r)n .

. 11 , f (k, r) = f (k, r, 1). 11 . 84


f (k, r). 12. rk -- , , 0 rk 1/(k - 1). ? 1/rk = o(k 2 ) 0, -1/c lim f (k, rk ) = , 1/rk c ž k 2 , c = const e k ? 1, k 2 = o(1/rk ). : k = o(k ) k . ? ,
k

lim

1-

k k

k

=

k

lim

k k - k

-k

=
k -k k



-

= =

k

lim 1+
-
kk k -k

k k - k
k

k k k -k

= (3.16)

k

lim e

= lim e-

k

.

, 1/rk = o(k 2 ) k . ? , k k rk = k /k 2 . rk 1/(k - 1), : k c ž k , c -- ? 1, k = o(k ). f (k, rk ) = 1- (k - 1)k k2
k



1-

c(k - 1)k k2

k

= o(1). ?

? (k - 1)k /k = o(k ), (3.16)
k

lim f (k, rk ) = =

k k

lim

1-

(k - 1)k k2
k

k

=
k

lim e-

(k-1)k k

= lim e-

= 0.

, 1/rk ck 2 k , c = const. 85


(k - 1)/ck = o(k ), (3.16) ?
k

lim f (k, rk ) = lim

k

1-

k-1 ck 2

k

= lim e-
k

k -1 ck

= e-

1/c

.

.

? , , k 2 = o(1/rk ) k

, k 0 k rk = k /k 2 . (k - 1)k /k = o(k ), (3.16) ?
k

lim f (k, rk ) = =

k k

lim

1-

(k - 1)k k2
k

k

=
k

lim e-

(k-1)k k

= lim e-

= 1.

12 . , c ž k 2 , k , 6 , e-1/c . , k 2 , 6 . , , , k 2 , . d(k ) d(1 ,...,k ), . 13. d(k ) = 1/(k 2 - 1). : F (x) d(1 ,...,k ). F (x) = P(d(1 ,...,k ) < x) = 1-P(d(1 ,...,k ) x) = 1-f (k, x). x 0 F (x) = 0, x 1/(k - 1) F (x) = 1, , 86


d(k ) =
-
k = xF (x)|0 1 k -1 1 -1

xdF (x) =
0

1 k -1

xdF (x) =

-
0

1 k -1

F (x)dx =
1 k -1

=
0

f (k, x)dx =
0

(1 - (k - 1)x)k dx =

1 . k -1
2

13 . , k 2 , 6 .

87


4


4.1 -

, , , [28], [26, 31, 32], [15], [25] . . , , . , , [9]. , , Spart = X, X, , X -- , -- X × X , , x, y , z X ž x 88 x;


ž (x

y )&(y

z ) (x

z );

ž (x

y )&(y

x) (x = y ).

a X , Ka -- , X {0, 1} a}. , Ka (x) , NKa = {x X : x a. K = {Ka (x) : a
n

X }, M = {
i=1

Kai (x) : ai X, n N}, N --

. . 1. a, b X Kb (a) = 1, N
K
a

N

K

b

.

. Kb (a) = 1, a b. a b. , c b , c NKa c , c NKb . . 2. a X, f M f (a) = 1, NKa Nf .
n

. f =
i=1

Kai . f (a) = 1, -

Kai , Kai (a) = 1, 1 NKa NKai , , NKa Nf . .
n

3. a X
i=1

fi = Ka , fi M.

i {1,n}, fi = Ka . . Ka (a) = 1, i, fi (a) = 1. 2 NKa Nfi , , Nfi NKa , , NKa = Nfi , Ka = fi . .
n

4. a X, f = N
K
a

fi , fi M, f (a) = 1,
i=1

Nf .
n

. Nf =
i=1

Nfi . a Nf , a Nf

i

i = 1,...,n. 2 89


N

K n

a

N
f
i

f

i

i = 1,...,n. , NK

a



N
i=1

= Nf . .

a R X R, b R \{a} , a b.
n

5. f = f 0.
i=1

fi , fi M, f M,
n n

. Nf =
i=1

Nfi . ,
i=1

N

f

i

= ,

f 0. Nf ( ) , ? M = {a1 ,...,am } -- Nf , . , a Nf a M , ai M , a ai . , a ai
m

Kai (a) = 1 a N

K

ai

. , Nf
i=1

N

K

ai

. -

, 4 ( , f (ai ) = 1) i {1,...,m} NKai Nf . ,
m

Nf =
i=1

N

K

ai

, , f M, .

F = M, . U -- F . {1 ,...,m } U ,
m

a X ,
i=1



i

= Ka .

U -- F = M, . B = {1 ,...,m } -- U
m

,
i=1



i

= Ka . U ,

- B , Ka , B . 90


14 ( ). U -- F = M, . B -- U . U B. . C U . fC C . C , fC 0. fC C , 5 fC M. CB - , B . B -- , a X , = fC = Ka . 3
B

C CB , fC = Ka . C B . .

C C

B

U -- F = M, , I = X, V , Spart . y V . U , - LU (y ), y, , y . 7. I = X, V , -- Spart . U -- F = M, , I . y V U y . . O(y, ) = . U I , 1 = y, = Ky . , LU (y ) , 14 U LU (y ). .
LU (y )

4.2



, , , 91


(set-inclusion search problem). . , - , , ( ), , , , . (). , , , i- 0 () , i- . , i- 0, i- .
b b

,

(x1 ,...,xn ) (y1 ,...,yn ) xi yi , i = 1,n, xi ,yi {0, 1}, . , , i- 0 ( i ), i- 0 ( i- ). , ( , - -- ) , . 92


, . , . , , . . : S
bool

= B n ,B n , ,, P ,

b

B n -- n- , B n = {(1 ,...,n ) : i {0, 1} (i = 1,n)};
b

-- B n × B n ,
b

(x1 ,...,xn ) (y1 ,...,yn ) xi yi , i = 1,n; -- B n , B n ; P -- , , x B n P(x) = 1/2n A B n P(A) = |A|/2n . , , , (., , [27]), Sbool , , , -- . , [5] n- B n {(1 ,...,n ) B n : i1 = 1 ,...,ik = k }, n - k . (1 ,...,n ) B n , 1. , k , n k - B n Bk .
n

= (1 ,...,n ) B n |||| =
i=1

2n-i ž n .

, . , m k - B n , m . 93


x11 &x22 & ... &xrr , & - , i i i k {0, 1}, x0k = xik , x1k = xik , ik {1, 2,... ,n}, k = 1, 2,... ,r i i (r 1 n 1), X n = {x1 ,x2 ,...,xn }, r -- . xij = xik j = k , . , . n Kn . 0, , Kn , X n . , , , , . f (x1 ,...,xn ) , B n , , f () f ( ). . n Mn . y B n . , {i1 ,...,ik } y , 1,
y,
b

b

(x1 ,...,xn ) = xi1 &xi2 & ... &xik .

& . , 1 , , , . 2 , Mn , , Kn , X n , Sbool . 94


, Sbool 3, , , I Sbool Mn , , Kn , X n , .


4.1. V = {y1 ,y2 ,...,yk } B n yi ti (i = 1, 2,...,k ). I = B n ,V ,
b

.

4.3



-, , , [49, 51, 52, 54]. . n 15 (-). Bm -- m- n n n B A Bm . R(A) = { Bm+1 : ( A : )}. |R(A)| , A -- n Bm , R(A) -- n Bm+1 . A B n , O(A, ) =
y A b b

O(y, ).

b

. 8 ( -). A
n Bm , |O(A, )| , A -- n Bm . b

9. I = B n ,V , -- Sbool . U -- I F = Mn , , Mn -- n . V , 95

b


ž , ; ž m > 0 t U , t ž 21-m , . . V = {y1 ,...,yk }. , yi V -- m, |O(yi , )| = 2n-m , O(yi , ) -- (n - m)- B n . Al l m- m B n . , l n - m +1, |O(Al , )| = 2n- m
b m+1 b b

ž (1 - 2-l ).
b

yi V O(yi , ) = , 7 14 yi V U yi , Ci . LU (yi ), , i (i = 1,k ). , , . , , . yi V (i {1,k }), . m > 0. i = i -- i Ci , - . i , i -- U , . i -- , Ci , i . . 1. i -- U . (i ,i ) 1. , yi , (i ,i ). 96


2. , i U , - j , j {1,k }\ {i}. , Ci Cj -- , yj yi , , (i ,i ) 21-m . , yi , (i ,i ). 3. i U j . Cj1 ,...,Cjq -- , i . 3.1 yj1 ,...,yjq yjs , m. i P(O(yjs , )) = |O(yjs , )|/2n 21-m , , (i ,i ) 21-m . , yi , (i ,i ). 3.2 , yj1 ,...,yjq , m. {yj1 ,...,yjq } t m , i , , . , t 1. V . , V , yi . , i -- s ys V Cs , - , , s -- , Cs , i , (i ,s ) , Cs . V , t , i V , t , i V (t t). , t P(O(V , )), P(O(V , )), , 97
b b b b


, V , (t +1) ž P(O(V , )) = 2-n (t +1) ž|O(V , )|. - |O(V , )| |O(At , )|. m , t n - m +1, 2-n (t +1) ž|O(V , )|
b b b b b

2-n (t +1) ž|O(At , )| = m = 2-n (t + 1)(1 - 2-t )2n-m+1 = = t ž 21-m +21-m (1 - (t + 1)2-t ) t ž 21-m .

b

t > n - m + 1, y V O(y, ) \ O(V \ y, ) = , 2-n (t +1) ž|O(V , )|
b b b

2-n (t +1) × ×(|O(An- m (t +1) ž 21
m+1

, )| + t - n + m - 1)
-m

b

-m

> t ž 21

.

, . , yi V (i {1,k }), i i , . . 6. i i -- , yi , (i ,i ) , , yi . . yi V , yi , i , i , (i ,i ) , i - s . s {1,k }\{i} , i = s . i Cs , Ci , i Ci i , i i i , , 98


ys , s i , 2, , , ys ys (s ,s ), (i ,i ). 6 . yi V . , , , yi , . . 1. s {1,k }\{i} , i = s . , 6, yi 2, , , yi yi (i ,i ), 6 , , yi . 2. s {1,k } \ {i} i = s . . 2.1 s {1,k } \ {i} i s . , , i , , , , , , yi . , , yi 3.1 , , yi , (i ,i ), yi 3.2 , t 1, , yi , : (i ,i ) , i Ci . , 6, , , yi , 99


. 2.2 s {1,k }\{i} , i = s . V = {yj1 ,...,yjl } -- V , jr = i (r = 1,l). 2, , i , , , , , , V . . 2.2.1 V , yi . yi 3.1 , , yi , (i ,i ), 6 , , yi . 2.2.2 V , yi . yi 3.2 . V V -- , yi . V , , i V . 6 2.2 , . , , , , yi , . yi , . 9 . 9, . -- 16 ( ). I = B n ,V , Sbool . F = Mn , , 100
b


Mn -- . T (I, F ) 2 ž
y V

P(O(y, )) - t0 ,

b

t0 -- 0 V (t0 {0, 1}). . ti -- i V (i = 1,n). U F = Mn , , I . ( , F Sbool .) 9 V , , i > 0 t U , t ž 21-m , . ,
n

T (U )
i=1

ti 21-i .

, V y0 = (0,..., 0) 0. C0 , LU (y0 ) ( 14 ). 0 -- , C0 , (0 ,0 ) -- C0 . y0 B n , (0 ,0 ), , , 1. , (0 ,0 ) , , 0. ,
n

T (U ) t0 +
i=1

ti 21

-i

=2ž
y V

P(O(y, )) - t0 .

b

U . . 101


q q q B Å r Å rd s Ån rrd x1 x 1 Å rrÅÅ dq
n . 4.1: K1

. 16, , , .

4.4


b

17 ( ). I = B n ,V , -- Sbool . F = Kn , , Kn -- . n |V | = k m -- , 2 m < k 2 mn . +1 m n 21-i T (I, F ) 1+ +2-m k. i i=1
n . Kl -- , l ( , l). Uln , - n Kl . n . l = 1. K1 = {1,x1 ,...,xn }. n U1 , 4.1, , n K1 . . Uln 1 -- , - n Kl-1 . Uln , Uln 1 - n n , Kl \Kl-1 , . -

102


l xi1 & žžž &xil . Uln 1 - , xi1 & žžž &xil-1 , xil . , , xi1 & žžž &xil . n n Kl \Kl-1 , n Uln , Kl . n , Ul n +1 = n 1 + 1 , 1 ( -- , ), i- (i 2) n , 21-i i (i- -- , (i - 1)- ). , Uln
l

T (Uln ) = 1 +
i=1

n 1-i 2. i

I . y V , Ky . U , I , n . Um , . y V . . 1. Ky n , m. Um , Ky , y . 2. Ky m. n Ky = xi1 & žžž &xil , l > m. Um , xi1 & žžž &xim , , xim+1 & žžž &xil , y. y V , U , , , 1 I . U . U n Um . , 103


n 2, Um k , , m. , k 2-m . , m n T (I, F ) T (U ) T (Um )+2-m k = 1 + i=1

21

-i

n +2-m k. i

.

4.5


I (k, Sbool ) = {I = X, V , S
bool

k -- , : |V | = k }.

, I (k, Sbool ) T (k, Sbool , F ) = sup
I I (k,S
bool

T (I, F ).
)

17 , , 16 . 18. ( ) ? m(n) n , m = o(n), k (n) , mn 1 = o(k ) ? - n k m , F = F, , F Mn Kn F , n T (k, Sbool , F ) 21
-m

k.

. V , k - m- B n , V n Bm |V | = k . I = B n ,V ,
b

. 16 T (I, F ) 2 ž
y V

P(O(y, )) = 21

b

-m

k.

104


17
m -1

T (I, F ) 1+
i=1

21

-i

n +21 i

-m

k = 21

-m

k (1 + o(1)). ?

, 18.

4.6



, 16, . , X n , , , , , . [10]. Ud (I, F ) -- F , I . Td (I, F ) = inf {T (U ) : U Ud (Ik , F )}, Td (k, Sbool , F ) = sup
I I (k,S
bool

Td (I, F ).
)

19. F = X n , k (n), m(n) (n) , n, k (n) n (n), m(n) 1, m(n) = o(log2 n/ log2 log2 n), ? m-1

(n) , (log2 n - log2 (n))/(m(n) log2 (m(n) + 1)) n , n Td (k, Sbool , F ) 22
-m

k. 105


. . p(n) -- , pm k > (p - 1)m . p/n. : m = const, m n . p n k
1/m

n

n-

1

n(n - 1) žžž (n - m +2) (m - 1)!
1/m

1/m

= o(1), (4.1) ?

nm-1 m (m - 1)! n

=

n(m - 1)!

1/m

, , (n) = o(n). ? , (., , [5, . 282]), p n = k
1/m

n

n

-1

ne 2 (m - 1) m - 1 ž e m-1
m- 1 m

m -1

1/m

=

nm-1 nm

1/m

ž (4.2)

ž(2 (m - 1))- r(n) ,

1/ 2m

= o(1). ?

r

pm + p
i=1

mi n.

(4.3)

y B n , , y , 1. X n m + r +1 , m p , (m + i)- (i = 1,r) pmi , (m + r +1)- . (4.3) . i- X n (i = 1,m + r +1) xi , q . 106


V = { x11 x22 ...xm xm+1 ...xm+r : qj {1,p},j = 1,m; qq qm f1 fr
m

fj (q1 ,...,qm ) =
i=1

qi ž ij

-1

,j = 1,r}.

x11 x22 ...xm xm+1 ...xm+r qq qm f1 fr (q1 ,...,qm ), V |V | = pm k . , j {1,r}
m

fj =
i=1

qi ž ij

-1

p ž m ž mj

-1

= pmj .

, V m - 1 . V : x11 x22 ...xm xm+1 ...xm+r , qq qm f1 fr x11 x22 ...xm xm qm f qq
+1
1

...xm f

+r

r

.

qil = qil , il {1,m}, l = 1,s, qj = qj , j {1,m} \ {il : l = 1,s}. , s > 0. fjl = fjl , jl {1,r}, l = 1,t, fj = fj , j {1,r}\{jl : l = 1,t}. , t < s. , , t s. fj1 = fj1 , ...... fjt = fjt . s , m m qi ž ij1 -1 = qi ž ij1 -1 , i=1 i=1 ........................ m m qi ž ijs -1 = qi ž ijs -1 .
i=1 i=1

107




s

(qil - qil ) ž il
l=1 s

j1 -1

= 0,

..................... (qil - qil ) ž il
l=1 js -1

= 0.

i1 i1 i1
j1 -1 j2 -1

i2 i2 i2

j1 -1 j2 -1

js -1

. . .

js -1

. . .

... ... .. . ...

is is is

j1 -1 j2 -1

js -1

. . .

0, i1 ,i2 ,...,is -- . , , [24, . 54]. qi1 = qi1 , ...... qis = qis . q = qi1 , ...... qis = qis .
i1

. , t < s , , V m - 1 . V , V V |V | = k . I = B n ,V , -- Sbool . U -- Ud (I, F ). y V . 7 14 , U Cy y . V . Cy m + r y . y = xi1 xi2 ...xim+r , 108
b


Cy ( , ). xij (j {1,m + r}) , . P(Nxi1 &xi2 &...&xij -1 ) = 21-j . Cy , xij , Cy , , xi1 ,...,xij -1 , Cy , U -- . , , V m - 1 , , , xim ,...,xim+r , Cy . , V r + 1 , , , .
r

21
j =0

-m -j

= 22

-m

(1 - 2-

r -1

).

, T (U ) k ž 22 r(n) = [log
m+1 r -m

(1 - 2-

r -1

).

(n/p)]. r mi p(m +1) n,
r

pm + p
i=1

(4.3). r(n). , , : m = const, m n . , (4.1), 1 n r ž log2 - 1 log2 (m +1) p log2 n - log2 + log2 ((m - 1)!) m log2 (m +1) n . 109


, (4.2), n 1 ž log2 - 1 r log2 (m +1) p 1 m-1 (log2 n - log2 n - log2 (m +1) m m-1 m-1 - log2 e + log2 (m - 1) + m m 1 1 log2 (2 (m - 1)) - log2 ) = + 2m m - log2 n - log2 +(m - 1) log2 me 1 + log2 2 (m - 1) = m log2 (m +1) n . , U Ud (I, F ) n T (U ) > k ž 22-m . , n (4.4) Td (k, Sbool , F ) Td (I, F ) > k ž 22-m . . Sbool . , I . n Um-1 , 17. y V . xi1 xi2 ...xim+r . n Um-1 , xi1 xi2 ...xim-1 , xim ,xim+1 ,...,xim+r . y V . , U F I . U . n Um-1 k , r + 1 , , , 22-m (1 - 2-r-1 ),
m -1

T (U ) = 1 +
i=1

21

-i

n + k ž 22 i

-m

(1 - 2-

r -1

) = k ž 22

-m

(1 + o(1)). ?

I Td (k, Sbool , F )
<

k ž 22

-m

.

, (4.4), . 110


5


. , , , , , . ., n- , , n . , . . [15]. . , . . ( -- ) [25, 37, 38, 39, 41, 42, 45, 48, 55, 56]. . [0, 1]. [a, b] [0, 1]. , [a, b]. 111


, , , [25] . , , , , , . , , . [8]. , Yint [0, 1], Xint [u, v ] [0, 1], (u, v ), , 0 u v 1, Xint = {x = (u, v ) : 0 u v 1}. Xint Xint ,, P , -- Xint , , P -- . , P p(u, v ), B P(B ) =
B

p(u, v ) du dv .

, p(u, v ) [0, 1] × [0, 1], p(u, v ) = 0 (u, v ) Xint . , int , (u, v )int y u y v, (u, v ) Xint , y Yint . Sint = Xint ,Yint ,int ,, P . Sint . 112


5.1



F1 = {a,int : a Yint }, F1 = F 1 , . (5.1)

, Nf f F1 . , , F1 Sint , V = {y1 ,...,yk } , 1.5 , I = Xint ,V ,int . 20. I Sint T (I, F1 ) = k. . , a Yint (a, a) Na,int a Yint , , a = a (a, a) Na ,int , 5, , T (I, F1 ) = k. .

5.2


M
a,b

= {x =(u, v ) X
def int

: u b, v a}.

, (5.2) F2 = {fa,b : (a, b) Xint }, Nfa,b = Ma,b , F2 = F2 , . , Nf f F2 , y Yint y,int = fy,y , F2 Sint . . 21. p(u, v ), P Xint , , 113


I = X
y V

int

,V ,int S
y V

int

P(O(y, int )) T (I, F2 )

P(O(y, int )) + (k ),

k = |V |, (k ) = O( k ) k . . 4. . p(u, v ) c = const. k ti = i/m (i = 0,m) -- [0, 1]. m= I , Dm . . m i- (i = 1,m) fti-1 ,ti . y V . y (ti-1 ,ti ] (y [t0 ,t1 ] i = 1). , i- , fy,y , y . k V . , I . (, ) -- , , y . P(N



)

=
0

ti

1

y

y

p(u, v ) dv du =
ti- y
1

p(u, v ) dv du +
0 ti y ti- 1 y
1

1

+
0 y

p(u, v ) dv du +
i-1

p(u, v ) dv du

c ž y ž (y - t c ž (ti - t

i-1

)+ P(O(y, int )) + c ž (ti - y )(1 - y ) c + P(O(y, int )). )+ P(O(y, int )) = m

, ( k ) P(O(y, int )) +
y V

kžc . m

, 1, kžc + m. T (Dm ) P(O(y, int )) + m
y V

114


, k ž c/m + m = O( k ) k . . .
n m
j

10. fa,a =
j =1

fj , fj =
i=1

faij

,b

ij

, -

j {1,n}, fj = fa,a . . min bij = bj , max aij = aj . , Nfj = M
n 1im
j

1im f
a,a

j

aj ,b

j

. , N

=M

a,a

=

M
j =1

aj ,b

j

. , bj a aj a j {1,n},

, bj aj . , b < a, Ma,b (u, u). Ma,a (a, a), , j {1,n} , bj = aj = a, fj = fa,a , . 11. I = Xint ,V ,int -- Sint , U -- F2 , I . U , I , , (, ), 2, = 0, T (U ) T (U ). . y V . U I O(y, int ) = , LU (y ) = y,

int

= fy,y =
LU (y )

.

, , C = {C1 ,...,Cn } -- , U LU (y ),
m
j

Cj (j = 1,n) fj =
n m i=1
j

faij

,b

ij

,

fy,y =
j =1 i=1

faij

,b

ij

. 10 j {1,n}

, fj = fy,y , Cj fy,y . V = {y1 ,...,yk }. , yi (i = 1,k ) , 115


y , yi ,int . ( ) Ci . U0 , U , Ci (i = 1,k ). U0 I , U . , Ci (i = 1,k ) : , ( i ). , i = yi . , , Ci , , = i . , LU (yi ). Ci fyi ,yi , Ci fyi ,yi , Ci . LU (yl ), l = i. Ci ( f ) Ci (, f g , Nf Ng ) , , f (yi ,yi ) = 1, yl ,int (yi ,yi ) = 0, , U I . , Ci (i = 1,k ) 2 , U0 , Ci (i = 1,k ), , , U0 k , 0, . , i (i ,i ) (i = 1,k ). i 2, Ci Ci . i = 1, Ci , (i ,i ). i -- i Ci , , i 2. , . , Ci i i . Ci , i i , (i ,i ), fyi ,yi . C i . , C i fyi ,yi , Ci . i (i = 1,k ). , C i (i = 1,k ), 116


U . , , , . M . 12. V -- , V V1 ,...,Vt
t V

=
y V

M

y,y

, V --

(
i=1

Vi = V Vi Vj = , i = j ), , int

, V1 = , I = X Sint
t

,V ,int

T (I, F2 )
i=2

(|Vi | +1)P(MVi )+ |V1 |.

. U U (I, F2 ). 11, U0 , , L(U0 ) (, ), 2 T (U ) T (U0 ). U0 , , . , , , , , . , 2. t -- . Vi , i- (i = 1,t) (, V1 = ). , 1, |V1 |. , i {2,t}. i i- . , Ni MVi (i = 2,t). , i- , P(MVi ). i- (i = 2,t) , i . , P(MVi ). i (i = 2,t) 0, 117


. ,
t

T (U ) T (U0 )
i=2

(|Vi | +1)P(MVi )+ |V1 |.

U . 22. p(u, v ), P Xint , I = Xint ,V ,int Sint , T (I, F2 ) =
y V

P(O(y, int )) + (k ),

k = |V |, (k ) = O( k ) k . . , I = Xint ,V ,int , P(O(y, int )) + 1 (k ) T (I, F2 )
y V y V

P(O(y, int )) + 2 (k ),

1 (k ) = O( k ) 2 (k ) = O( k ) k . 21. . Aa -- , : Aa = {(u, v ) X
int

: 0 v - u a},
2

(5.3)

0 < a < 1/2. Aa S (Aa ) =
A
a

du dv =

a2 1 (1 - a) - =a- . 2 2 2

: 0, (u, v ) Aa , pa (u, v ) = (5.4) 1/S (Aa ), (u, v ) Aa . a , a > 1/3. P X pa (u, v ). 118
int




, y [a, 1 - a] a2 . 2 ž S (Aa ) 0 y V = {y1 ,...,yk }, yi = a +(i - 1)t, t = (1 - 2a)/k , i = 1,k . , i {1,k } a y 1 - a t < a k 1. V1 ,...,Vr -- V , 12, P(O(y, int )) = pa (u, v ) dv du =
r y 1

T (I, F2 )
i=2

(|Vi | +1)P(MVi )+ |V1 |,

I = Xint ,V ,int . P (MVi ) 5.1, 1 P(MVi ) = 2S (Aa )

, Vi V , MVi , (((|Vi |- 1)t + a)2 -
2

-((|Vi |- 1)t) - (|Vi |- 1)t2 ) = 1 (a2 +2(|Vi |- 1) ž t ž a - (|Vi |- 1)t2 ). = 2S (Aa ) ,
r

T (I, F2 ) =

|V1 | +
i=2

(|Vi | +1)P(MVi ) 1 2S (Aa )
r

|V1 | +
2

(|Vi | + 1)(a2 +(|Vi |- 1)(2ta - t2 )) =
i=2

ak a2 + |V1 | 1 - 2S (Aa ) 2S (Aa ) + 2ta - t2 2S (Aa )
r

+

(a - t)2 (r - 1) + 2S (Aa )

|Vi |2 >
i=2

>

a2 a2 k + |V1 | 1 - 2S (Aa ) 2S (Aa ) + ta 2S (Aa )
r

+ c1 (r - 1) + (5.5) 119

|Vi |2 ,
i=2


a ppppp E tttt 0 1u Vi . 5.1:

v T 1

(a - t)2 . , 2S (Aa ) t < a t k . (5.5) , |V1 | = o(k ) k , ? , . 0 < c1 < . m1 ,...,ml -- .
l l


i=1

m2 , i
i=1

mi = n, , -

n - [n/l] ž l [n/l]+1, [n/l],
l 2 i

m
i=1

=

n- 2n

n l l

n +1 l
2

2

+ l+

n l-n l

n l

2

=

n n +n- l l

l-

n n >n , l l

120



r

|Vi |2 > (k -|V1 |)
i=2

k -|V1 | . r

5.5 , t = (1- 2a)/k , , a2 k + 2 (k ), T (I, F2 ) 2S (Aa ) 2 (k ) = c1 (r - 1) + k -|V1 | (1 - 2a)a (k -|V1 |) . 2S (Aa )k r

, k , ? 2 (k ) = c1 r + c2 k/r + o(r + k/r), c1 c2 -- . , 2 (k ) r k 2 (k ) k . , a2 k = 2S (Aa ) P(O(y, int )).
y V

5.3



? F3 = F2 {f0,a : a [0, 1]}, F2 (5.1), , F3 = F3 , . , Nf f F3 . . 23. I = Xint ,V ,int -- Sint , V = {y1 ,...,yk }, 0 y1 ... yk 1.
k -1

T (I, F3 )
i=1

P(O(yi ,int )) + 2] log2 k [. 121


. k ] log2 k [, . . 2 , (), (). , , , , , . , , , . i- ( i ) yi (i = 1,k ). F3 . . V , . , V , , yi V , yj -- , yl V l {i, j }. , , . yj -- V . -- , , , f0,yj , , -- fyj ,yj . ? f0,yj , -- , f , , -- . , . i i+1 fyi+1 ,yi+1 . i 1 k - 1. U 1 . U 1 . -- U 1 , . V = {yi ,yi+1 ,...,yj }. ( V -- , .) ž i = 1 j = k , N = X ž i = 1 j = k , N



int

;
int

= {(u, v ) X

: 0 u yj }; :y
i-1

ž i = 1 j = k , N = {(u, v ) X 122

int

< u 1};


ž i = 1 j = k , N





= {(u, v ) X

int

:y

i-1

< u yj }.

, U 1 I . 1, , i = yi ,int i {1,k }. i. . i = 1. 1 , . , 1 = &fy1 ,y1 . yj V . c = yj , j = k , c = 1, j = k . , c y1 . N
1

= {(u, v ) N : u y1 , v y1 } = = {(u, v ) Xint : 0 u c, u y1 , v y1 } = = {(u, v ) X
int

: 0 u y1 , v y1 } = M

y1 ,y

1

=N

f

y1 ,y1

,

1 = fy1 ,y1 . . , i 1 i i = fyi ,yi . i+1 (i +1 k ). : i , . yl yj -- V . c1 = c2 = y l -1 , 0, l = 1, l = 1,

yj , j = k , 1, j = k ,
i+1 ,y

, c1 yi c2 y i+1 = (i &fy N

i+1 i+1

. ) = (i )&fy
i+1

,y

i+1

) ( &fy

i+1

i+1

,y

i+1

,

=

({(u, v ) X

int int int

: u yi , v yi } : c1 < u c2 }) : u yi+1 , v y
i+1 i+1

{(u, v ) X {(u, v ) X = {(u, v ) X

}=
f
yi+1 ,yi+1

int

:uy

, vy

i+1

}=N

.

, U 1 I . 123


,
k -1

T (U 1 )
i=1

P(O(yi ,int )) + 2] log2 k [.

( -- ), -- . 1 2 -- , , . , V1 V2 = , N1 N2 = . P(N



) = P


N





P(X

int

) = 1,

, . U 1 ] log2 k [ , , , 2 , , , , , 2] log2 k [. i (i = 1,k - 1) P(O(yi ,int )). ,
k -1

T (I, F2 ) T (U 1 )
i=1

P(O(yi ,int )) + 2] log2 k [.

23 . , U 1 , 23, . log2 k , . , , , , , , , , -- , [25]. [25, . 93] , 124


, , , . . 24. k N pk (u, v ), Xint , Vk k , pk (u, v ) Ik = Xint ,Vk ,int , F = F, , I , (3 log3 k - 1)k P(O(y, int )) + T (Ik , F ) 2k +1
y Vk


y Vk

P(O(y, int )) + c log2 k,

c -- , , , 2(3 log3 2 - 1) . c= 5 . k N. Vk Vk = {y1 ,...,yk }, yi = i/(k + 1), i = 1,k . pk (u, v ) p1/(k+1) (u, v ), (5.4). , P(O(yi ,int )) = 1/(2k +1) i {1,k } P(O(yi ,int ) O(yj ,int )) = 0 i, j {1,k }, i = j . , 7, , , F = F, , Ik , 3k log3 k . T (Ik , F ) 2k +1 , k , P(O(y, int )) = 2k +1
y Vk

. 125


5.4



, F4 = F3 {f-
,a

:N

f

-,a

? = Aa ,a [0, 1]}{f-,a : a [0, 1]},

Aa -- , (5.3), , F4 = F4 , . , Nf f F4 . . 25. p(u, v ), P Xint , , p(u, v ) c = const. I = Xint ,V ,int -- Sint . T (I, F4 )
y V

P(O(y, int )) + 2ž] log2 log2 |V |[+6 + 2c.

. V = {y1 ,...,yk } , y1 y2 ...yk . S = {s1 ,...,sm }, si = i/(m +1), i = 1,m. m = [log2 k ]. si (i = 1,m) li , si V , , si , , li = 0. V U 1 , 23. U 1 1 . 1 , 0 . f-,1/(m+1) F4 . , 2 , ? f-,1/(m+1) . m 2 , 2 . 126


2 , (), (). , 23, , 1 ,...,m , 1 (,,...,), m (,,...,). F3 . -- . j -- , , , . , , f0,sj , ? f0,sj . , . , U 1 1 ,...,k y1 ,...,yk . k , 1 ,...,k i (i = 1,k ) yi . i {2,k } i i-1 (i ,i-1 ) fyi-1 ,yi-1 . i {1,m}, li = 0, i li fyli ,yli , li < k , i li +1 fyli +1 ,yli +1 . U 2 . , U 2 I = Xint ,V ,int . yi V . , LU 2 (yi ) = {i ,i }. i i , fyi ,yi , , N

i





i

N

f

yi ,yi

= O(yi ,int ).

(5.6)

x = (u, v ) -- , u yi v , x O(yi ,int ). , i (x) i (x) = 1. , x A1/(m+1) . (0 ,1 ) , (0 ,2 ) -- . , i (0 ,2 ), i (x) = 0. G U 2 , , 127


. (0 ,1 ) x 1, 1 . G1 U 1 , , i (x) = 1, U 1 I . , x A1/(m+1) . (0 ,1 ) , (0 ,2 ) , 2 , , (0 ,1 ) 0. 2 , , 2 , , 1. , , 2 j , 1. , j , , , sj S , sj u. , yi < sj . i lj , u yi ylj < sj v , fylj ,ylj (x) = 1, (j ,lj ) 1. lj i , fyr ,yr , r {i, lj }, u yi yr ylj < v , fyr ,yr (x) = 1 r {i, lj }, lj i 1 x. , , , i , 1 x, i (x) = 1. , fylj +1 ,ylj +1 (x) = 1, (j lj +1 , i (x) = 0, lj +1 i . , yi sj . i lj +1, u sj ylj +1 yi v , fylj +1 ,ylj +1 (x) = 1, lj +1 . lj +1 i , 1 x, i (x) = 1. i (x) = 0. , , x O(yi ,int ), 128


i (x) i (x) = 1. , x O(yi ,int ) i (x) i (x) = 0. (5.6), ,
i

(5.7)



i

= y

i

,int

,

(5.8)

, (5.7) , N

i

N





i

= ,

(5.9)

yi , U 2 I . U 2 . N U 2 . N1 -- U 2 , , N2 = N \ N1 . T (N ) - N , T (U 2 ) = T (N ) = T (N1 )+ T (N2 ). (5.10) T (N1 ). N1 2(k - 1) , i (i = 1,k - 1) i (j = 2,k ), , (5.9), (5.8), ,
k -1 k

T (N1 )

=
i=1 k

P(N



i

)+
i=2

P(N





i

)

(5.11)


i=1 k

(P(N (P(N
i=1



i

)+ P(N





i

)) = (P(O(yi ,int )).

k
i

=





i

)) =
i=1

G1 (G2 ) G1 (G2 ), , N1 . G1 , 23. - 1 A1/(m+1) , 129


23, , , G1 , 2P(A1
/(m+1)

)

c 2c 2c - . m +1 (m +1)2 log2 k

(5.12)

, , G2 , 2 ž P(X
int

\ A1

/(m+1)

).

G1 G2 ] log2 k [ ] log2 [log2 k ][+1, (5.12) , , T (N2 ) 2 log2 log2 k +2c +6. (5.10) (5.11) 25. , U 2 , . x = (u, v ) Xint . . x. v - u < 1/([log2 k ]+1), , 23. v - u 1/([log2 k ]+1), O(log2 log2 k ) S si , x ( ), li si V x, , x. li +1 , , , x. , O(log2 k ), O(log2 log2 k ). x , 25. 130


5.5



G1 = {gž,m (u, v ) = max(1, ]u ž m[) : m N}, G2 = {g,a (u, v ) = G3 1, u a : a [0, 1]}, 2, u > a (5.13) (5.14)

= { g-,m (u, v ) = = 1, 2 0 v - u < 1/m : m N}, (5.15) (5.16)

F5 = F1 ,G1 G2 G3 ,

F1 (5.1). . 26. I = Xint ,V ,int -- , Sint , F5 -- , (5.13)-(5.16) R(I ) =
def y V

P(O(y, int )). , -

p(x), P, c, R(I ) < T (I, F5 , 4 |V |- 1+6 c[log2 |V |]) R(I )+5. . V = {y1 ,...,yk }, y1 žžž yk , V -- , . 4. , . , 0 . , , . 1 , -- 2 . m -- , . g-,m (u, v ) G3 . 1, 2. 131


1 V , 3.1, G2 , f=,a a,int F1 . D. D D, -- D. , yi , i (i = 1,k ). i (i = 1,k - 1) , i+1 , yi+1 ,int F1 . (k - 1)- . 2 (, , , ) m - 1 , 1 m - 1, 2 gž,m G1 (, m -- ). , 2 m - 1 , gž,m m . , 2 i, i . S = {s1 ,...,sm-1 } , si -- V , ysi -- i/m (i = 1,m - 1), , si = 0. k , 1 ,...,k . i (i = 1,k ) yi ( yi -- i i ). i (i = 2,k ) , i-1 , yi-1 ,int F1 . (k - 1)- . i . si = 0, i , si , ysi ,int F1 . si < k , i , si +1 , 132


ysi +1 ,int F1 . , i (i = 1,m - 1), . U0 . , U0 I = Xint ,V ,int . yi V U0 , LU0 (yi ) = {i ,i }. O(y, int ) = Ny,int i i , yi ,int , N

i





i

O(yi ,int ).

1 , yi V Ni O(yi ,int ),
i

, , , x O(yi ,int ) i (x) = 1, i (x) = 1, i , i . Aa = {x = (u, v ) : 0 v - u a}. yi V . , x = (u, v ) A1/m O(yi , int ). , v - u < 1/m u yi v . , i . g-,m (x) = 1, (0 ,1 ) 1. , (0 ,2 ) 0. 9 , D ( 1 ) , 1 j , yj , u V , [u, v ] ( , yi [u, v ]). , u yj yi v . , , yj yi , . , x , i . 133


, i (x) = 0, i (0 ,2 ), x, , 0. , x = (u, v ) (X \A1
/m

) O(yi ,int ),

v - u 1/m u yi v . g-,m (x) = 2 (0 ,1 ) 0, (0 ,2 ) 1. j {1,m - 1} -- , j/m -- u . , gž,m (x) = j . v - u 1/m, j/m [u, v ]. . 1) yi j/m. u yi ysj v , ysj -- j/m V . , , j sj 1. , , sj i , 1, 0 yi ysj v . , i (x) = 0, sj +1 , i . 2) yi > j /m. u ysj +1 yi v . , , j sj +1 , 1, , sj +1 i , 1 x. i (x) = 0. , yi V x X : xint yi U0 x , - ( ) i i . , U0 I . U0 . x A1/m . T (U0 ,x) 1 + (] log2 k [-1) + 2 + |JU0 (x)|. 134


g-,m 0 . , , D. , D, , . , , , ( ). , x X \A1/m . T (U0 ,x) 1+1+2+ |JU0 (x)|. g-,m , -- gž,m 2 , -- , , j , 2 . , , , , , , , . , yi , , i i 1, , , . U0 . T (U0 ) = Mx T (U0 ,x) = P(A1/m ) ž (2+] log2 k [) + +P(X \A1/m ) ž 4+ Mx |JU0 (x)| P(A1
/m

) ž ([log2 k ] - 1) + 4 +
y V

P(O(y, int )) P(O(y, int ))
y V

c ž ([log2 k ] - 1)

2 1 -2 mm

+4+

2c ž ([log2 k ] - 1) +4+ m

P(O(y, int )).
y V

U0 I , JU0 (x) = {y V : xint y }, 135


, Mx |JU0 (x)| =
y V

P(O(y, int ))

. U0 : Q(U0 ) 2+(2k - 1) + (k - 1) + (k - 1) + m +2m. , 0 . D. . -- , 2 . , , , i (i = 1,m). m = 2 c [log2 k ] T (U0 ) 5+
y V

P(O(y, int )),

Q(U0 ) 4 k - 1+6 c[log2 k ], 26. , . V = {y1 ,...,yk }, . . c , m m = 2 c [log2 k ], c , , , c = 2. V S = {s1 ,...,sm-1 }, . , . - x = (u, v ) . x. 1/m, V u . , , V -- v 136


-- , v . , , log2 k . v - u 1/m, gž,m j j/m, [u, v ]. , sj , V -- u. u, , sj +1, V -- v , v . , , 4 ( v - u 1/m, gž,m , 1 , , 1 , ). , m , 1, , , . , , , log2 k , S .

137



[1] - . ., . . . (1962) 146, 263-266. [2] ., . . , , 1982. [3] . . . (1985) 283, 2, 265-269. [4] ., ., . . , , 1979. [5] . ., . . . , , 1992. [6] . . . (1991) 3, 2, 69-76. [7] . . . (1992) 4, 3, 118-127. [8] . . . (1995) 7, 2, 40-60. [9] . . . (1996) 8, 4, 108-122. 138


[10] . . . (1998) 10, 1, 63-72. [11] . ., . . . (1999) 11, 4, 139-144. [12] . . . (1958) 118, 427-430. [13] . . . III ( ). . (1968), . 20, 181-200. [14] . . . , , 1989. [15] . . . 3, , , 1978. [16] . ., . . . , , 1991. [17] . ., . ., . . . , , 1985. [18] ., . . . . (1987) 24, 5-96. [19] . . . (1963) 10, 63-97. [20] . . . , , 1986. [21] . . , , 1980. [22] ., . . , , 1971. 139


[23] . . . . - -, , 1994, 175 . [24] ., . . , , 1978. [25] ., . : . , , 1989. [26] . . . (1979), 3, 68-74. [27] . , . , , 1973. [28] . . , , 1979. [29] . ++. , , 1991. [30] . . , , 1985. [31] . . . , , 1975. [32] . , 1975, . 1. : "- "(.359), "- "(.359-400). [33] . . . , , 1979. [34] . . . . (1958), . 1, 75-127. [35] Bayer R., McCreight E. M. Organization and Maintenance of Large Ordered Indexes. Acta Informatica (1972) 1, 3, 173-189. 140


[36] Ben-Or M. Lower bounds for algebraic computation trees. Proc. 15th ACM Annu. Symp. Theory Comput. (Apr. 1983) 80-86. [37] Bentley J. L. Multidimensional binary search trees used for associative searching. Commun. Ass. Comput. Mach. (Sept. 1975), 18 509-517. [38] Bentley J. L., Friedman J. H. Data structures for range searching. Comput. Surveys (1979), 11 397-409. [39] Bentley J. L., Maurer H. A. Efficient worst-case data structures for range searching. Acta Inform. (1980), 13 155- 168. [40] Bentley J. L., Saxe J. B. Decomposable searching problems. I. Static-to-dynamic transformation. J. Algorithms (1980), v. 1, 301-358. [41] Bentley J. L., Stanat D. F. Analysis of range searching in quad trees. Inform. Processing Lett. (1975), 3 170-173. [42] Bolour A. Optimal retrieval algorithms for small region queries. SIAM J. Comput. (1981) 10, 721-741. [43] Borodin A. B. Computational complexity -- Theory and practice. Currents in Theory of Computings. Englewood Cliffs, NJ: Printice-Hall, 1973, 35-89. [44] Bottenbruch H. Structure and use of ALGOL 60. JACM (1962) 9, 161-221. [45] Chazelle B. M. Filtering search: a new approach to queryanswering. Proc. 24th IEEE Annu. Symp. Found. Comput. Sci. (Nov. 1983), 122-132. [46] Dobkin D. P., Lipton R. J. On the complexsity of computations under varying sets of primitives. J. Comput. Syst. Sci. (1979) 18, 86-91. [47] Dumey A. Indexing for Rapid Random Access Memory Systems. Computers and Automation. (1956) 4, 12, 6-9. 141


[48] Fredman M. L. A lower bound of the complexity of ortogonal range queries. J. ACM. (1981) 28, 696-705. [49] Harper L. H. Optimal numbering and isoperimetric problem on graphs. J. Combin. Theory (1966) 1, 3, 385-393. [50] Hibbard T. N. Some Combinatorial Properties of Certain Trees with Applications to Searching and Sorting. J. ACM (1962) 9, 1, 13-28. [51] Katona G. O. H. A Theorem on finite sets. Theory of Graphs, Proc. Col loq. held at Tihany. Hungary, (1966), 187-207. [52] Katona G. O. H. The Hamming-sphere has minimum boundary Studia Scient. Math. Hungarica (1975) 10, 131- 140. [53] Knuth D. E. Optimum Binary Search Trees. Acta Informatica (1971) 1, 14-25. [54] Kruskal F. B. The number of simplices in compex. Mathematical Optimization Techniques (1963), 251-278. [55] Lee D. T., Wong C. K. Worst case analysis for region and partial region searches in multidimensional binary search trees and balansed quad trees. Acta Informatica (1977) 9 23- 29. [56] Lueker G. S., Willard D. E. A data structure for dynamic range queries. Inform. Processing Lett. (Dec. 1982) 15, 5, 209-213. Commun. ACM (1971) 14, 4, 228-239. [57] Maurer W. D., Lewis T. G. Hash table methods. Commputing Surveys (1975) 7, 5-20. [58] Peterson W. W. Addressing for Random Access Storage. IBM J. Research & Development (1957) 1, 130-146. [59] Preparata F. P., Shamos M. J. Computational Geometry. Springer-Verlag, New York, 1985. [60] Rabin M. O. Proving simultaneous positivity o linear forms. J. Comput. Syst. Sci. (1972) 6, 639-650. 142


[61] Reingold E. M. On the optimality of some set algorithms. J. ACM (Oct. 1972) 19, 4, 649-659. [62] Schay G.,Jr, Spruth W. G. B. Analysis of a File Addressing Method. Comm. ACM (1962) 5, 459-462. [63] Steele J. M., Yao A. C. Lower bounds for algebraic decision trees. J. Algorith. (1982) 3, 1-8. [64] Turing A. M. On Computable Numbers, whis an Application to the Entsheidungsproblem. Proc. London Math. Soc. (1937) 42, Ser 2, 230-235. [65] Ullman J. D. A Note on the Efficiency of Hashing Functions. JACM (1972) 19, 569-575. [66] Yao A. C., Rivest R. L. On the polyhedral decision problem. SIAM J. Comput. (1980) 9, 343-347.

143


.. . M., , 144 . -

05.05.2005 . 60×90 1/16. 9,0 .. 8 250 . - . , . 04059 20.02.2001 . -