,,,
" "
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=,
0δ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.
"
Copyright (c) 2024 Stud-Baza.ru , , , .