. , , ,

,,,

,

" "

 

 

2002


25 , 10 , 5 , 1

: , , , , , , , , -

: .

: .

: , .

: , , .

: , .


1.

2. -

2.1 -

2.2

3.

4.

4.1

4.2

4.3


. , . , . , . :

1.         , .

2.         , , .

3.         , , .


1.

, tk si, , . . . , S, , ( ) ( ) , . ( , ) ( ). .

ti . si tk (1) , - sj , tk-1 si. (1) = . . , tr n2

.


. , . , ; . , , τ , .

.

. , . , , .

, ,, - , 1.

. : , , si, sj r . r P(r) r- P(r)=pr. r- : .

. . si , sj () r, pij(r)>0, pij(q)=0 q. . , - . .

si sj, r q pij(r)>0, pji(r)>0, . sj si, si sk, sj sk. () . , , . , . , si , pii=1, pij=0. , , . .

( ) Δt i j :

().


λij t, , Δt, , .

, , , , . .

.

, . , pj , .. , .

, . , , [λij] , λij=pijλi, {1/μ1, 1/μ2, , 1/μn}.

, . , [pij] .

. , ( ). S P(0) , , P=[pij] .

, , .


2. -

. (), (), , , .

. , . ( ) , , , , .

, , , . , - () , .

- ( ). , . , , .

, - , , , . .

2.1 -

, - ( ) , , . ( ) - .

, X, F(x). , F(x), , , :

.

xi , . N- .

. . p. , , .. 0, 2, 4, 6, 8, 10. , 2k, :

,

(1)

, , ( ) . . ξ, [0,1]. ξ<p p, ..

P {ξ<p}=p.


. 1, [0,1]. ξ, [0,1], [0, p] ( ) , .. p. ξ p. ξ<p, , . . (1001000) , , (1).

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

, (, β- ) .

( ) , , . , . , , , .

- , , . .

- , . . , -, , , . , -, , . , , .

, . , N=. , n n>3 () - . , . -, , , , .

, 100 . (, , .), , .. 1001000 . . , , . , . , . -. , .

. , [0,1]. , . . X,

.


y x, .. y=F(x), . , , F(x), y , [0,1], ( ), , F(x), ..

. (2)

X F(x). , . F(x) Y, X (2) (. 2).

,


.

, Y [0,1], . .

.

Y

.

X , , (. 2), X. , , F(x). , [0,1] . , , , : 0 1

z1, z2, z3, ξ*


, ξ*, [0,1],

.

k. 2k. , .. , . . k :

. (3)

(3) 2-k.

.

.


,

, (4)

:

. (5)

:

,

,

,

, (4), :

. (6)


(5) ξ* k. k.

, (7)

.

, ξ (3)

, i=0,1,2,, 2k-1

p=1/2k.

ξ (5) (6), (7). ,

;

.

. (8)


, [0,1] x

(8) , σ . ξ η , η [0,1] (. 1).

1

k 2 3 5 10 15

σξη

1,29 1,14 1,030 1,001 1,00

. 1 , k>10 .

zi (i=1,2,, k), 0 1 1/2. : . , .

. , , . , zi=1, , zi=0. , zi=1. k, Δt, :

.

.

, λΔt P{Zi=1} 1/2.

zi . u(t), . , , , u(ti) . a

a ,

.

zi. u(ti) u(ti+1), Zi :


u(ti) a u(ti+1) a , . . , P {u(ti)>a}=W ti. A1Hv. Hv , v

u(ti) a; u(ti+1) a. (9)

A1Hv

P{A1Hv}=W (1-W) [W2+(1-W)2]v.

, v (9) A1. W (1-W), (9)

W (1-W) [W2+(1+W)2]

..

.


, W=const, . zi :

W=P {u(ti)>a}=1/2+ξ.

P{Zi=1}=2W (1-W)=1/22ξ2.

ξ, P{Zi=1} 1/2.

. , , . . , , , . . . u, [0,1], .. .

un=u [mod 2-n], (10)


u [mod 2-n] u 2-n. , un [0,1].

(10) . . .

1. u = 0,10011101 = 1·1/2 + 0·1/22 + 0·1/23 + 1·1/24 + 1·1/25 + 1·1/26 + 0·1/27 + 1·1/28 +

n=4. {u mod 2-4} = 0,1101

, . . , , .

(. 3). L α1, , αL , αi αj , , , αL+1 αk ().

T=L-i+1. i (. 3).


, ( ) . .

2.2 -

- , . , , p1=0,8 p2=0,805 . , - 0,010,05 .

. - .

,

M N . M/N

, (11)


. (12)

, -. (11) (12):

,

,

p0 . M/N mx X.

.


, , ..

. (13)

2. , x . -. δ = 0,1  p = 1-p0 = 0,9 σx = 1 . N. (13) :

.

δ=0,1  p=0,9.


3.

, . , , .

, , , - .

, .

, -: , , . . . , . ( ) .

, . . G0 G11 G12 G11 G21 G22 -, . 4.

() () , .

, .

( 3) .

3.

a1=18, a2=16, a3=13. , , b1=12, b2=10, b3=8, b4=6, b5=5, b6=4. . , . , , . , .

. , . . , a2 b2 b5, , .

, , . 5. () () , . . {1, 2, 3} , , , , , . ( ) . , {2, 1, 3} , a1 ..


, . , . , , , 447 . . , , : , . . , , . . :

{(b2, b3), (b4, b5, b6), (b1)};

{(b1, b4), (b2, b5), (b3, b6)};

{(b1, b4), (b2, b6), (b3, b5)};

{(b1, b5), (b2, b4), (b3, b6)};

{(b2, b3), (b1, b6), (b4, b5)};

{(b1, b6), (b2, b4), (b3, b5)};

{(b2, b4), (b1, b6), (b3, b5)}.

, . . , , .

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


4.

4.1

. : (CPU), (HDD), - (IOI). (OS) , . (j). . : ; ; ; . .

, GBD (MDBk). , .

i , :

          i- (j-) (l-) i=||ijl||;

          , i i- j- (MFi=||Fi(tjl)||);

          j- , i (jOi) j- , j- (nOi).

. :

          MDBjk (Mqj=||qjks||);

          , MDBjs , MDBjk (j=||Fj(Vobjs)||);

          MDBjk, (kO), MDBjk, j- (mOj).

4.2

j- . j- , (Voni) (HDD). j- . . j- (Δt) , , j- . , j- . FIFO.

, i, i. , i i , - .

. : ; ; i- .

, . .

, i- Ti, (ηCPU) (ηHDD) -. (N) i- i=1,, n () (i, ηCPUi, ηHDDi). N n (i, ηCPUi, ηHDDi). .

1. (i) (ηCPU, ηHDDi) . , 5, 5. 1 - .

N h- (h- , h=0,, 5) - , :

M1ih=||(MTih, DTih)||; M2ih=||(MηCPUih, DCPUih)||; M3ih=||(MηHDDih, DηHDDih)||.

2. M1ih, M2ih, M3ih h- : (h, h); (MηHDDh, DηHDDh); (MηHDDh, DηHDDh) :

MYh=, DYh=,

i1 i- ;

m0 ;

mi i- ;

Yh , (, ηCPU, ηHDD).

4.3

.

1.         (i=1).

2.         (1<i<m0).

3.         (i=m0).

. .

0. Tξ(STR).

1. STR n (|STR| = n). Tξ(STRi1), i=1,, n. , i- , n-1 i. Tξ(STRi1) i- (i1) . .

2. STR n-1 (|STR| = n-1). , i (i1) . n-1 , , Tξ(STRi2), i=1,, n-1, , i , n-2 i. Tξ(STRi2) i- (i2) . . .

k (k>2). STR n-k+1 (|STR| = n-k+1). , k-1 . n-k+1 , , Tξ(STRik), i=1,, n-k+1. Tξ(STRik) i- (ik) k-. . k- k .

n. STR 1 (|STR| = 1). , . , Tξ(STRin), i=1, () .

, .


- . , , , .

, , , . , . 1960 . , , , . , , .

, , .

, .


1.      ..  . ., , 1987.

2.      ..,  .., . .: , 2000.

3.      ..,  .., . .: , 1969.

4.      ..,  ..  . 2. , 1999.

5.      ..  . .: , 1988.

6.      ..,  ..  . .: , 1994.

7.      ..,  ..,  ..  // . . 2002. 6 (15)  . 79.

8.      ..  . 1. .: , 1973.

9.     Land A.H., and Doig A.G. An automatic method of solving discrete programming problems. Econometrica. v28 (1960), pp.497520.

10.  Little J.D.C., Murty K.G., Sweeney D.W., and Karel C. An algorithm for the traveling salesman problem. Operations Research. v11 (1963), pp. 972989.

&quot;

 

 

 

! , , , .
. , :