.

Моделі, методи і алгоритми в задачах евклідової комбінаторної оптимізації: Автореф. дис… канд. фіз.-мат. наук / С.І. Недобачій, НАН України. Ін-т пр

Язык: украинский
Формат: реферат
Тип документа: Word Doc
148 2413
Скачать документ

IAOe?IIAEUeIA AEAAeAI?ss IAOE OE?A?IE

?INOEOOO I?IAEAI IAOEIIAOAeOAAIIss

?IAI? A. I. I?AeAI?IIAI

Iaaeiaa/?e Noai?neaa ?aaiiae/

OAeE
519. 85

IIAeAE?, IAOIAeE ? AEAI?EOIE A CAAeA*AO

AAEE?AeIAI? EIIA?IAOI?II? IIOEI?CAOe??

01.05.02 – iaoaiaoe/ia iiaeaethaaiiy oa ia/enethaaeuei? iaoiaee

Aaoi?aoa?ao aeena?oaoe?? ia caeiaoooy iaoeiaiai nooiaiy

eaiaeeaeaoa o?ceei-iaoaiaoe/ieo iaoe

Oa?e?a – 1999

Aeena?oaoe??th ? ?oeiien.

?iaioa aeeiiaia a Iieoaanueeiio aea?aeaaiiio oaoi?/iiio oi?aa?neoao?

?iai? TH??y Eiiae?aothea I?i?noa?noaa ina?oe Oe?a?ie

Iaoeiaee ea??aiee:

aeieoi? o?ceei-iaoaiaoe/ieo iaoe, i?ioani? ?iaoeue Ieaa Ieaen?eiae/,

Iieoaanueeee aea?aeaaiee oaoi?/iee oi?aa?neoao ?iai? TH??y
Eiiae?aothea,

caa?aeoaa/ eaoaae?e i?eeeaaeii? iaoaiaoeee oa iaoaiaoe/iiai
iiaeaethaaiiy.

Io?oe?ei? iiiiaioe:

aeieoi? o?ceei-iaoaiaoe/ieo iaoe, i?ioani? sseiaea Na?a?e
Anaaieiaeiae/,

Oa?e?anueeee aea?aeaaiee oi?aa?neoao aioo??oi?o ni?aa,

ia/aeueiee oaeoeueoaoo oi?aae?iiy oa ?ioi?iaoeee;

eaiaeeaeao o?ceei-iaoaiaoe/ieo iaoe, aeioeaio A?aaaii?e ?ai?
Aaea??eiae/,

Oa?e?anueeee aea?aeaaiee oaoi?/iee oi?aa?neoao ?aae?iaeaeo?ii?ee,

aeioeaio eaoaae?e nenoaiioaoi?ee.

I?ia?aeia onoaiiaa:

?inoeooo e?aa?iaoeee ?iai? A. I. Aeooeiaa IAI Oe?a?ie, a?aeae?e

iaoiae?a ?ica’ycoaaiiy neeaaeieo caaea/ iioei?caoe??, i?noi Ee?a.

Caoeno a?aeaoaeaoueny “ 9 ” a?oaeiy 1999 ?. i 14 aiaeei? ia
can?aeaii? niaoe?ae?ciaaii? a/aii? ?aaee Ae 64.180.01 a ?inoeooo?
i?iaeai iaoeiiaoaeoaaiiy ?iai? A.I. I?aeai?iiai IAI Oe?a?ie ca
aae?anith:

310046, i. Oa?e?a, aoe. Aei. Iiaea?nueeiai, 2/10.

C aeena?oaoe??th iiaeia iciaeiieoeny o a?ae?ioaoe? ?inoeoooo
i?iaeai iaoeiiaoaeoaaiiy ?iai? A. I. I?aeai?iiai IAI Oe?a?ie ca
aae?anith:

310046, i. Oa?e?a, aoe. Aei. Iiaea?nueeiai, 2/10.

Aaoi?aoa?ao ?ic?neaiee “_27_”_aeiaoiy_ 1999 ?.

O/aiee nae?aoa?

niaoe?ae?ciaaii? a/aii? ?aaee
A. I. Caeoeaa

CAAAEUeIA OA?AEOA?ENOEEA ?IAIOE

Aeooaeuei?noue oaie. Aaaaoi caaea/ i?iaeooaaiiy, ieaioaaiiy,
?ici?uaiiy, eeaneo?eaoe??, oi?aae?iiy caiaeeoueny aei iioei?caoe?? ia
eiia?iaoi?ieo iiiaeeiao. Na?aae iaoeiaeo i?aoeue, a yeeo noaaeyoueny oa
?ica’ycothoueny i?iaeaie, iia’ycai? c cacia/aieie caaea/aie, o
ia?oo /a?ao o?aaa iacaaoe i?aoe? A.I. ?iae?/aaa, TH. ?.
AEo?aaeueiaa, I. I. Eiaaeueiaa, A. E. Eaiioue?aa, ?. I. Eyoaiea, A. N.
Ieoaeaae/a, A. I. Ia?aiaeeoe?, ?. A. Na?a??iea, TH. A. Noiyia, A.
N. Oaia?aa, A. I. O?oa?ia, I. C. Oi?a, N. A. sseiae?aa.

Iio?aae i?aeoeee aeiaaathoue ciaoiaeaeaiiy aoaeoeaieo iaoiae?a ?
aeai?eoi?a ?ica’ycoaaiiy caaea/ iioei?caoe??, cie?aia oeo, iiaeaeyie
yeeo ? caaea/? ia eiia?iaoi?ieo iiiaeeiao, ui aeiioneathoue caio?aiiy a
aaee?ae?a a?eoiaoe/iee i?ino??. Oea a naith /a?ao ?iaeoue iaiao?aeiei
aiae?c a?aeiia?aeieo iiaeaeae ? onoaiiaeaiiy aeanoeainoae eiia?iaoi?ieo
iiiaeei oa aeanoeainoae eiia?iaoi?ieo iiiaia?aiiee?a, ye? ? ?o iioeeeie
iaieiieaie.

Ioaea, oaia aeena?oaoe?eii? ?iaioe ( “Iiaeae?, iaoiaee ? aeai?eoie a
caaea/ao aaee?aeiai? eiia?iaoi?ii? iioei?caoe??” ( ? aeooaeueiith.

Aeine?aeaeaiiy caaea/ aaee?aeiai? eiia?iaoi?ii? iioei?caoe??, a oiio
/ene? caaea/ aaiiao?e/iiai i?iaeooaaiiy, i?iaiaeyoueny, cie?aia, a
?inoeooo? i?iaeai iaoeiiaoaeoaaiiy ?iai? A. I. I?aeai?iiai IAI Oe?a?ie
i?ae ea??aieoeoaii /eaia-ei?aniiiaeaioa IAI Oe?a?ie TH. A. Noiyia, ia
eaoaae?? i?eeeaaeii? iaoaiaoeee ? iaoaiaoe/iiai iiaeaethaaiiy
Iieoaanueeiai aea?aeaaiiai oaoi?/iiai oi?aa?neoaoo ?iai? TH??y
Eiiae?aothea i?ae ea??aieoeoaii aeieoi?a o?ceei-iaoaiaoe/ieo
iaoe, i?ioani?a I. I. ?ioey, a Oa?e?anueeiio aea?aeaaiiio oaoi?/iiio
oi?aa?neoao? ?aae?iaeaeo?ii?ee, Oa?e?anueeiio aea?aeaaiiio oi?aa?neoao?
aioo??oi?o ni?aa oa ?ioeo iaoeiaeo caeeaaeao.

Aeena?oaoe?eia ?iaioa ? i?iaeiaaeaiiyi aeine?aeaeaiue a ?aieao ?icaeoeo
oai??? aaee?aeiai? eiia?iaoi?ii? iioei?caoe??, a i?e aeine?aeaeothoueny
iaeano? aecia/aiiy caaea/, iiaeaeyie yeeo ? aaee?aeia? caaea/?
iioei?caoe?? ia ia?anoaaieo iiiaeeiao, ?ic?iaeaii iiaee iaoiae oi/iiai
?ica’ycoaaiiy iaei??? c oaeeo caaea/.

Ca’ycie ?iaioe c iaoeiaeie i?ia?aiaie, ieaiaie, oaiaie. Aeena?oaoe?eia
?iaioa aeeiioaaeanue ia eaoaae?? i?eeeaaeii? iaoaiaoeee oa iaoaiaoe/iiai
iiaeaethaaiiy Iieoaanueeiai aea?aeaaiiai oaoi?/iiai oi?aa?neoaoo ?iai?
TH??y Eiiae?aothea (?ai?oa ( Iieoaanueeee oaoi?/iee oi?aa?neoao) ca?aeii
c ?iaeea?aeoaeueiei ieaiii ani??aionueei? i?aeaioiaee oa
aea?aeathaeaeaoiith oaiith “?ic?iaea oai??? iiaeaeae, iaoiae?a ?
aeai?eoi?a aaee?aeiai? eiia?iaoi?ii? iioei?caoe??” (Ae? ?
0196U006063).

Iaoa ? caaea/? aeine?aeaeaiiy. Iaoith ?iaioe ? onoaiiaeaiiy iiaeo
aeanoeainoae iaeanoae aecia/aiiy caaea/, iiaeaeyie yeeo ? caaea/?
aaee?aeiai? iioei?caoe?? ia ia?anoaaieo iiiaeeiao, ?ic?iaea iiaiai
iaoiaeo oi/iiai ?ica’ycoaaiiy caaea/? i?i?i?caoe?? caaaeaii? aeiaaeeie
ca’ycoth/i? n?oee i?e e?i?eiiio ?icoaooaaii? i?yiieooieo aeaiaio?a.

Iniiaieie caaea/aie aeine?aeaeaiiy ?:

1. Iaea?aeaiiy iaca?aeieo nenoaie e?i?eieo iaiaaeaiue iioeeeo iaieiiie
iaeanoae aecia/aiiy caaea/, iiaeaeyie yeeo ? aaee?aeia? caaea/?
iioei?caoe?? ia caaaeuei?e ia?anoaai?e oa caaaeuei?e iie?ia?anoaai?e
iiiaeeiao.

2. Iaea?aeaiiy iiaeo aeanoeainoae ia?anoaaii?, caaaeueii? ia?anoaaii?,
caaaeueii? iie?ia?anoaaii? iiiaeei oa ?o iioeeeo iaieiiie (
ia?anoaaiiai, caaaeueiiai ia?anoaaiiai oa caaaeueiiai iie?ia?anoaaiiai
iiiaia?aiiee?a.

3. Iaea?aeaiiy aeanoeainoae iaeiiai a?aeia?aaeaiiy iiiaeeie
ia?anoaaeaiue ia?oeo n iaoo?aeueieo /enae o iiiaeeio ia?anoaaeaiue ?c
iiaoi?aiiyie, aeaiaioaie yei? ? aaniethoi? aaee/eie ??cieoeue on?o ia?
ia?oeo n iaoo?aeueieo /enae, yea aeieea? a caaea/? i?i?i?caoe??
caaaeaii? aeiaaeeie ca’ycoth/i? n?oee i?e e?i?eiiio ?icoaooaaii?
i?yiieooieo aeaiaio?a; iiaoaeiaa aeai?eoio onoaiiaeaiiy i?iia?aco aai
eiai a?aenooiino? oa aecia/aiiy ca’yce?a i?ae no?oeoo?aie iioeeeo
iaieiiie iacaaieo iiiaeei i?e cacia/aiiio a?aeia?aaeaii?;

4. ?ic?iaeaiiy iiaiai iaoiaeo oi/iiai ?ica’ycoaaiiy caaea/?
i?i?i?caoe?? caaaeaii? aeiaaeeie ca’ycoth/i? n?oee i?e e?i?eiiio
?icoaooaaii? i?yiieooieo aeaiaio?a.

Iaoeiaa iiaecia iaea?aeaieo ?acoeueoao?a. Iiaeie ?acoeueoaoaie, ye?
aeeeaaeaii a aeena?oaoe?? ?:

1. Onoaiiaeaiiy iaca?aeii? nenoaie e?i?eieo iaiaaeaiue caaaeueiiai
ia?anoaaiiai iiiaia?aiieea; aecia/aiiy ??aiyiue on?o eiai a?ia?a?aiae
/a?ac iaiaaeeeoeia? iaiaaeaiiy oa ?o e?eueeino?; iien aa?oei ??aiyiiyie
a?ia?a?aiae; aecia/aiiy e?eueeino? a?ia?a?aiae, ui ca?aathoueny a iaei?e
? o?e aea aeia?euei?e aa?oei?; iiaa aeiaaaeaiiy oai?aie i?i ca?aei?noue
aa?oei c iiiaeeiith ia?anoaaeaiue ?c iiaoi?aiiyie, yeith ?iaeoeo?oueny
cacia/aiee iiiaia?aiiee.

2. Onoaiiaeaiiy iaca?aeii? nenoaia e?i?eieo iaiaaeaiue caaaeueiiai
iie?ia?anoaaiiai iiiaia?aiieea; iien eiai a?ia?a?aiae iaiaaeeeoeiaeie
iaiaaeaiiyie; aecia/aiiy caeaaeiino? i?ae e?euee?noth a?ia?a?aiae
cacia/aiiai iiiaia?aiieea ? e?euee?noth a?ia?a?aiae caaaeueieo
ia?anoaaieo iiiaia?aiiee?a, aeiaooeii yeeo a?i ?; oea ae ( noiniaii
aa?oei;

3. Aeyaeaiiy caeaaeiino? i?ae e?euee?noth a?ia?a?aiae aeiaooeo
iiiaia?aiiee?a ? e?euee?noth a?ia?a?aiae iiiaia?aiiee?a-ni?aiiiaeiee?a,
ye? ooai?ththoue oeae aeiaooie: oea ae ( noiniaii aa?oei.

4. Aecia/aiiy iaeiaioi? e?eueeino? ?aaa? (r-a?aeaeae?), c yeeo
neeaaea?oueny oeyo a?ae aeia?eueii? aa?oeie ia?anoaaiiai iiiaia?aiieea
aei aoaeue-yei? ?ioi? eiai aa?oeie oa iiaoaeiaa aeai?eoio ciaoiaeaeaiiy
oaeiai oeyoo; aeiaaaeaiiy ianoi?aeiino? aa?oei iiiaia?aiieea, ye?
ciaoiaeyoueny ia iaei?e ? o?e aea r-a?aeaeae? a?ae aoaeue-yei? eiai
o?eniaaii? aa?oeie e aecia/aiiy e?eueeino? oaeeo aa?oei.

5. Ciaoiaeaeaiiy e?eoa??th ?nioaaiiy i?iia?aco i?e iaeiiio
a?aeia?aaeaii? iiiaeeie ia?anoaaeaiue ia?oeo n iaoo?aeueieo /enae o
niaoe?aeueio iiiaeeio ia?anoaaeaiue ?c iiaoi?aiiyie, yea aeieea? i?e
aeine?aeaeaii? caaea/? i?i?i?caoe?? caaaeaii? aeiaaeeie ca’ycoth/i?
n?oee i?e e?i?eiiio ?icoaooaaii? i?yiieooieo aeaiaio?a ? aeyaeaiiy
aeanoeainoae cacia/aieo iiiaeei, iia’ycaieo c oeei a?aeia?aaeaiiyi.

6. ?ic?iaeaiiy iiaiai iaoiaeo ?ica(ycoaaiiy caaea/? i?i?i?caoe??
caaaeaii? aeiaaeeie ca(ycoth/i? n?oee i?e e?i?eiiio ?icoaooaaii?
i?yiieooieo aeaiaio?a, iiaoaeiaa aeai?eoio eiai ?aae?caoe?? ia IAII.

Oai?aoe/ia oa i?aeoe/ia cia/aiiy iaea?aeaieo ?acoeueoao?a.
Aeena?oaoe?eia ?iaioa ia? oai?aoe/iee oa?aeoa?. Iaea?aeai? ?acoeueoaoe
iiaeooue canoiniaoaooeny aeey i?iaaaeaiiy iiaeaeueoeo aeine?aeaeaiue
aaee?aeiaeo eiia?iaoi?ieo iiiaeei ? caaea/ iioei?caoe?? ia ieo.
Onoaiiaeaiiy iaca?aeieo nenoai e?i?eieo iaiaaeaiue caaaeueiiai
ia?anoaaiiai oa caaaeueiiai iie?ia?anoaaiiai iiiaia?aiiee?a iiaeia
canoiniaoaaoe aeey iaea?aeaiiy iaca?aeieo nenoai e?i?eieo iaiaaeaiue
iioeeeo iaieiiie iaeanoae aecia/aiiy caaea/? aaee?aeiai? iioei?caoe?? ia
?ioeo eiia?iaoi?ieo iiiaeeiao. Oea aea? iiaeeea?noue aeyaeyoe iaa?aeii?
ia oeae /an ?o aeanoeaino?, ye? iiaeooue aeei?enoiaoaaoeny i?e
?ica’ycoaaii? a?aeiia?aeieo caaea/. Aeeeaaeaiee iaoiae ? aeai?eoi
oi/iiai ?ica’ycoaaiiy caaea/? i?i?i?caoe?? caaaeaii? aeiaaeeie
ca’ycoth/i? n?oee i?e e?i?eiiio ?icoaooaaii? i?yiieooieo aeaiaio?a
iiaeia aeei?enoiaoaaoe i?e ?ica’ycoaaii? caaea/, ye? iathoue
a?aeiia?aeio iiaeaeue.

?acoeueoaoe ?iaioe ai?iaaaeaeai? a Iieoaanueeiio aea?aeaaiiio
oaoi?/iiio oi?aa?neoao? ?iai? TH??y Eiiae?aothea i?e aeeiiaii?
aea?aeathaeaeaoii? oaie “?ic?iaea oai??? iiaeaeae, iaoiae?a ? aeai?eoi?a
aaee?aeiai? eiia?iaoi?ii? iioei?caoe??” (Ae? ? 0196U006063) o ?icae?eao
ca?oo i?i aeeiiaiiy oeacaii? oaie.

Iniaenoee aianie caeiaoaa/a. On? ?acoeueoaoe aeena?oaoe?eii? ?iaioe,
ye? iiaeai? aei caoenoo, iaea?aeai? iniaenoi aeena?oaioii. O ?iaioao,
iaienaieo o ni?aaaoi?noa?, aeena?oaioo iaeaaeaoue: [1] ( ia?oee oa
ae?oaee ?icae?ee, a a /anoei? 2 ( ioieo 4; [2] ( oi?ioethaaiiy oai?aie
i?i iaiaaeeeoeia? iaiaaeaiiy caaaeueiiai ia?anoaaiiai iiiaia?aiieea oa
?? aeiaaaeaiiy, iien on?o eiai a?ia?a?aiae iaiaaeeeoeiaeie iaiaaeaiiyie,
aecia/aiiy e?eueeino? a?ia?a?aiae oeacaiiai iiiaia?aiieea; [6] ( oai?aia
i?i iaiaaeeeoeia? iaiaaeaiiy caaaeueiiai ia?anoaaiiai iiiaia?aiieea; [7]
( oai?aia i?i iaeiaioo e?euee?noue ?aaa? i?ae aeia?eueieie aa?oeiaie
ia?anoaaiiai iiiaia?aiieea ? ?? iane?aeee, aeai?eoi ciaoiaeaeaiiy
iaeiaioiai oeyoo i?ae aeaiia caaeaieie aa?oeiaie ia?anoaaiiai
iiiaia?aiieea;

Ai?iaaoe?y ?acoeueoao?a aeena?oaoe??. Iniiai? iieiaeaiiy ?iaioe
aeiiia?aeaeeny ? iaaiai?thaaeeny ia:

( 46-51-?e iaoeiaeo eiioa?aioe?yo i?ioani??a, aeeeaaea/?a, iaoeiaeo
i?aoe?aiee?a, ani??aio?a oa nooaeaio?a Iieoaanueeiai aea?aeaaiiai
oaoi?/iiai oi?aa?neoaoo ?iai? TH??y Eiiae?aothea (i. Iieoaaa, 1994-1999
??.);

( Anaoe?a?inuee?e iaoeia?e eiioa?aioe?? ”?ic?iaea oa canoinoaaiiy
iaoaiaoe/ieo iaoiae?a o iaoeiai-oaoi?/ieo aeine?aeaeaiiyo”, i?enay/ai?e
70-??//th a?ae ia?iaeaeaiiy i?ioani?a I. N. Eac?-i??nueeiai (i. Euea?a,
1995 ?.);

( 5-7-?e I?aeia?iaeieo iaoeiaeo eiioa?aioe?yo ?iai? aeaaeai?ea I.
E?aa/oea (i. Ee?a, 1995-1998 ??.);

( Nai?ia?ao iaoeiai? ?aaee IAI Oe?a?ie (Oa?e?anueea naeoe?y
“Iaoa-iaoe/i? iaoiaee aaiiao?e/iiai i?iaeooaaiiy”, i. Oa?e?a, ?inoeooo
i?iaeai iaoeiiaoaeoaaiiy ?i. A. I. I?aeai?iiai IAI Oe?a?ie, 1997, 1998,
1999 ??.);

( I?aeia?iaei?e iaoeia?e eiioa?aioe?? “?ic?iaea oa canoinoaaiiy
iaoaiaoe/ieo iaoiae?a o iaoeiai-oaoi?/ieo aeine?aeaeaiiyo” (i.Euea?a,
1998 ?.).

Ioae?eaoe??. Iniiai? ?acoeueoaoe aeena?oaoe?eii? ?iaioe iioae?eiaai? a
8 iaoeiaeo i?aoeyo, na?aae ieo a?ioo?a (1, noaoo? a aeo?iaeao ( 2,
noaoo? a ca??ieeao iaoeiaeo i?aoeue ( 2, iaoa??aee i?aeia?iaeieo
iaoeiaeo eiioa?aioe?e ( 2, oace i?aeia?iaeii? iaoeiai? eiioa?aioe?? ( 1.

No?oeoo?a oa ianya aeena?oaoe??. Aeena?oaoe?y iaienaia oe?a?inueeith
iiaith, neeaaea?oueny c? anooio, /ioe?ueio ?icae?e?a, aeniiaeo, nieneo
aeei?enoaieo aeaea?ae c 109 iaeiaioaaiue, 3-o aeiaeaoe?a. Onueiai (150
noi??iea. Nienie aeei?enoaieo aeaea?ae oa aeiaeaoee caeiathoue 19
noi??iie.

CI?NO ?IAIOE

O anooi? iaa?oioiaaii aeooaeuei?noue oaie, i?iaaaeaii iaeyae aeecueeeo
ca iai?yieii i?aoeue, aecia/aii iaoo e caaea/? aeine?aeaeaiiy, aeacaii
iiaecio iaea?aeaieo ?acoeueoao?a oa ?o oai?aoe/ia e i?aeoe/ia cia/aiiy.

O ia?oiio ?icae?e? c?iaeaii iaeyae iaoiae?a ?ica’ycoaaiiy caaea/
eiia?iaoi?ii? iioei?caoe??. Aeeeaaeaii iniiai? iiiyooy oai???
aaee?aeiai? eiia?iaoi?ii? iioei?caoe??, ye? aeei?enoiaothoueny a
ianooiieo ?icae?eao ?iaioe, oa a?aeii? aeanoeaino? iaeanoae aecia/aiiy
caaea/ aaee?aeiai? iioei?caoe?? ia ia?anoaaieo iiiaeeiao ? aeanoeaino?
iioeeeo iaieiiie oeeo iiiaeei. Aeacaii i?aoe?, a yeeo iaaaaeai? iniiai?
?acoeueoaoe aeine?aeaeaiue ?c cacia/aieo ieoaiue.

, aea x=( x1, …, xn ), y=( y1, …, yn ) ( oi/ee i?inoi?o Rn, dimL (
aei??i?noue i?aei?inoi?o L(Rn, convM ( iioeea iaieiiea iiiaeeie M, vertI
( iiiaeeia aa?oei iiiaia?aiieea I.

, aea ei(R1 (i(Jn, r1+…+ rn=(. Aaaaeaoeiaii, ui g1 ( … ( g(, e11 ( on?
ia??aiino? ni?eie

2, 3, …, r1 ,
(4)

i?e rn >1 ( on? ia??aiino? ni?eie

k – rn , k – rn +1 , …, k – 2,
(5)

? o?eueee aiie.

Aeeeth/eaoe c nenoaie (2) ia??aiino? ni?eie (4) ? (5), ye iaaeeeoeia?,
oa cai?ieaoe ia??aiino? ni?eie 0 oa k ??ai?noth

, (6)

iaea?aeeii iaca?aeio nenoaio e?i?eieo iaiaaeaiue iiiaia?aiieea Ik n (G):

(7)

.

Aoaeue-yea ia??ai?noue nenoaie (7), yeui ?? caienaoe o aeaeyae?
??aiino? o nenoai? c ??ai?noth (6), iieno? a?ia?a?aiue iiiaia?aiieea Ik
n (G).

sseui n = 2 ? r1 > 1 oa rn > 1, oi e?euee?noue ( (Ak – 2) a?ia?a?aiae
iiiaia?aiieea Ik n (G) aei??aith? 2k.

(j(Js , s=k+1-(r1+rn).

Aeoiaey/e c iaca?aeii? nenoaie e?i?eieo iaiaaeaiue iiiaia?aiieea
Ikn(G), ?iaeoueny iien eiai aa?oei ??aiyiiyie a?ia?a?aiae oa
aecia/a?oueny e?euee?noue a?ia?a?aiae, ui ca?aathoueny a iaei?e ? o?e
aea aeia?euei?e aa?oei?.

Iaea?aeai? ?acoeueoaoe aeathoue iiaeeea?noue aeeeanoe iiaa aeiaaaeaiiy
oai?aie, i?i ca?aei?noue aa?oei caaaeueiiai ia?anoaaiiai iiiaia?aiieea
Ikn(G) c iiiaeeiith Ekn(G).

(G, I) iathoue i?noea oae? oaa?aeaeaiiy.

>1 on?o ia??aiinoae ni?eie

), (8)

>1 ( on?o ia??aiinoae ni?eie

+1), …, (i, ki -2), (9)

oa an?o ia??aiinoae ni?eie (i, ki), (i(Js ia?aoai?th? ?? a iaca?aeio
nenoaio iaiaaeaiue.

(G, I).

), aea i(Js .

), aea i(Js.

Mi.

Aeae? aeeeaaeaii aeaye? aeanoeaino? iioeei? iaieiiee iiiaeeie En (Jn)
(ia?aia?anoaaiiai iiiaia?aiieea In (Jn).

Iaoae I(() ( /enei ?iaa?n?e o ia?anoaaeaii? ((En(Jn). Ine?eueee
vertIn(Jn) = En (Jn) , oi aeia?eueia ia?anoaaeaiiy ((En(Jn) aoaeaii
oaeiae iaceaaoe aa?oeiith iiiaia?aiieea In (Jn).

Iacaaii r-a?aeaeaeeth i?ae aeia?eueieie aa?oeiaie (1 oa (2
iiiaia?aiieea In (Jn) iaeiaioo e?euee?noue ?aaa?, ui c’?aeio? aa?oeie (1
oa (2; r-a?aeaeaeue i?ae aa?oeiaie (1 oa (2 iicia/aoeiaii r((1, (1).
A?aeaeaeue (((1, (2) ia a?aei?io a?ae r-a?aeaeae? iaceaaoeiaii
e-a?aeaeaeeth. Iathoue i?noea oae? oaa?aeaeaiiy.

= (1, 2, …, n).

Oaa?aeaeaiiy 2.4.4. Na?aae aa?oei iiiaia?aiieea In (Jn), ye?
ciaoiaeyoueny ia iaeiaeia?e r-a?aeaeae? a?ae iaei??? e o??? ae
aeia?eueii? eiai aa?oeie, noi?aeieo i?ae niaith iaia?.

Oaa?aeaeaiiy 2.4.5. E?euee?noue aa?oei iiiaia?aiieea In (Jn), ye?
ciaoiaeyoueny ia iaei?e ? o?e aea r-a?aeaeae?, ??ai?e k, aea k (
n(n-1)/2, a?ae aoaeue-yei? eiai o?eniaaii? aa?oeie, aecia/a?oueny
k-ei eiao?oe??ioii oa??ii? ooieoe?? G(z) = =(1-zn) … (1-z2)
(1-z)/( (1-z)n.

Oaa?aeaeaiiy 2.4.6. Iaoae ? oeyo, ui i?ioiaeeoue ?aa?aie iiiaia?aiieea
In (Jn) a?ae aeia?eueii? eiai aa?oeie (1 aei ?ioi? aeia?eueii? aa?oeie
(2, o yeiai eiaeia ianooiia aa?oeia ciaoiaeeoueny ia iaio?e e-a?aeaeae?
a?ae (2, ii??aiyii c iiia?aaeiueith. Oiae? oeae oeyo ia? e?euee?noue
?aaa? ??aio r((1, (2 ).

O o?aoueiio ?icae?e? aeeeaaeai? ?acoeueoaoe aeine?aeaeaiiy iaeiiai
a?aeia?aaeaiiy, yea aeieea? a iiaeae? caaea/? i?i?i?caoe?? caaaeaii?
aeiaaeeie ca’ycoth/i? n?oee i?e e?i?eiiio ?icoaooaaii? i?yiieooieo
aeaiaio?a, iiiaeeie En (Jn) o iiiaeeio Ek(n-1)(G(), aea G( ={ |i-j| :
j(Jn\Ji , i(Jn – 1 }={1n -1, 2n -2, …, (n-2)2, n-1}, k = | G( |=
n(n-1)/2.

Caaeaii a(aeia?aaeaiiy (: En(Jn)(Ek(n-1)(G(). Iaoae (=(a1, …, an) (
aeia(eueiee aeaiaio iiiaeeie En (Jn). Iicia/eii (ij = |ai – aj| (i(Jn,
(j(Jn. Aaaaeaoeiaii, ui ca aecia/aiiyi ((()=(*, aea (*=((12, …, (1n,
(23, …, (2n, …, ((n-1)n )(Ek(n-1)(G(). Iao?eoeth ((i j ) iacaaii
a(aeiia(aeiith aeaiaioo (*.

Iaoae (*(Ek(n-1)(G(). ?icaeyiaii iao?eoeth ((ij), a(aeiia(aeio aeaiaioo
(*, ye iao?eoeth noi(aeiino( ioeueoea?aoa A ?c aa?oeiaie, ye( iathoue
iiia?e k(1), k(2), …, k(n). Iaoae A0 ( ioeueoea?ao ?c aa?oeiaie,
i?iioia?iaaieie /eneaie 1, 2, …, n, o yeiai e?aoi(noue ?aa?a,
(ioeeaeaioiiai aa?oeiai i oa j, aei?(aith? (i – j( (i(Jn, (j(Jn.

Oaa?aeaeaiiy 3.1.1. Aeey oiai, uia aeaiaio (*(Ek(n-1)(G() i?e
a(aeia?a-aeaii( ( iaa i?iia?ac ((En(Jn), iaiao(aeii ( aeinoaoiuei, uia
ioeueoea?aoe A oa A0 aoee (ciii?oieie.

Oea oaa?aeaeaiiy aea? iiaeeea?noue iiaoaeoaaoe aeeeaaeaiee o
aeena?oaoe?ei?e ?iaio? aeai?eoi ciaoiaeaeaiiy i?iia?aco aai onoaiiaeaiiy
eiai a?aenooiino? i?e caaeaiiio a?aeia?aaeaii? (.

, aei?(aith? n – 2.

Aa?oeia iiiaia?aiieea Ik(n-1)(G(), yea i?e a?aeia?aaeaii? ( ia?
i?iia?ac, iacaa?oueny i?iia?aciith aa?oeiith.

Oaa?aeaeaiiy 3.2.2. A?aeiioaiiy e?eueeino? aa?oei iiiaia?aiieea
Ik(n-1)(G(), ui iaeaaeaoue aeia?euei?e a?ia?ieiuei? xi =j, aea j(Jn-1
(i(Jk, aei e?eueeino? i?iia?acieo aa?oei oe??? ae a?ia?ieiueie,
aei??aith? a?aeiioaiith e?eueeino? an?o aa?oei iiiaia?aiieea Ik(n-1)(G()
aei e?eueeino? an?o eiai i?iia?acieo aa?oei.

O /aoaa?oiio ?icae?e? aeeeaaeaii iiaee iaoiae oi/iiai ?ica’ycoaaiiy
caaea/? i?i?i?caoe?? caaaeaii? aeiaaeeie ca’ycoth/i? n?oee i?e e?i?eiiio
?icoaooaaii? i?yiieooieo aeaiaio?a oa aeai?eoi eiai ?aae?caoe?? ia IAII.

Oey caaea/a ia? iiaeaeue aaee?aeiai? caaea/? eiia?iaoi?ii?
iioei?caoe??: ciaeoe

O(x), (10)

ci j | xi – xj |, ci j =c j i, c i i=0 , ci j (R1 (i(Jn, (j(Jn.

Caieoaii iaaeae?aaiiaeuei? aeaiaioe iao?eoe? N = (ni j)n ( n o
aeaeyae? ia?anoaaeaiiy

(n 12, n 13, …, n 1 n, …, n 23, n 24, …, n 2 n, …, n( n -1) ( n
-1), n( n -1) n) (11)

aai (n1, …, n k ), aea k=n(n-1)/2, c( = nij, (=j – i + (i – 1)(2n –
i)/2, i(Jn -1, j(Jn\ Ji .

( .

E(Mm). Aaaaeaii a?aeia?aaeaiiy (c: E(M*)(Ek(n-1)(G(). Iaoae
x(m)=(x(m)1, …, x(m)n)(E(Mm) ( E(M*). sseui x(m)i (0, x(m)j (0, aea
i(j, oi iicia/eii rij =|x(m)i – x(m)j| ? iacaaii oea /enei a?aeiia?aeiei
aeaiaioo cij(C=(cij), aea cij=cji, cii=0 (i(Jn, (j(Jn,. Noeoii?noue
/enae rij ooai?th? ioeueoeiiiaeeio, yeo iicia/eii G((rij ). Aeaa?aii an?
aeaiaioe cij c oaeeie ?iaeaenaie, aeey yeeo aeeiio?oueny i?eiaeii? iaeia
c oiia: x(m)i =0 aai x(m)j = 0, ? oii?yaeeo?ii ?o ca ianiaaeaiiyi:

, (12)

aea s =(n(n-1)-m(m-1))/2. Aeaiaioe ioeueoeiiiaeeie G(\ G(( rij )
oii?yaeeo?ii ca iac?inoaiiyi, caienaaoe ?o o aeaeyae? iine?aeiaiino?

r1 ( … ( rs . (13)

. Ca oiiae m=n ia?ii: {(c(x(n))} = =V(().

(. sseui m=n, oi F(x(n)) =O(x). Aeey iine?aeiaiino? ia?anoaaeaiue
x(2)(E(M2), …, x(n)(E(Mn), o yei? ia?anoaaeaiiy x(i+1) iaea?aeaii c
ia?anoaaeaiiy x(i) (i(Jn-1\{1} cai?iith a iueiio iaeiiai ?c ioe?a
(i+1)-i aeaiaioii ianeao M, aeeiio?oueny ni?aa?aeiioaiiy F(x(2))(…
(F(x(n)).

Ia?anoaaeaiiy, ye? aoaeaii ?icaeyaeaoe, caienoaaoeiaii o oaaeeoeth TP,
a ia/eneai? ia ieo cia/aiiy ooieoe?? F(x(m)) ( o oaaeeoeth TF. Eiaeiiio
ia?anoaaeaiith x(m)(E(Mm) (m(Jn\{1} i?e oi?ioaaii? oaaeeoe? TP
iaaea?oueny a?aeiia?aeiee iiia? NP.

(Rc(x(m)(NP))) ? caieoaii eiai a ianea TF. Na?aae on?o caienaieo o
ianea TF cia/aiue F(x(m)(NP)) aeaa?aii iaeiaioa. sseui oaeeo cia/aiue
aeae?eueea, oi aeaa?aii aeia?eueia c ieo. Ca eiai iiia?ii NP onoaiiaeii
a?aeiia?aeia eiio ia?anoaaeaiiy x(m)(NP). Oaea ia?anoaaeaiiy
iaceaaoeiaii aeo?aeiei ia?anoaaeaiiyi iiiaeeie E(Mm).

Iieoaii aeai?eoi ciaoiaeaeaiiy oi/iiai ?ica’yceo caaea/? (10).

Iaoae caaeaii /enei n, iao?eoey N=(nij)n ( n, aea nij=nji, nii=0 (i(Jn,
(j(Jn, ? ia?anoaaeaiiy x(E(Mn)=En(Jn) ?c iaeiaioei na?aae a?aeiieo aei
ii/aoeo ?ica’ycoaaiiy caaea/? cia/aiiyi oe?eueiai? ooieoe?? FC*=O(x).

(Rc(x(2)). Ii??aith?ii oe? cia/aiiy c FC*. O? c ieo, ye? iaio? a?ae
FC*, caieno?ii a oaaeeoeth TF, a a?aeiia?aei? ?i ia?anoaaeaiiy ( a
oaaeeoeth TP. sseui e?euee?noue caienaieo ia?anoaaeaiue iiiaeeie E(M2)
aei??aith? ioeth, oi ia?ii ?ica’ycie: x* = x, O(x*) = FC*. sseui ae
e?euee?noue caienaieo ia?anoaaeaiue iiiaeeie E(M2) ia aei??aith? ioeth,
oi ia?aoiaeeii aei ianooiiiai aoaio.

Aeae?a?ii na?aae cia/aiue F(x(2)) iaeiaioa ? ca eiai iiia?ii ciaoiaeeii
a?aeiia?aeia ia?anoaaeaiiy (=x(2), yea ? aeo?aeiei aeey iiiaeeie E(M2).
Ca ia?anoaaeaiiyi ( oa ianeaii M oi?io?ii ia?anoaaeaiiy iiiaeeie E(M3),
cai?ithth/e a ia?anoaaeaii? ( ioe? o?ao?i aeaiaioii ianeao M. Aeey
eiaeiiai ?c noi?iiaaieo ia?anoaaeaiue x(3) ia/eneth?ii F(x(3)) ?
ii??aith?ii eiai c FC*. O? ia?anoaaeaiiy, a yeeo cia/aiiy ooieoe?? F
iaio? a?ae FC*, caieno?ii a oaaeeoeth TP, a a?aeiia?aei? ?i cia/aiiy
ooieoe?? ( a oaaeeoeth TF. sseui e?euee?noue c?iaeaieo ia oeueiio e?ioe?
caien?a aei??aith? ioeth, oi ?c ia?anoaaeaiue iiiaeeie E(M2) aeeeth/a?ii
aeo?aeia ia?anoaaeaiiy ?: a) yeui e?euee?noue ia?anoaaeaiue iiiaeeie
E(M2) i?ney aeeiiaiiai aeeeth/aiiy noaea ??aiith ioeth, oi iieeaaea?ii
x* = x, O(x*) = FC*; a) yeui oey e?euee?noue a?aei?iia a?ae ioey, oi a
iiiaeei? E(M2) aecia/a?ii iiaa aeo?aeia ia?anoaaeaiiy ( ? ca iei
oi?io?ii ia?anoaaeaiiy iiiaeeie E(M3).

sseui e?euee?noue caienaieo o oaaeeoeth TP ia?anoaaeaiue iiiaeeie E(M3)
a?eueoa a?ae ioey, oi na?aae oeeo ia?anoaaeaiue aecia/a?ii aeo?aeia
ia?anoaaeaiiy ( ? oi?io?ii ia?anoaaeaiiy iiiaeeie E(M4), cai?ithth/e a
ia?anoaaeaii? ( ioe? /aoaa?oei aeaiaioii iiiaeeie M.

I?iaeiaaeoth/e oi?ioaaoe oaeei /eiii ca aeo?aeiei ia?anoaaeaiiyi
iiiaeeie E(Ms), aea 2( s

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Ответить

Курсовые, Дипломы, Рефераты на заказ в кратчайшие сроки
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020