close

Вход

Забыли?

вход по аккаунту

?

Модификация алгоритма выделения структурных особенностей.

код для вставкиСкачать
Y~K
519.854.64
H. B.
BeCTHHK CTI6ry. Cep. 10, 2006, Bblll. 2
O/l,e.M,C1WU
MO,l1;H<I>HKAD;H.5I AJIrOPHTMA BhI,l1;EJIEHH.5I
CTPYKTYPHhIX OCOBEHHOCTEH *)
1. BBe,a;eHlIe. CTPYKTYPHbIM MeTO,n; IfHTerpHpOBaHIUI ClfCTeM m 06bIKHOBeHHblx ,n;mp­
<pepeHIIHaJIbHbIX ypaBHeHlfM [1-7] caMoro q6IIIero BH,n;a
z~
= <Pk(X,Zl, ... ,Zm),
k
= 1, ... ,m,
(1)
(1)
npe,n;nOJIaraeT, 'ITO cYIIIecTByeT npe06pa30BaHHe, nplfBO,1J;5IIIIee clfcTeMY
Y~
= fo(X,Yo,Yl,···,Yn),
(2)
i
= 1, ... ,l,
(3)
,n,
(4)
j = 1 + 1, ...
1 E {O} UN,
K BH,n;y
n E {O} U N,
1 ~ n,
n
Ys: [XO,X k ]-+ R T . ,
S
= O,l, ... ,n,
LTs = m,
s=O
v=i
f j .. [X0, X]k
X
R T- fi - -RTj
t,
n
j
= 1+ 1, ... , n,
fj
= LTv.
v=j
r pynnbI ypaBHeHlfM
rpynn ypaBHeHlfM
(3), (4) CTpyKTypHO TO)K,n;eCTBeHHbI. Ka)K,n;oe ypaBHeHHe O,n;HOM H3
(3), (4)
3aHHMaeT onpe,n;eJIeHHOe MeCTO B nOCJIe,n;OBaTeJIbHOCTH ypaBHe­
HlfM cBoeM rpynnbI. Ero npaBa5I 'IaCTb He 3aBHCHT OT IfCKOMbIX <PYHKIIlfM, nOBe,n;eHlfe KO­
TOPbIX onHCbIBaeTCH 3TlfM If BceMH nOCJIe,n;YIOIIIHMH ypaBHeHlf5IMH TOM )Ke rpynnbI. 3,n;ecb
(2) - npe,n;cTaBHTeJIb «o6IIIeM» rpynnbI, B KOTOPYIO BOllIJIH Bce ypaBHeHH5I, He HMeIOIIIHe
crpyKTypHbIX oco6eHHOCTeM YKa3aHHOrO BbIllIe THna.
CJIe,n;yeT OTMeTHTb, 'ITO B paCCMaTpHBaeMOM CHCTeMe MO)KeT OTCYTCTBOBaTb KaK 06IIIa5I
rpynrra ypaBHeHHM (2) (TO
0), TaK H rpynna ypaBHeHlfM (3) (l 0, n EN).
B Ka'IeCTBe npe06pa30BaHlf5I, npHBo,n;5IIIIerO cHcTeMY (1) K BH,n;y (2)-(4), BbI6HpaeM ne­
=
=
pecTaHoBKY (nepeo603Ha'IeHHe) ypaBHeHHM CHCTeMbI
(1). 3a,n;a'Ia COCTOHT B TOM, 'ITo6bI
YKa3aTb TaKOM nOp5I,n;OK CJIe,n;OBaHH5I ypaBHeHHM If HyMepaIIHH nepeMeHHbIX HCXO,n;HOM CHC­
TeMbI (1), npH KOTOPOM ,n;JI5I npe06pa30BaHHOM CHCTeMbI
7rZ'
= 7r<p(x, 7rz)
(5)
.) Pa60Ta BblnOJIHeHa npl1 <pHHaHcoBoH nOp)WP)KKe PoccHiicKoro <poHp;a <PYHp;aMeHTaJIbHbIX HCCJIep;OBa­
IillH (rpaHT Ng 05-05-65318).
© J1. B. OJIeMCKOH, 2006
55
(2)-(4)
C BhI,n;eJIeHHhIMM OC06eHHOCT51MM
3<p<peKT OT rrpl1MeHeHI151 CTPYKTypHoro rrO,lI,Xo,n;a
6y,n;eT MaKCI1MaJIhHhIM, T. e. MaKCI1MaJIhHO OTHOlIIeHl1e
3,n;ech 11 B ,n;aJIhHeMlIIeM
1f
nz
= (n(l), n(2), ... , ... , n(m))
L:::ro+1 W1f (s)! L:;~I w1f(s) .
= (Z1f(I) , Z1f(2) , ... , Z1f(m)) T,
-
mp
= (<P1f(I), <P1f(2) , ... , <P1f(m)) T ,
1m = {1, 2, ... , m} ,
rrepecTaHoBKa 3JIeMeHTOB MHO)KeCTBa
orrpe,n;eJI.HIOIlI,a51 rrop51,n;OK CJIe,n;OBaHI151 ypaBHeHI1M CI1CTeMhI
(1) .
TIpl1'-IeM 3,n;eCh (,n;JI51 HarJI.H,l1­
n(i)
(5). C
HOCTI1 M3JIO)KeHM51 aJIrOpl1TMa M rrOCTaHOBKI1 3a,n;a<m) paBeHCTBO
ypanHeHl1e CMCTeMhI
(1)
6y,n;eT 3aHl1MaTh i-e MeCTO B CI1CTeMe
YCTaHOBI1Th CB513h Me)K,n;y ypaBHeHM51MI1'I1CXO,n;HOM CI1CTeMhI
(1)
=j
03Ha<-J.aeT, <-J.TO j-e
Y<-J.eTOM 3Toro MO)KHO
M CI1CTeMhI
(2)-(4):
Ys = (Z 1T (","-I
+1)'Z1f (","-I
rv))T,
L..." =0 rv
L..."v=o rv +2)" ",Z1f("'"_
L.."I.I_O
1.1
/s
= (<p 1f(L~:~ rv+I)' <P 1f(L~:~ rv+ 2)' ... , <P1f(L~=o r v )) T,
S
= 0, ... , n.
,ll;aJIee, Ws - BeCOBhle K03<p<pMll,l1eHThI, JIl160 3a,n;aBaeMhle rrOJIh30BaTeJIeM, JIl160 paCC<-J.I1ThIBa­
eMhle KaK OTHOCI1TeJIhHhle ,n;OJIM 3aTpaT (<-J.I1CJIO apM<pMeTI1<-J.eCKMX Orrepall,MM, BpeM51) BhI'-ll1C­
JIeHI151 rrpanOM <-J.aCTM
<Ps
<P = (<PI, <P2, ... , <Pm),
S
HOBOK 113 m
B [8]
K BI1,n;y
3JIeMeHTOB
OT o6IlI,ero <-J.MCJIa orrpe,n;eJIeHI1M BCeX KOMrrOHeHT BeKTOp-<pYHKll,Hll
= 1, ... , m.
1m
0603Ha<-J.I1M <-J.epe3
P = {n} -
MHO)KeCTBO Bcex rrepeCTa­
= {1,2, ... ,m}.
paCCMaTpI1BaJIC51 <-J.aCTHhIM CJIyqati: peIlleHI151 3TOti: 3a,n;a<-J.M -
(2)- (4)
B rrpe,n;rrOJIO)KeHI1M BhII10JIHeHI151 paBenCTB:
WI
=
aJIrOpl1TM rrpl1Be,n;eHIDI
W2
= ... =
B [9~
Wm .
paCCMOTpeHO o606IlI,eHMe ,n;anHOrO aJIrOpMTMa Ha CJIY<-J.aM HepaBHOrrpaBHhIX rrpaBhIX <-J.acrell
Wt
i=
Wd,
'It, d Elm , t
i=
d.
TIpe,ll,JIaraeMhle 3,n;eCh ycoBeplIIeHCTBOBaHI151 aJIrOpl1TMa 11 e m
<popMaJIM3all,M51 rr03BOJIl1JIM rrOBhICI1Th 3<p<peKTMBHoCTh pa60ThI aJIrOpl1TMa, 113JIO)KeHHoro B
[9],
11 ,n;aTh KOMrraKTHoe rrpe,n;CTaBJIelme caMOM ero Tpy,n;oeMKoM rrepe6opHoM <-J.aCTI1 B BH,!l.e
6JIOK-CXeMhI.
2. OCHoBHble nOH.HTH.H.
2.1. MaTpl1ll,y A = {aij }rj=1
Onpe,n;eJIeHHe
'4eil
6y,n;eM Ha3hIBaTh cmpy~myp'/-tOil
CI1CTeMhI 06hIKHoBeHHhlx ,n;11<p<pepeHll,l1aJIhHhIX ypaBHeHI1M
(1)
11 o603Ha<-J.aTh
.Mampu­
A( <p),
ec.llll
ee 3JIeMeHThI
0,
aij = { 1,
ecJtu
eCJtu
TaK, CTPYKTypHa51 MaTpMll,a CI1CTeMhI
AU) =
<Pi 'He aaeucum om Zj,
<Pi aaeucum om Zj.
(2)-(4)
*
MMeeT 6JIO<-J.HhIM BM,n;
*
*
*
*
*
*
*
*
*
OqXrl
*
*
*
*
*
*
Or/xr/
*
Or/+I xr/+I
*
*
*
*
*
Orlxr/
*
*
*
Or/+I xrn
*
Orn Xrn
3,n;eCh 11 B ,n;aJIhHeMlIIeM Or; xrj - HYJIeBM MaTpMll,a pa3MepHOCTI1 ri X rj. CI1MBOJIOM
*~
3Ha<-J.eHhI 6JIOKM, KOTophle MoryT 6hITh M HeHYJIeBhIMI1.
Onpe,n;eJIeHHe
2.2.
MHO)KeCTBO, 3JIeMeHTaMM KOToporo 51BJI51IOTC51 HOMepa KOMrrOHelll
I1CKOMOti: BeKTop-<pYHKll,I1M Z
56
= {Zl,
. . . , ... ,
Zm},
OT KOTOPhIX He 3aBMCl1T rrpaBa51 <-J.aCTh i­
(1),
ypaBHeHlUl CO,1l;Y
CO,1l;Y
(1)
Ei(tp),
Ei(tp)
2.3.
Onpep;eJIeHHe
(1),
CO,1l;Y
Z
M 0603Ha'IaTb
r
= {j E 1m
: aij
= 0,
A(tp)
= {avtJ,}mV,tJ,--I}.
MHO)KeCTBO, 3JIeMeHTaMM KOToporo 5lBJI51IOTCH HOMepa ypaBHeHMM:
6y,z:t;eM Ha3bIBaTb j-M
eepmU'lW.fI,'b'H'btM CTpyKTypHbIM
MHO)KeCTBOM CO,1l;Y
Hj(tp):
= {i E 1m
Hj(tp)
I1YCTb
CTpyKTypHbIM MHO)KeCTBOM
T.e.
C rrpaBbIMM 'IaCT51MM, He 3aBMC51Ill,MMM OT j-M: KOMrrOHeHTbI BeKTop-<pYHKll,MM
= {ZI, •.. , Zm},
(1)
20pU30'Hma.fl,'b'H'btM
6y,z:t;eM Ha3bIBaTb i-M
M 0603Ha'IaTb
= (rO,rl, ... ,rn) E
: aij
({O} U N)
X
= 0, A(tp) = {avtJ,} V,tJ,­
m -I}.
Nn.
BBe,z:t;eM B paCCMOTpeHMe
k-I
b(r, k)
= L ri,
b(r, 0)
= 0,
b(r, n + 1)
= m.
i=O
Onpep;eJIeHHe 2.4. By,z:t;eM rOBopMTb, 'ITO CO,1l;Y (1) MMeeT 'Hy.fl,'b-cmpy'K:mypy C rrapa­
1 E {O}UN, n E N, 1 < n, T (rO,rl, .. . ,rn ) E ({O}UN) X Nn, M 0603Ha'IaTb ee
=
MeTpaMM
ZS:;[l, n, r],
eCJIM ,z:t;JI51 ropM30HTaJIbHhIX MHO)KeCTB crrpaBe,z:t;JIMBbI BKJIIO'IeHM51
{b(r,i)
{b(r,j) + 1, ... ,b(r,n + I)} C E 6(r,j)+tJ,(j)(tp) ,
r,z:t;e
J.L(s)
= 1, ... ,l, n> 1 > 0,
= 1 + 1, ... ,n, n> l;?! 0,
+ 1, ... ,b(r,l + I)} C E 6(r,i)+tJ,(i)(tp) ,
i
i
= 1, .. . ,rs ; S = 1, ... ,n.
MO)KHO BBeCTM 3TO )Ke rrOH51TMe, MCrrOJIb3Y51 orrpe,z:t;eJIeHMe CTPYKTYPHOM: MaTpMll,bI.
Onpep;eJIeHHe
1 E {O} U
MeTpaMM
ee
ZS:;[l, n, r],
2.5.
N, n
By,z:t;eM rOBopMTb, 'ITO CO,1l;Y
E
N, 1 < n, r
(1)
= (ro, TI, ••. , rn)
E
MMeeT HyJIb-CTpyKTYpy C rrapa­
({O} U N) X Nn,
A(tp) CO,1l;Y (1)
eCJIM ,z:t;JI51 3JIeMeHTOB CTPYKTYPHOM: MaTpMll,bI
M 0603Ha'IaTb
crrpaBe,z:t;JIMBbI
paBeHCTBa
a~(s)V(s)
r,z:t;e
= 0,
S
= 1, ... , n,
= b(r, s) + 1, ... , b(r, s + 1);
I/(s) _ { b(r,s) + 1, ... ,b(r,l + 1),
b(r,s)+I, ... ,b(r,n+l),
~(S)
TaK, CO,1l;Y
(2)- (4)
MMeeT HyJIb-CTpyKTypy
CTPYKTYPHa51 MaTpMll,a CO,1l;Y
(1)
eCJIM
0< 1 < n
eCJIM
O~l<nMs>l.
M
s
~
l,
ZSi[l, n, r].
C HYJIb-CTPYKTYP0M:
ZS:;[O, n, r], n E N
MMeeT BM,z:t;
*
*
Onpep;eJIeHHe
npeae.fl,'b'l-wJ£,
2.6.
*
By,z:t;eM rOBopMTb, 'ITO HyJIb-CTpyKTypa
M 0603Ha'IaTb ee
ZSm cp[l, n, r],
ZS:;[l, n, r]
CO,1l;Y
(1) ­
eCJIM crrpaBe,z:t;JIMBbI HeBKJIIO'IeHM51
{b(r, 1), ... ,b(r,l + I)} <t. Ec5(r, I)(tp) , 1 > 0,
57
ct Eo(r,l+ll(<P), I ~o.
{b(r,I+1), ... ,b(r,n+1)}
Onpe,n;eJIeHHe 2.7.
nOHHMaTb BeJIH'-:IHHY
I1o,n; 067jeMOM 'Hy.lt'b-cmpy'K:myp'bt
E:=ro+l Wv
H 0603Ha'-:laTb ee
ZS~[I,
IZS~[I,n,r]l,
n, r] CO,LI)T (1)
r,n;e Wv -
6y,n;eM
BeCOBble K03<p­
<pHIIHeHTbI.
MO:tKHO nOKa3aTb, '-:ITO
Izsm7fcp[l, n, r]1 > IZS:cp[i, it, f] r,j)7f E P.
C<pOPMYJIHpyeM C HCnOJIb30BaHHeM BBe,n;eHHbIX nOH}lTHM ,n;Be paCCMaTpHBaeMble 3,n;eCb
3a,n;a'-:lH . .
f
3a,n;aqa 1.
HaifTH nepeCTaHOBKY
7f* E
3a,n;aqa 2.
HaMTH nepeCTaHOBKY
7f* E P
TaKYIO, ,n;JI}I KOTOPOM cnpaBe,n;JIHBO HepaBeHCTBO
TaKYIO, ,n;JI}I KOTOPOM cnpaBe,n;JIHBO HepaBeHCTBO
Bcp(Wl ,W2, . .. ,Wd) C 1m 6y,n;eM Ha3bIBaTb 3.1teMe'Hm ­
'H'btM 'Hy.lt'b-cmpy'K:myp'H'btM OC'H08a'HUe.M CO,II,Y (1), eCJIH ,n;JI}I Bcp = U~=l w s , Wq n Ws = 0,
s ;/= q, cnpaBe,n;JIHBbI BKJIIO'-:IeHH}I U~=j Ws C Ek(<p), Vk E Wj, j = 1, ... , d.
Onpe,n;eJIeHHe 2.9. ,II,JI}I JII06oro MHO:tKeCTBa G C 1m BeJIH'-:IHHY EiEG Wi 6y,n;eM Ha3bl ­
BaTb 8eCOM M'HO::»ceCm8a G H 0603Ha'-:laTb V[G] :
Onpe,n;eJIeHHe 2.8.
MHO:tKeCTBO
W C 1m. I1epeHYMepyeM
W = {i 1 ,i 2 , ... ,i q }. 3,n;ecb
I1YCTb MHO:tKeCTBO
HaTypaJIbHOrO p}l,n;a
MHO:tKeCTBa
W.
ero 3JIeMeHTbI C HCnOJIb30BaHHeM '-:IHCe.,
H B ,n;aJIbHeMllieM
IWI =
q -
MOIIIHOCTb
BBe,n;eM B paCCMOTpeHHe
s
her,s) = Lri, h(r,O) =0, h(r,d) =
IWI,
r = (rl,r2, ... ,rd) ENd.
i=l
TeopeMa 2.1.
,4.1t.R m020 "tmo6'bt
'H'btM 'Hy.lt'b-cmpy'K:myp'H'btM OC'H08a'HUeM
M'HO~eCm80
B = {i 1,i2, ... ,i q } 6'bt.lto 3.1te.Me'Hm ­
Bcp(Wl, ... ,Wd), Iwsl = r s , s = 1, . . . ,d, CO,II,Y (1).
'He06XOaUMO u aocmamo"t'Ho, "tmo6'bt
{i p, i p+1, ... , i h(r,dl+1 - p} C Eip(<p)
p=
1, ... ,h(r,d) _
nHih(r ,dHl_p (<p),
(6)
[h(;,dl ]
U
{i h (r,s-l)+ll i h(r,s - 1)+2,.··, ih(r,s-l)+d C Eih(r,B-IHk (<p),
k
3,n;eCb
[a]-
IIeJIM '-:IaCTb '-:IHCJIa
TeopeMa 2.2.
8a.lta ma'K:a.R
= 1, ... , r s,
= 1, ... , d.
a E R.
,4.1t.R m020 "tmo6'bt 'Ha
7f* E P,
s
"tmo CO,II,Y
(5)
P = {7f} cY'l1l;ecm8lr
ZS;:cp[O, n, r], 'Heo6xo­
M'HO~eCm8e nepeCma'H080'K:
UMe.lta 6'bt 'Hy.lt'b-cmpy'K:mypy
aUMO U aocmamo"t'Ho, "tmo6'bt cY'l1l;ecm808a.lto 3.1teMe'Hm'HOe 'Hy.lt'b-cmpy'K:myp'Hoe OC'H08a'H,U €
B~(Wl, ... ,Wn)'
a.lt.R 'K:OmOp020
\ZS;:cp[O, n, r]\ = V [B~] .
58
Wo = 1m\B~(Wl,
... ,Wn)' a
Iwsl
= rs, s = O, ... ,n.
"
JIpU"re.M
TeopeMa 2.3. ,4/tJl, m020 'l£mo6'b£ 'Ha M'HO;)ICeCmee nepecma'Hoeo'K: P = {1[} cY'l..4ecm­
6oea/ta ma'K:aJl, nepecma'Hoe'K:a 1[* E P, 'l£mo COrDY (5) UMe/ta 6'b£ 'Hy/t'b-cmpy'K:mypy
ZS;!cp[l, n, r], 'He06xoiJuMO U aOcmamo'l£'HO, 'l£mo6'b£ cY'l..4ecmeoea/tu aea 8aaUM'HO 'Henepe­
U ?W'IO'l..4uecJl, M'HO;)ICeCmea - 9/teMe'Hm'H'b£e 'Hy/t'b-cmpy'K:myp'H'b£e OC'H08a'HUJI, B~ (WI, ... ,Wz)
H
B~(Wl+1, ... ,Wn ), a/tJl, 'K:OmOp'b£X Wo
s, S
= 0, ... ,no
= 1m \ [B~(W1, ... ,Wl) U B~(Wl+1""
= V [B~] + V [B~] .
,Wn )]
,
Iwsl =
IIpu'l£e.M IZS;!cp[l,n,rJI
tI: 0 K a 3 aTe JI b C T B 0 TeopeM
2.1- 2.3
[8J.
KOHCTPYKTllBHO
Ha llX 6a3e II rrocTpoeH
ail ropllTM BbI~eJIeHllR CTPYKTYPHbIX oco6eHHoCTeii II rrpllBe~eHllR rrpOll3BOJIbHOii CllCTeMbI K
BH~
(2)-(4).
ITo CTPYKTYPHOii MaTpllu;e A(<p) <p0pMllPyeM
Ei (<p) II BepTllKaJIbHbIe Pi (<p )CTPYKTYPHbIe MHO)KeCTBa. 3aTeM CTPOllM
} lHO)KeCTBO 0(1,0) = {i E 1m : i E Ei(<P)}. ECJIll MHO)KeCTBO 0(1,0) = 0, TO 'il1[ E P,
Izsm 7rcp [l, n, rJ I = O. 9TO 3Ha'-IllT, '-ITO HllKaKOe ll3MeHeHlle rrOpR~Ka CJIe~OBaHllR ypaBHeHllii
3. AJIrOplfTM pemeH1UI 3a,D;aq 1,2.
r o pll30HTaJIbHbIe
lIcxo~Hoii CllCTeMbI He MO)KeT 06eCrre'-IllTb BbI~eJIeHllR rpyrrrr ypaBHeHllii, llMelOru;llX CTPYK­
rypHbIe oco6eHHOCTll.
ITpe~CTaBJIReT
Kor~a 0(1,0)
llHTepec CJIY'-IaH,
=1=
0.
ITpll'IeM aJIrOpllTM peII1eHllR C<P0PMYJIllpOBaHHbIx BbIII1e 3a~a'-I COCTOllT ll3 Tpex rrOCJIe­
.lOBaTeJIbHO BbIIIOJIHReMbIX '-IacTeii.
I.
Pe3YJIbTaTOM pa60TbI rrepBoii '-IaCTll aJIrOpllTMa (pllC.
aaaa'l£u 2)
RBJIReTCR rrOCTpoeHlle
yrropR~O'-IeHHbIX
2-
MHO)KeCTB
~JIR aaaa'l£u 1, pllC.
1, 2 -
~JIR
iJl II iJ 2. tI:JIR orrpe~eJIeHHOCTll
6y~eM llMeHOBaTb llX pe'K:Opa'H'b£MU.
3 aM e'-I a H II e
S
=
1,2,
3.1.
9JIeMeHTbI JII06bIX yrropR~O'-IeHHbIX MHO)KeCTB
rrOJIY'-IeHHbIX B pe3YJIbTaTe rrepe60pa rro 6JIOK-CXeMe (pllC.
pRIOT YCJIOBlllO
(6)
TeopeMbI
2.1.
BS = {iI, i2, ... , id,
1, 2), y~OBJIeTBO­
,l.I;eiicTBllTeJIbHO, rro rrOCTpoeHlllO crrpaBe~JIllBbI CJIe~YIOru;lle
BKJIIO'-IeHllR:
{iI, ik} CEil (<p) n Hik (<p) n O(s ,O) ==
O(s,l)
= b(s,0)\{i 1 ,id,
b(s,O), . . } c E i2 (<p ) n H i k _ 1 (<p) n H("'\(s,l) -= n (s,l) , { 1,2,2k-1
A
0(s,2)
= b(s,l\ {i2' ik-d;
(8)
"
} C E it(s) ()
{2t(s),2k+1-t(s)
<p n H ik+1-t(s) ( <p ) n O(s,t(s)-l) =
O(s,t(s))
O(s,t(s))
,
= b(s,t(s)-l) \ {it(s), ik+1-t(s)},
= { 0,.
rrpll k = 2t(s), {2t(s)+d, rrpll k = 2t(s) + 1. M B CllJIY TOrO '-ITO b(s,t(s)-l) C b(s,t(s)-2) C . . . b(s,l)
{i p ,i p + 1 , ... ,ik+1-P} C Eip(<p) n Hik+1_P(<P), t(l)
,lI,OKa3bIBaeT 3TO
b(s,t(s)-l)
=
c
b(s,O), crrpaBe~JIllBbI BKJIIO'-IeHllR
/1, t(2)
=
v, p
=
1, . .. ,t(s).
LITO II
yTBep)K~eHlle.
= {ii, i 2 , ... , i d, s =
1, 2), MO)KHO rrpoBecTll pa36lleHlle Ha KJIaCCbI.
tI:JIR 3Toro rrOJIaraeM, '-ITO i1 E WI. 9JIeMeHT i2 6y~eT rrpllH~JIe)KaTb MHO)KeCTBY WI, eCJIll
i l E Ei2(<p). ECJIll)Ke i1 ~ E i2 (<P), TO WI = {it} II i2 E W2·
ITpe~rrOJIO)KllM, '-ITO {i 1,i2} C WI. Tor,ll,a eCJIll {i1,i2} C E i3 (<p), TO i3 E WI, llHa'-Ie (eCJIll
{iI, i 2} rt. Ei3 (<p)) i3 E W2.
f
3 a M e '-I a H II e
1,2,
3.2.
tI:JIR JII06oro
yrropR~O'-IeHHOrO MHO)KeCTBa B S
rrOCTpoeHHoro rro 6JIOK-CXeMe (pllC.
59
0(1,0) = {i E
Inll
fJ
i
E Ei(2')}; F(I,O) :=
:= 0; fj := 0, I-' := 0
0; Q(I,O) := 0 ,
HeT
Tn
= 0, I, .. . ,J.' -
Ii J.' := I-' -
1
HeT
Q(I,I-') : = Q(I,I-') U {.8-},
.8(1-') := .8­ = (.8i,.82);
0(1,1-'+1) := D~I.;I-') '{.8t,.82}
I-' := I-'
+ 1;
k=21-'+I;B
.
F(I,I-') := 0;
Q(I,I-')
:=
0
Puc . 1.
60
1
_ ,,(nl)
= { i l , · · · , i k },
.
_ ,,(nl)
~m+l -.:1
' 1k_m
'1-'+1 =
= 0 , 1, . . . , J.' -
t
, 'm
-
....... 2
'
1
Pel.l1eKMe ~aJlia'"'lH 1
C\.
BI : = 0· iiI : = 0 · ii 2 : =
Ko"e~ nepe60pa
liiII = 10{I .0)1; ii 2 := 0
Di~:;/{<f» =
n
Ei{<f»
Hj{<f»
n 0{2.v).
S{2.v)
= h = (i.j)
E 0{2.v) X 0{2 . v).
i ¢ j : {i.n
w~~,v) =
c
k=2v ; B 2 ={ilo . .. • i k }
i Tn + I
i . j E 0{2.v) ;
= a~Tn);
m
ik_Tn
= a~Tn);
=0,1 , . .. ,11-1
D~2 . v){<f>)}.
m a xwi : i·, i E 0(2 , 11)
HeT
V[D{2,:v)] = max V[D~2.v)];
a':. a E
S{2.v)\Q{2.v)
Q{2.v) := Q{2 . v) U {a+}
0{2 . v+I) :=
k = 2v
a{v) :=,,+ =(ai,a:i)
v := v
+ 1;
+
1; B2 = {iI, .. . , i k } ,
(Tn) .
(Tn)
1,-n+l = 0;1
, 1k_m = 0: 2
i ll +l
i·, 11\
0, 1, . .. , II - 1
D~2~v\{ai . a :i l .
=
Q{2 ,v) : = 0
Ha
KOHe~
=
@
(Jli.ll.Jl
nepe60pa (Ana
~aJlia"H 2)
3a~a"H
1)
Puc. 2.
61
,L1;onYCTllM , '-IT O Y)Ke npOll3Be,LI.eHO pa36lleHlle MHO)KeCTBa
MeHTa
iUe_1+d
BKJIIO'-IllTeJIbHO, T. e.
II YCTaHOBJIeHO, '-ITO
9JIeMeHT
BS
{i Ue _ 1+ 1' ... ,i Ue _ 1+ d} ewe, .
iU e-1 +d+ I
i Ue_1+d+1 E Wf"
ynOp5l,LI.0'-IeHHOrO
MHO)KeCTBa npllHa,LI.JIe)KllT
eCJIll CnpaBe,LI.JIllBO BKJIIO'-IeHlle
3TOMY
)Ke
KJIaccy
{iUe_1+1, ... ,iue_1+d} C Eiue_1+d+1(CP).
IIocJIe '-IerO eCTeCTBeHHbIM 06pa30M nepeXO,LI.llM K paCCMOTpeHllIO CJIe,LI.yIOlII,erO 3JIeMeHTa
i Ue _ 1+d+2 Ha
B CJIy'-Iae
3aKOH'-IeHO, II
npllHa,LI.JIe)KHOCTb MHO)KeCTBY
we,
=
p5leM Ha npllHa,LI.JIe)KHOCTb MHO)KeCTBY
11
we,.
{iUe_1+1, ... ,iue_1+d} ct. Eiue_1+d+1(CP), cPOpMllpOBaHlle KJIaCCa Wf,
{i Ue _ 1+ 1 ' ... ,iue }, Uf, = Uf, - l + d, i Ue + 1 E We,+l. IIocJIe 3TOrO npOBe­
)Ke, eCJIll
Wf,+l
3JIeMeHT
i Ue +2.
TaK ,LI.O TeX nop, nOKa He llC'-IepnaeM Bce 3JIeMeHTbI MHO)KeCTBa
,L1;JI5I npOBe,LI.eHHOrO pa36lleHll51 ynop5l,LI.0'-IeHHOrO MHO)KeCTBa
BS
BS.
WI, W2, . .. ,
Ha KJIaCCbI
... ,Wp(s) CnpaBe,LI.JIllBO npe,LI.CTaBJIeHlle BS
Uf~S{ Wi , npll'-IeM Uf~sd Wi C Eg(cp), V9 E
Wd, d = 1, ... ,pes), Wt n Wq = 0, t
q, KOTopoe 06eCne'-IllBaeT BbIIIOJIHeHlle yCJIOBll51 (7)
=
i-
TeopeMbI2.1.
A
3TO 3Ha'-IllT, '-ITO Bce nOCTpoeHHble ynop5l,LI.0'-IeHHble MHO)KeCTBa
BS
51BJI5IIOTC5I
(c yqeTOM 3aMe'-IaHll51 3.1 II YTBep)K,LI.eHll51 TeopeMbI 2.1) 3 JIeMeHTHbIMll HyJIb-CTpyKTypHbIMll
B~ (WI, W2, ... , Wp(s) ).
OCHOBaHll5lMll
II.
PYKOBO,LI.CTBY5lCb npaBllJIOM 3aMe'-IaHll5l3.2, BO BTOpOll. '-IaCTll aJIrOpllTMa npOBO,LI.ll M
nOO'-Iepe,LI.HO pa36lleHlle peKOp,LI.HbIX MHO)KeCTB Ha KJIaCCbI. CHa'-IaJIa ,LI.eJIaeM 3TO ,LI.JI5I ynop5l­
A2 _ A2
AI _ AI
B
Bcp(Wl,W2, . .. ,wz), a 3aTeM ,LI.JI5I B
Bcp(W/+l,W/+2, ... ,wn ).
=
,LI.O'-IeHHOrO MHO)KeCTBa
3
aM e '-I a H II e
3
a M e '-I a H II e
=
TaKuM 06pa30M, 6 pe3y.lt'bmame 6'bmOmte'HU.R a6YX nep6'btX "tacmeu
a.lt20pUmMa nocmpoe'H'bt a6a 63aUM'HO 'HenepeceKaw'UI;UXC.R 3.1teMe'Hm'H'btX 'Hy.lt'b-CmpyKmyp'H'btX
OC'H06a'HU.R Bl , B2 - napa, UMeW'UI;a.R MaKCUMa.lt'b'H'btU cyMMap'H'btU 6ec.
3.3.
3.4. PYKOBO,LI.CTBY5lCb YTBep)K,LI.eHll5lMll TeopeMbI 2.2 (,LI.JI5I peIIIeHll51
3aaa"tu 1) II TeopeMbI 2 .3 (,LI.JI5I p eIIIeHll51 3aaa"tu 2), ,LI.JI5I JII06011. napbI B~ (W/+I' W/+2 , ... ,wn )
II B~(Wl'W2' ... ,Wi) 3JIeMeHTHbIX HyJIb-CTpyKTypHbIX OCHOBaHllll., nOJIY'-IeHHOll. B pe3YJIbTaTe
nepe60pa nO 6JIOK-CXeMe (pllC. 1 , 2), II npOBe,LI.eHll51 pa36lleHll51 Ha KJIaCCbI MO)KHO nocTpollTb
nepecTaHoBKY 7r
E P, Ha KOTOPOll. CO,L1;Y
(5)
llMeeT HyJIb- CTpyKTypy
ZS:cp [l, n, T], lEN.
,L1;JI5I 3Toro He06xo,LI.llMO nepeHYMepoBaTb 3JIeMeHTbI KJIaCCOB
Ws
= {9o(r,s)+1, ... ,9o(r ,s)+r.},
3JIeMeHTHblX HyJIb-CTpyKTypHbIX oCHOBaHllll.
MHO)KeCTBa
Wo
= 1m \
(Bl U B2)
Ts
= IWsl ,
s
B~ (Wl,W2' ... ,wz)
r,LI.e TO = Iwol.
= {91, ... , 9 r o},
= 1, . . . , n,
II
B~(W/+I,W/+2' ... ,w n )
II
IIocJIe '-Iero llCKOMa51 nepe­
CTaHOBKa npe,LI.CTaBllMa B Bll,LI.e
7r
= (
1
91
2
92
TO
9r o
TO
+1
b(T,l
+ 1)
9o(r,/+1)
9o(r,I)+1
b(T, 1+ 1)
+1
9o(r,i+l)+1
m
9o(r,n+l)
).
IIpll'-IeM 'Hy.lt'b-CmpyKmypa Z S:cp [I , n, T], lEN, 'Ha .ltw6ou nepeCma'H06Ke 7r, nocmpoe'H'Hou
no npa6U.lty, npU6eae'H'HOMY 6'btWe, .R6.1t.RemC.R npeae.lt'b'Hou.
III. B
TpeTbell. '-IaCTll aJIrOpllTMa, PYKOBO,LI.CTBY5lCb 3aMe'-IaHlleM 3.4, Ha 6a3e peKOp,LI.HbIX
Bl, B2 CTPOllM llCKOMYIO nepeCTaHOBKY 7r* ,
3aaa"tu 2.
peIIIeHllll 3aaa"tu 1 He06xo,LI.llMO C'-IllTaTb nOCT05lHHO
3JIeMeHTHblX HyJIb-CTpyKTypHbIX OCHOBaHllll.
KOTOPa51 51BJI5IeT C5I peIIIeHlleM
3aaa"tu 1
HJIll
,L1;JI5I llCIIOJIb3 0BaHll51 aJIrOpllTMa npH
BI
= 0 II Bl = 0.
Ha'-IaTb pa60TY aJIrOpHTMa CJIe.n.yeT co BTOpOll. '-IaCTll nepe60pa (pllC .
2)
Ta6JLuv,a 1.
0
A(F) =
I
1
1
1
1
CTPYKTypHa~ MaTpHn;a Hcxo~oiiA(F) H npeo6pa30BaHHoiiA(7f* F) CHCTeM
1 0
1
0
0
0
0
1
0
0
0
0
1
0
0
1
1
1
1
0
0
1
1
1
0
0
0
1
~ II ~ ~ II ~
~ II ~ ~ II ~
1 0 0
1 0 0
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 o 0
1 0 1
1 0 1
0
0
1
1
I,
1
1-£1 v
/1-=0
2
/1-=1
3
1-£=2
4
v=o
5
6
v=l
1-£=2
7
v=o
8
v=l
W8
0")
w
=
1
0
0
Ta6JLuv,a 2.
N
A(7f* F)
I
s(p ,!-,/v)
IS(p ,!-,/V)
= {1, 2, 4,
5,6,7,8}
n(1,1) = {3,4,
. 5,6}
n(1 ,2) = {3 , 5}
SP,O) = {(1, 7), (6, 2),
26
f3(0)
= (1,7)
22
6
f3(1)
= (6,4)
15
n(2,0)
(3,2), (6,7), (3, 7), ...}
S(1,1) = ((6 4),(5,4),
J
(6,3), (5, 6), (6, 5), (4, 3)}
S(1,2) = 0
= {2, 5,8}
n(2 , 1)
S(2,0)
= 0
= {5}
'­
n ( 1,2)\p(1,2)
n(2,0)
= {2, 3, 8}
n(2 , 1)
_Y1 ::::
= {8}
{1}, W2
= {(3, 2), (3, 8),
(2,8), (8, 2)}
S(2,1) = 0
= {6,5}, W3 = {4}, W1 = {7},
f3(!-') / o(v) li *
0
0
0
0
1
0
1
1
3
0
0(0)
3
= (2,8)
4
W5
1 0
0
0
0
0
0
0
0
1
0
0
= {3},
0(0)
3
= (3,2)
{8,2},
6
Wo -
aaaa"{u 2
V[BP]
0
L:~-1
V[Bd]
0
0
0
= {1,6,
3,4,7}
B1
19
0
0
= {2,8}
= {1,6,
5,4,7}
B1
8
19
27
27
27
11
i'" = 8
W6 -
0
1 0
1 0
BP
B2
S(2,0)
0
0
8
i* = 5
0
1 1
1 0
1 0
1 0
0
0
0
0
0
1
V[D.e+/ o+]lwi+
i* = 3
0
= {(2, 8), (8,2),
(2,5)}
5(2,1) = 0
S(1,2) = 0
0
CxeMa pa60TbI aJII'OpHTMa IIpH pemeHHH
n (p,!-, /v)
n(1 ,0)
0
B2
= {3,8,2}
11
30
7r'" = (1,6,5,4,7,3,8,2).
-­
I
V
11 OrpaHl1'-:ll1TbC51 TOJIbKO nepe60pOM no BepXHeMY ,n;epeBy, T. e~ Tpe6oBaHl1e cnYCTl1TbC51 no
,n;epeBy nepe60pa Ha nOl1CK HOBorO ynop51,n;O'IeHHOrO MHO)KeCTBa Bl 03Ha'IaeT (npl1 pelIIeHl1l1
3aaa"{u 1) OKOH'IaHl1e nepe60pa C nepexo,n;OM Ha pa3611eHl1e Ha KJIaCCbI.
4. IIpHMep npHMeHeHHlI aJIrOpHTMa BbI,n;eJIeHHlI CTPYKTypHbIX oco6eHHocTe:n.
Ilpo,n;eMoHcTpl1pyeM pa60TY aJIrOpliTMa pelIIeHl151 3aaa"{u 2 Ha npl1Mepe BbI,n;eJIeHl151 HYJIb­
CTpyKTYPbI
ZS;;; F [l, n, r 1 MaKCl1MaJIbHOrO
06'beMa CO~Y:
8
I
Y = F(x,y),
(9)
y,F E R .
A(F) (Ta6JI. 1) C BeCOBbIMl1 K03¢¢1111l1eHTaMl1
= W7 = 5, W8 = 6 l1MeeT HyJIb-CTpyKTypy
(4,2,2). Ee 06'beM IZS 8 F[l,2,rll = 19.
CTPYKTYPHa51 MaTpl111a l1cxo,n;Hoif Cl1CTeMbI
WI
=
W2
=
ZS8 F [l,2,r],
2,
W3
=
r
=
W5
=
3,
=
W4
4,
IlepecTaHoBKa (nepeo603Ha'IeHl1e) 7r*
BoceMb
lIIarOB
aJIrOpl1TMa.
Ero
W6
= (~ ~ ~ : ~ ~ ~ ~)
pa60Ta CXeMaTl1'IHO
CTPYKTYPHa51 MaTpl111a npe06pa30BaHHOif Cl1CTeMbI
CTpyKTypy ZS8 F[4, 6, r],
r = (0,1,2,1,1,1,2)
npe,n;cTaBJIeHa
A(7r* F)
(CM. Ta6JI.
C 06'beMOM IZS 8 F[4,
Haif,n;eHa 3a
B Ta6JI.
1)
6, rll
2.
l1MeeT HYJIb­
=
30.
8¢­
¢eKTl1BHOCTb npl1MeHeHl151 CTPYKTypHoro no,n;xo,n;a npl1 l1HTerpl1pOBaHl1l1 l1cxo,n;Hoif Cl1C­
TeMbI onpe,n;eJI51eTC51 OTHOlIIeHl1eM
2::=ro+l W s / 2::=1 Ws
= 19/30, a npe06pa30BaHHOif ­
2:::ro+1 W 7r (s)/ 2::=1 W7r(s) = 1.
Summary
Olemskoy 1.
V. Updating of algorithm of allocation structural features.
The reduction algorithm of systems of the ordinary differential equations of a general view to the
systems of the structurally divided ordinary differential equations is written out. The found change
following the equations of the initial system provides the greatest possible effect in application of
the structural integration method.
JIHTepaTypa
1. OlteMC'IWU H. B. LIeTblpeX3TaIlHhlR MeTO,lJ, nHToro rrOpH,lJ,Ka TO<JHOCTH 'lHCJIeHHOro HHTerpH­
POBaHHH CHCTeM CnellHaJIbHOrO BH,lJ,a / / )KYPH. BbI'lHCJI. MaTeMaTHKH H MaT. <pH3HKH. 2002. T. 42,
Ng 8. C. 1179- 1190.
2. OlteMC'IWU H. B. CTPYKTYPHbIR no,lJ,xo,lJ, B 3a,lJ,a'le KOHCTPYHPOBaHHH HBHbIX O,lJ,HOiliarOBbIX
MeTO,lJ,OB / / )KYPH. BbI'lHCJI. MaTeMaTHKH. H MaT. <pH3HKH. 2003. T. 43, Ng 7. C. 961 - 974.
3. OlteMC'IWU H. B. MeTO,lJ,bI THna PYHre- KYTTbI HHTerpHpOBaHHH CHCTeM H ,lJ,li<p<pepeHllHaJIb­
HbIX ypaBHeHHR BToporo rropH,n;Ka CnellHaJIbHoro BH,n;a / / BbI'lHCJIHT. TeXHOJIOrmr. 2004. T. 9, Ng 2.
C . 67- 81.
"
'
4. OlteMC'lCOU H. B. BJIO)KeHHble MeTO,lJ,bI nHToro nOpH,lJ,Ka / / BecTH. C.-IIeTep6. YH-Ta. Cep.10:
IIpHKJIa,IJ,HaH MaTeMaTlfKa, HH<popMaTHKa, npolleccbI ynpaBJIeHHH. 2004. BbIll. 2. C. 82-93.
5. OlteMC'lCOU H. B. KOHCTPYHpOBaHHe HBHbIX MeTO,lJ,OB THIIa PYHre-KYTTa HHTerpHpOBaHHH
CHCTeM CrrellHaJIbHOrO BH,lJ,a/ / :I13B. nY30B. MaTeMaTHKa. 2005. Nv 2 (513). C. 75-80.
6. OlteMC'lCOU H. B. BJIO)KeHHbIR rrHTH3T~bIR MeTO,lJ, rrHToro nOpH,lJ,Ka THIIa ,ll;0pMaHa- IIpHHca
/ / )KYPH. BbI'lHCJI. MaTeMaTHKH H MaT. <pH3HKH. 2005. T. 45, Ng 7. C. 1181- 1191.
7. OlteMC'IWU H. B. MeTO,lJ, rrHToro rropH,lJ,Ka THna PYHre-KYTTbI HHTerpHpOBaHHH CHCTeM CTPYK­
TypHO pa3,lJ,eJIeHHbIX ,lJ,li<p<pepeHllHaJIbHbIX YPaBHeHHR / / BecTH. C.-IIeTep6. YH-Ta. Cep. 10: IIpH­
KJIa,lJ,HM MaTeMaTHKa, HH<popMaTHKa, npOlJ,eCCbI yrrpaBJIeHHH . 2005. BbIll. 1. C. 39- 48.
8. OlteMC'lCOU H. B. AJIrOPHTM BbI,lJ,eJIeHHH CTPYKTypHbIX oco6eHHocTeR / /HHKOJIaR E<pHMOBH'l
KHPHH: C6. CT. CII6: ACCII:I1H . 2003. C . 234-251.
9. OlteMC'lCOU H. B. 5iBHbIR MeTO,n; THrra PYHre-KYTTbI nHToro rrOpH,lJ,Ka / / BbI'lHCJI. TeXHOJIOrHH.
2005. T. 10, N2 2. C. 87-105.
CTaTbH I10CTYI1I1JIa B peAaKJJ;I1IO
11
AeKa6pJl
2005
r.
Документ
Категория
Без категории
Просмотров
3
Размер файла
4 239 Кб
Теги
особенности, выделением, алгоритм, модификация, структурная
1/--страниц
Пожаловаться на содержимое документа