IAOe?IIAEUeIEE OAOI?*IEE OI?AA?NEOAO OE?A?IE

“EE?ANUeEEE IIE?OAOI?*IEE ?INOEOOO”

E?AAI

NAAAeA IOOAIIAAe AE?I

OAeE 681.324

IAOIAe OA CANIAE NOAOE*IIAI IEAIOAAIIss CAAeA*

O IA?AEAEUeIEO IA*ENETHAAEUeIEO NENOAIAO

Niaoe?aeuei?noue 05.13.13 — Ia/enethaaeuei? iaoeie, nenoaie oa ia?aae?.

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

eaiaeeaeaoa oaoi?/ieo iaoe

Ee?a — 1998

Aeena?oaoe?y ? ?oeiien

?iaioa aeeiiaia o Iaoe?iiaeueiiio Oaoi?/iiio Oi?aa?neoao? Oe?a?ie

“Ee?anueeee Iie?oaoi?/iee ?inoeooo”

ia eaoaae?? ia/enethaaeueii? oaoi?ee

Iaoeiaee ea??aiee —aeieoi? oaoi?/ieo iaoe, i?ioani? eaoaae?e

ia/enethaaeueii? oaoi?ee Iaoe?iiaeueiiai Oaoi?/iiai Oi?aa?neoaoo Oe?a?ie
Neiiiaiei Aaea??e Iaaeiae/.

Io?oe?ei? iiiiaioe:

Aeieoi? oaoi?/ieo iaoe, i?ioani? Ia/o?ei Ieeieae Eai?oiiiae/, canooiiee
ia/aeuei?ea aieiaiiai oi?aae?iiy I?i?noa?noaa ina?oe Oe?a?ie.

Eaiaeeaeao oaoi?/ie/ iaoe, aeioeaio Ua?aeia Ieaenaiae? Aiae??eiae/,
aeioeaio Ee?anueeiai aea?aeaaiiai Oi?aa?neoaoo a?oeoaeoo?e oa
aoae?aieoeoaa.

I?ia?aeia onoaiiaa:

?inoeooo i?iaeai ?aaeno?aoe?? ?ioi?iaoe??.

A?aeae?e — i?iaeaiii — i??aioiaaieo ?ioi?iaoe?eii-ia/enethaaeueieo
nenoai

Caoeno a?aeaoaeaoueny 28.12.1998 ?. a 14.30 aiaeei ia can?aeaii?
niaoe?ae?ciaaii? ?aaee Ae26.002.02 o Iaoe?iiaeueiiio Oaoi?/iiio
Oi?aa?neoao? Oe?a?ie “Ee?anueeee Iie?oaoi?/iee ?inoeooo”

(i. Ee?a, i?. Ia?aiiae 37, ei?i. 18, aoae. 306)

A?aeaoee ia aaoi?aoa?ao o aeaio i?ei??ieeao, caa??ai? ia/aoeith
onoaiiae,

i?ineii iai?aaeoe ca aae?anith: 252056, i. Ee?a, i?. Ia?aiiae 37,

a/aiiio nae?aoa?th IOOO “EI?”.

C aeena?oaoe??th iiaeia iciaeiieoeny o a?ae?ioaoe?

Iaoe?iiaeueiiai Oaoi?/iiai Oi?aa?neoaoo Oe?a?ie “EI?”

Aaoi?aoa?ao ?ic?neaiee ____________1998 ?.

A/aiee nae?aoa?

niaoe?ae?ciaaii? a/aii? ?aaee I.I.I?eiaa

AIIOAOe?ss

Iaoith aeena?oaoe?eii? ?iaioe ? ?ic?iaea oa aeine?aeaeaiiy iaoiae?a e
cania?a aoaeoeaiiai ?iciiae?eaiiy ia/enethaaeueieo ?ia?o oa ?oiuei?
iioei?caoe??, aeicaieyth/eo ciaiueoeoe /aniao neeaaei?noue noaoe/iiai
ieaioaaiiy caaea/ o ia?aeaeueieo ia/enethaaeueieo nenoaiao.

Aeey aeinyaiaiiy iieeaaeaii? iaoe o aeena?oaoe?? ae??oothoueny ianooii?
ieoaiiy:

Aiae?c a?o?oaeoo?ieo iniaeeainoae ia?aeaeueieo ia/enethaaeueieo nenoai
(IIN), aeae?eaiiy oa eeaneo?eaoe?y ocaaaeueiaieo a?o?oaeoo?ieo
oa?aeoa?enoee, aecia/ath/eo i?eioeeie oi?aae?iiy e i?aai?caoe??
ia/enethaaeueieie i?ioeanaie a IIN.

Ii??aithth/ee aiae?c oa eeaneo?eaoe?y iaoiae?a oa aeai?eoi?a noaoe/iiai
ieaioaaiiy ?ia?o o ia?aeaeueieo ia/enethaaeueieo nenoaiao e aeae?eaiiy
iniaeeainoae oa aeiia aei nenoaie noaoe/iiai ieaioaaiiy.

Oai?aoe/ia iaa?oiooaaiiy e ?ic?iaea iaoiaeo no?oeoo?ii ( naiaioe/iiai
aiae?co ii/aoeiai? ?ioi?iaoe?? c iaoith i?aeaeuaiiy aoaeoeaiino?
ieaioaaiiy ?ia?o a N?IAe.

Oai?aoe/ia iaa?oiooaaiiy e ?ic?iaea aeai?eoi?a noaoe/iiai ieaioaaiiy oa
?iciiae?eaiiy ?ia?o a IIN.

Ia caoeno aeianaia ianooiia.

Caaaeueia eeaneo?eaoe?y ia?aeaeueieo nenoai ia?iaee aeaieo, o?aoiaoth/a
iniaeeaino? a?o?oaeoo?e no/anieo ia?aeaeueieo ia/enethaaeueieo nenoai oa
i?aai?caoe?? ia/enethaaeueieo i?ioean?a a IIN.

Iaoaiaoe/ia iinoaaeaiiy caaea/? ?iciiae?eaiiy e iioei?caoe?? i?ioean?a
i?e noaoe/iii ieaioaaii? ?ia?o a IIN.

Oaa?aeaeaiiy, iieeaaeai? aei iniiae aaeaioeaiiai aeai?eoio ?iciiae?eaiiy
caaea/ o ia?aeaeueiiio ia/?nethaaeueiiio ioi/aii?.

Aaeaioeaiee aeai?eoi ni?yiiaaiiai iiooea ??oaiiy caaea/? ?iciiae?eaiiy
?ia?o oa iioei?caoe?? i?inoi?iai — /aniaeo oa?aeoa?enoee ?iceeaaeo i?e
noaoe/iii ieaioaaii? a IIN.

Neaioth/ee aeai?eoi i?inoi?iai ( /aniaiai ?iciiae?eaiiy ?ia?o a IIN c
o?aooaaiiyi aea?aieo iaiaaeaiue aei nenoaie ieaioaaiiy ?ia?o.

Aeai?eoi no?oeoo?ii ( naiaioe/iiai aiae?co ii/aoeiai? ?ioi?iaoe?? oa
ae?iaee no?aoaa?? aaeainiai? iioei?caoe?? i?inoi?iai — /aniaiai
a?aeia?aaeaiiy iia’ycaiiai a?aoa caaea/ a IIN ia iniia? ?ic?iaeaieo
i?ioeaaeo? aa?oeeaeueii — ai?eciioaeueii? eeanoa??caoe?? e aeae?eaiiy
aa?oei, iath/eo iciaee «yaii?», «i?eoiaaii?» oa «ioeueoeieeeaoeaii?
o?aiceoiino?».

?acoeueoaoe noaoenoe/iiai aeine?aeaeaiiy ?ic?iaeaieo iaoiaeia
aeeiai?/iiai ieaioaaiiy i?ioean?a a N?IAe oa ii??aiyiiy ?o c a?aeiieie.

CAAAEUeIA OA?AEOA?ENOEEA ?IAIOE

Aeooaeuei?noue oaie.

C?inoaiiy i?iaeoeoeaiino? IN ? iianye/aniei ia’?eoii aeine?aeaeaiue ia
i?ioyc? onueiai ia??iaeo ?icaeoeo cania?a IO.

Ia??ai? c i?aeaeuoaaiiyi i?iaeoeoeaiino? i?ioeani??a ?ioaineaii
i?iaiaeyoueny ?iaioe ii oaeineiiaeaiith ia?aeaeueieo nenoai ia?iaee
aeaieo, aeey yeeo ieoaiiy i?aai?caoe?? ieaioaaiiy e ia/enethaaiiy ua
a?eueo oneeaaeiththoueny. O?aaa a?aei?oeoe, ui oaoi?/ia ?aae?caoe?y
aenieiia?aeaeueieo IN aeia?aaeaea? ?ic?iaeo nenoaiiiai i?ia?aiiiai
caaacia/aiiy, ae??uoth/eo caaea/? iioeiaeueiiai ?ici?uaiiy ia?aeaeueieo
i?ia?ai o ia/enethaaeueia ioi/aiiy.

A?aeiii aaaaoi ?ia?o a aaeoc? oai??? ?icia?aeaethaaiiy ia/enethaaiue oa
?aae?caoe?? i?aeoe/ii ae?th/eo nenoai ?icia?aeaethaaiiy aeai?eoi?a ?
i?ia?ai, ia?aaeaa/ath/eo iiaeeeaino? aueiiaiiy iiia?aaeaeoaaeueii?
i?aeaioiaee ?ia?o a aaaaoii?ia?aiiiio ?aaeei? ?iaioe nenoaie. Aea
aeine?aeaeaiiy a aaeoc? oai??? iiaoaeoaaiiy nenoai ieaioaaiiy ?ia?o a
IIN ua ia aeaee aeinoaoiuei aoaeoeaieo i?aeoe/ieo aeai?eoi?a ? i?ia?ai
aeey IIN, oiaoi oaeeo, ye? a aeicaieeee c iacia/ieie iaeeaaeieie
aeo?aoaie aeei?enoiaoaaoe ?o aeey noai?aiiy ?IN Aiae?c ?acaeoeo IN a
inoaii? ?iee iieaco?, ui noai?aiiy oa aeei?enoaiiy noaiaea?o?a aeey
aenieioaeaee?niiai ca’yceo, oaeeo ye FDDI, HiPP, SONET, aeicaiey?
aoaeoaaoe aeiaaeuei? IN, c’?aeioth/? ??ciiiai?oi? oaeaeeiae?th/?
a?aeaeaeai? ia/enethaaeuei? iaoeie aeey nieeueii?, aoaeoeaii? oa
aeiiiiii? ia?aaee ??cieo caaea/.

??oaiiy naii? caaea/e ieaioaaiiy oa ?iciiae?eaiiy ?ia?o c o?aooaaiiyi
on?o aeiia aei nenoaie ieaioaaiiy, e ia?aiao??a IN ?/aai aoiaeiiai
iioieo caaaeaiue ? e?eoe/ii neeaaeiith. Aiia yaey? niaith noeoii?noue
aeae?eueea neeaaeii ae??ooaaieo caaea/, iaeaaea/eo aei eeano NP-iiaieo.

Oaeei /eiii, aeine?aeaeaiiy e ?ic?iaea iaoiae?a ? cania?a i?aai?caoe??
ia/enethaaeueieo i?ioeanea a iai?aeaeueieo nenoaiao ia?iaee aeaieo ? ?o
iiaeaethaaiiy, i?aeoe/ia ?aae?caoe?y ? ai?iaaoe?y ? aeooaeueieie,
iathoue oai?aoe/io cia/ei?noue e i?aeoe/iee ?ioa?an.

Ia’?eoaie aeine?aeaeaiue ? iaoaiaoe/i? iiaeae? aeai?eoi?a noaoe/iiai
ieaioaaiiy, i???ioiaai? ia aeei?enoaiiy aaeaioeaieo iaoiae?a
iai?aaeaiiai iiooeo ??oaiue a ia?aeaeuei?o IN.

Iaoiaee aeine?aeaeaiue a?oioothoueny ia aeei?enoaii?: oai??? a?ao?a,
oai??? iiiaeei, oai??? iiaeaethaaiiy, iaoiae?a eiia?iaoi?ii?
iioei?caoe??, a oaeiae oaa?aeaeaiue, ye? aeiaaaeai? a aeena?oaoe??.
Caaaeuei? iieiaeaiiy e oai?aoe/i? ioe?iee i?aeoaa?aeaeai? ?acoeueoaoaie
?i?oaoe?eiiai iiaeaethaaiiy ia YII.

Iaoeiaa iiaecia. Cai?iiiiiaaii iiaee i?aeo?ae aei ??oaiiy caaea/
noaoe/iiai ieaioaaiiy a ia?aeaeuei?e ia/enethaaeuei?e nenoai? ia?iaee
aeaieo, nooue yeiai o iiia?aaeiueiio no?oeoo?iiio aiae?c? ii/aoeiai?
?ioi?iaoe?? ? a?cia/aii? aoaeoeaii? aaeaioeaii? no?aoaa?? ??oaiiy
caaea/? noaoe/iiai ieaioaaiiy, aa?aiooth/i? io?eiaiiy iioei?c??iaaiiai
??oaiiy ii e?eoa??yi iioei?caoe?? i?e cia/iiio ciaiueoaii? /ano
ieaioaaiiy. I?e oeueiio io?eiai? ianooii? ?acoeueoaoe:

?ic?iaeaia caaaeueia iiaeaeue noaoe/iiai ieaioaaiiy aeey nenoai
ia?aeaeueii? ia?iaee aeaieo, aeicaieeaoa ?iciiae?eeoe ?? ia i?aecaaea/?
e cae?enieoe ?o iaoaiaoe/io iinoaiiaeo.

Noi?ioeueiaai? oaa?aeaeaiiy e ne?aenoaa, aeiaiaey/? ei?aeoi?noue e
aenieo aoaeoeai?noue ?ic?iaeaieo iaoiae?a e cania?a ieaioaaiiy.

?ic?iaeai? aeai?eoie iai?aaeaiiai iiooeo aa??aioo ?iceeaaeo aeeiiaiiy
?ia?o a IIN, ye? a?oioothoueny ia no?aoaa?? iioaaiaiai eiino?othaaiiy
?iceeaaeo aeey caaea/? noaoe/iiai ieaioaaiiy e iioei?caoe??
?iciiae?eaiiy ?ia?o a IIN.

I?aeoe/ia oe?ii?noue ?acoeueoao?a aeena?oaoe?eii? ?iaioe ? a oiio, ui
aeei?enoaiiy cai?iiiiiaaiiai iaoiaeo ? cania?a aeicaiey? i?aeaeueoe
aoaeoeai?noue ieaioaaiiy a IIN.

E??i oiai, iia? aeai?eoie e i?ia?aie aaeaioeaieo ieaioaaeueiee?a
i?ecia/ai? aeey ??oaiiy oe?ieiai eeano caaea/ noaoe/iiai ieaioaaiiy
?ia?o a IIN c o?aooaaiiyi ye iniaeeainoae ?icia?aeaeaieo aeai?eoi?a
??oaiiy i?eeeaaeieo caaea/, oae e iniaeeainoae oiiieia?? ? oa?aeoa?enoee
ia/enethaaeueiiai ioi/aiiy iai ia?aae?. Iia? aeai?eoie oa i?ia?aie
a?ae??ciythoueny a?ae a?aeiieo /eiaei iaiueoith /aniaith neeaaei?noth.

O aeena?oaoe?eio ?iaioo aeeth/ai? ?acoeueoaoe, io??iai? aaoi?ii c 1995
ii 1997 ??. Ia eaoaae?? ia/enethaaeueii? oaoi?e? Ee?anueeiai
iie?oaoi?/iiai ?inoeoooo i?e aeeiiaii? aeiaiai?o i?i iaoeiaa -oaci?/ia
ni?a?ia?oieoeoai c iie?oaoi?/iei ?inoeoooii i. *ainoioiai (?anioae?ea
Iieueoa).

Iaoiaeieia?/i? oa iaoeia? aniaeoe aeena?oaoe?eieo aeine?aeaeaiue iaeoee
naith ?aae?caoe?th a o/aiai-iaoiaee/iiio caaacia/aii? eaeoe?eieo eo?n?a,
i?iaaaeaii? eaai?aoi?ieo ? ea??aieoeoa? eo?niaeie ?iaioaie ii eoinai
«I?aai?caoe?y ia/?nethaaeueieo i?ioeann?a a AII, eiiieaenao, ia?aaeao oa
nenoaiao» ? «Iia?aoe?ei? nenoaie» nooaeaio?a oaeoeueoaoo ?ioi?iaoeee oa
ia/enethaaeueii? oaoieee Iaoe?iiaeueiiai oaoi?/iiai oi?aa?n?oaoo Oe?a?ie
(«EI?»)

A??ia?aei?noue oai?ai, oaa?aeaeaiue ? aeniiae?a i?aeoaa?aeaeo?oueny
oi/ieie oai?aoe/ieie aeiaaaeaiiyie e ?acoeueoaoaie noaoe/iiai
iiaeaethaaiiy.

Ai?iaaoe?y ?iaioe. Caaaeuei? iaoeia? ?acoeueoaoe aeena?oaoe?eii? ?iaioe
aoee iiaeai? e iaaiai?thaaeeny ia XXIV i?aeia?iaei?e eiioa?aioe?? ? a
aeeneon?eiiio iaoeiaiio eeoa? ”Iia? ?ioi?iaoe?ei? oaoiieia?? a iaooe?,
ina?o? e a?cian?: New Information Tecnology in Science, Education and
Business, IT+SE`97” (Oe?a?ia, E?ei, sseoa-Ao?coo, 15-24 o?aaiy 1997
?ieo), ia iaoeiaeo nai?ia?ao a IOOO(EI?).

Ioae?eaoe??. Ii iaoa??aeai aeena?oaoe?? iioae?eiaaii 4-e iaoeiaeo
?iaioe.

No?oeoo?a ? ia’?i ?iaioe. Aeena?oaoe?eia ?iaioa neeaaea?oueny c
anooio, /aoe?ao aeaa ? aeniiaeo, aeeeaaeaieo ia 148 noi??ieao
iaoeiiieniiai oaenoo, ia? 97 iaethie?a ? oaaeeoeue ia 10 noi??ieao,
nienie e?oa?aoo?e c 140 iaeiaioaaiue oa aeaa aeiaeaoee.

O anooi? iaa?oioiao?oueny aeooaeuei?noue oaie aeena?oaoe?eii? ?iaioe,
oi?ioeth?oueny iaoa ? caaea/? aeine?aeaeaiiy, caaaeuei? iieiaeaiiy, ye?
i?iiiiothoueny aei caoenoo.

O ia?oiio ?icae?e? ?icaeyaeai? ieoaiiy i?aai?caoe?? ia/enethaaiue a
ia?aeaeueieo ia/enethaaeueieo nenoaiao, aeine?aeaeaii aieea a?o?oaeoo?e
ia/enethaaeueieo nenoai ia?aeaeueii? ia?iaee ?ioi?iaoe?? (IIN) ia
i?aai?caoe?th ? oi?aae?iiy ia/enethaaiiyie.

O ae?oaiio ?icae?e? cae?eniaii aiae?c i?eioeei?a iiaoaeiae ia?aeaeueieo
iia?aoe?eieo nenoai aeey IIN, iaoiae?a, no?oeoo? oa aeai?eoi?a
noaoe/iiai ieaioaaiiy ? aeeniao/a??caoe??, aecia/ai? aeiiae ? e?eoa???
iioei?caoe?? ??oaiiy caaea/ ieaioaaiiy oa ?iciiae?eaiiy, aecia/aia
caaaeueia iiaeaeue nenoaie noaoe/iiai ieaioaaiiy.

O o?aoueiio ?icae?e? iiaeaii iaa?oiooaaiiy iaoiaeo no?oeoo?ii —
naiaioe/iiai aiae?co ii/aoeiai? ?ioi?iaoe??, i?eaaaeai? oaa?aeaeaiiy,
iieeaaeai? a iniiao i?ioeaaeo? eieae?caoe?? ciie iiooeo ? aeai?eoio
neaioth/iai i?inoi?iai — /aniaiai ?iciiae?eaiiy aca?iica’ycaieo ?ia?o ii
?ano?nai i?e ae??oaii? caaea/ noaoe/iiai ieaioaaiiy aeey nenoai c?
ni?eueiith iai’yoth ? ?iciiae?eaieo nenoai. ?icaeyaeaii aa?enoe/iee
aeai?eoi iioei?coth/iai iaeoaaiiy ?ia?o i?e ae??oaii? caaea/?
ai?eciioaeueii? eeanoa?ecaoe??. ?icaeyaeaii aeai?eoi noaoe/iiai
ieaioaaiiy c o?aooaaiiyi eiioi?eaoe?eieo aeo?ao.

O /aoaa?oiio ?icae?e? iiaeaii iaa?oiooaaiiy ia?aii? nenoaie
iiaeaethaaiiy, aecia/ai? e?eoa??? ii??aiyiiy oa i?eaaaeai? ?acoeueoaoe
noaoenoe/iiai ii??aiyeueiiai aiae?co ?ac?iaeaieo aeai?eoi?a ? i?ia?ai c
iaea?eueo a?aeiieie, /ei i?aeoaa?aeaeothoueny ?acoeueoaoe oai?aoe/ieo
aeine?aeaeaiue.

O aeniiaeo i?eaaaeai? caaaeuei? oai?aoe/i? oa i?aeoe/i? ?acoeueoaoe
?iaioe, ?aeiiaiaeaoe?? ii ?o aeei?enoaiith.

INIIAIEE CI?NO ?IAIOE

Nenoaia ia?aeaeueii? ia?iaee aeaieo (NIIAe) — oea noeoii?noue oaoi?/ieo
cania?a (OC) ? i?ia?aiiiai caaacia/aiiy (IC), i?ecia/aia aeey
?ioi?iaoe?eiiai ia?aeaeueiiai ianeoaiaoaaiiy ei?enooaa/?a oa oaoi?/ieo
ia’?eo?a. ?niothoue ??ci? i?aeoiaee aei eeaneo?eaoe?? NIIAe aai
ia?aeaeueieo ia/?nethaaeueieo nenoai (IIN).

A IIN (aaaaoii?ioeani?ieo, aaaaoiiaoeieo eiiieaenao, ia?aaeao) caaea/a
ieaioaaiiy aeey ?iciiae?eaiiy cayaie (caaaeaiue, i?ioean?a…) ia
i?aeoiaeeo ?ano?nao nenoaie ? iaei??th c iaea?eueo neeaaeiiae??ooaaieo a
i?aai?caoe?? ia/enethaaeueieo i?ioean?a ? oai??? ?iceeaae?a.
Ia/enethaaeueio nenoaio oa ia/enethaaeueiee aocie IIN a caaaeueiiio
aeaeyae? iiaeeeai ?icaeyaeaoe c ??ciei nooiaiai aeaoae?caoe?? ye
noeoii?noue ?ano?n?a, a ia’?eoe ieaioaaiiy ia/enethaaiue aai “caaaeaiue”
ia ?ano?ne iiaeooue aooe iiaeai? ye i?ia?aie, i?ioeaaeo?e, ia?aeaeuei?
/anoee i?ia?ai, ie?ai? aeiee eiiaiae, eiiaiaee ? ie?ai? iae?i aai
i?e?iiia?aoe??.

?iciiae?eaiiy caaaeaiue (?ia?o, i?ioean?a) ia ?ano?ne a nenoaiao
ianiaiai ?icia?aeaethaaiiy (IIN-iaeii??aeieo nenoaiao) aai o
?iciiae?eaieo nenoaiao (?N-iaiaeii??aeieo nenoaiao) ia? oaeo caaaeueio
iinoaiiao [1,2]:

Nenoaia ?ano?n?a caaeaia a?aoii nenoaie GR=(VR,ER,WVR,WER), aea:

VR= {R1,R2, …,RN}- iiiaeeia aa?oei, eaaeiee aeaiaio yeiai iiaea? iaeei
c N ?ano?n?a nenoaie ? Ri((( , i=1..N.

ER={E1,E2,…,Ed}- iiiaeeia aeoa iienoth/eo ca’ycee iaeiiai ?ano?no c
?ioei Ei={Ri,Rj}, aea Ri,Rj(VR e 0 ( d ( N2.

WVR={WVR1,WVR2,…,WVRN}- iiiaeeia aaa aa?oei, aea WVRi={REi,RTi}. Aeey
(i=1..N, REi((+ — oa?aeoa?enoeea ?ano?no Ri, RTi({0 e (+} — noai
?ano?n?a.

WER={WER1,WER2,…,WERp }- iiiaeeia aaa aeoa. Oeth iiiaeeio iiaeia
iiaeaoe o aeaeyae? aeayei? iao?eoe? RC=RC[i,j]((+, aea i=1..N e j=1..N.

JPi((+ — i??i?eoao aeaiiai caaaeaiiy.

A i?aoeyo, i?enay/aieo ??oaiith caaea/ noaoe/iiai ieaioaaiiy
a?aei?/a?oueny, ui aiie ? neeaaeiiae??oaeueieie ? iaeaaeaoue eeano
NP-iiaieo. I?aoe?, i?enay/ai? ??oaiith oeeo caaea/ [2, 4, 5,], iiaeeeai
?acae?eeoe ia ianooii? eaoaai???:

??oaiiy caaea/? ieaioaaiiy;

??oaiiy caaea/? ?iciiae?eaiiy.

O iaaeao caaea/ ia?oi? eaoaai??? aeeiio?oueny ??oaiiy eeane/ii? caaea/?
ieaioaaiiy i?ae iacaith “ Aaaaoii?ioeani?iee ?iceeaae”. Iaeaaeeoue
a?aecia/eoe, ui i?e i?i?i?caoe?? /enea i?ioeani??a ?/aai /ano ??oaiiy,
ye i?aaeei, ia aecia/a?oueny a yeee naia ia/enethaaeueiee aocie aoaea
?ici?uaia eiaeia i?aecaaea/a aai caaea/a. Oea aecia/a?oueny o iaaeao
caaea/ ae?oai? eaoaai???. Ia’?aeiaiiy oeeo caaea/ i?eaiaeeoue aei
aeaoa?i?iiaaiiai i?inoi?iai-/aniaiai ieaio ?ici?uaiiy caaea/ o eiie?aoia
ia/enethaaeueia ioi/aiiy ? aeei?enoiao?oueny a nenoaiao ianiaiai
?icia?aeaethaaiiy. Oey no?aoaa?y i???ioiaaia ia ae??oaiiy caaea/ aeey
niaoe?ae?ciaaieo ia/enethaaeueieo nenoai, aea ieoaiiy aeei?enoiaoaaiiy
eiaeiiai aeaiaioo ?ano?n?a oa i?i?i?caoe?? /ano ae??oaiiy caaea/?
iaeii/anii ? e?eoe/ii aaaeeeaeie.

Iniiaiith caaea/ath noaoe/iiai ieaioaaiiy ? iaoiaeaeaiiy iioeiaeueiiai
aai iioei?ce?iaaiiai ieaio ?ici?uaiiy AIA ia caaeaio e?euee?noue
i?ioeani??a. A i?aoe? icia/aii, ui iiia?aaei?e no?oeoo?iee aiae?c
ii/aoeiai? ?ioi?iaoe?? ? cia?aaeaiiy AIA o y?onii — ia?aeaeuei?e oi?i?
(ssIO) noi?nii c eiia?iaoe??th no?aoaa?e ?ai?oiueiai ? i?caeiueiai
ieaioaaiiy aeicaieythoue iie?aueoe aeai?eoie iiooeo on?o aa?oei, ye?
aoiaeyoue a e?eoe/i? oeyoe Oeieaea- Oi?oaea ? Aeaeeno?e oa io?eiaoe
iiaee aeai?eoi c /aniaith neeaaei?noth I(2A+2N). Aeey aa?oei, ye? ia ?
e?eoe/ieie, aaaaeaii iiiyooy “o?aiceoieo”. O?aiceoia aa?oeia iiaea
iaeaaeaoe o?ueii eaoaai??yi:

yaia o?aiceoi?noue» — ci?iaiiy ??aiy iaeaaeiino? aa?oeie ia ca?eueoo?
e?eoe/iee oeyo ;

Oiiaa aecia/aiiy aa?oeie «yaii? o?aiceoiino?»:

iiiaeeia aa?oei ??aiy “i”

«iayaia o?aiceoi?noue» — neeathaaiiy (eeanoa??caoe?y) aa?oei oe???
eaoaai??? ia iaeiiio ??ai? ia ca?eueoo? e?eoe/iee oeyo ;

Aa?oeia xi «iayaii? o?aiceoiino?” aieiae?? aeanoea?noth:

iiiaeeia aa?oei ??aiy “i”

iiiaeeia aeoa i?ae (Vi-1 ,Vi)/

«ioeueoeie?eaoeaia o?aiceoi?noue» — neeathaaiiy (eeanoa??caoe?y) aa?oei
oe??? eaoaai??? ia ca?eueoo? e?eoe/iee oeyo, i?e oeueiio aa?oeie
iaeaaeaoue ??ciei ??aiyi.

— aa?oeie aieiae?thoue aeanoea?noth ioeueoeie?eaoeaii? o?aiceoiino?
i?ae ??aiyie i oa m,

Aaaaeaiiy o?aiceoiino? ? eeaneo?eaoe?y aa?oei ii aeaeyaeo o?aiceoiino?
ia aoai? iiia?aaeiueiai no?oeoo?iiai aiaeeco AIA aeicaiey? cai?iiiioaaoe
neaioth/ee i?inoi?iai — /aniaee aeai?eoi iaoiaeaeaiiy iioei?ciaaiiai
ieaio ?ici?uaiiy AIA a caaeaiia /enei i?ioeani??a IIN c ni?eueiith
iai’yoth. Eeth/aaa ?aeay iiaiai i?aeoiaeo i?noeoueny ia o iie?ieiaiio
aaaaoii?io?aeiiio neeaaeaii? ?iceeaaeo c aeei?enoaiiyi no?aoaa??
?aiiueiai ieaioaaiiy ? ioe?ii/ieo ooieoe?e, a a oi?ioaaii? nii/aoeo
aaciaiai ??oaiiy i?e ciyoeo iaiaaeaiiyo ia /enei i?ioeani??a ? iio?i
ai?eciioaeuei?e oa aa?oeeaeuei?e eeanoa??caoe?? aa?oei AIA. Iaoa
eeanoa??caoe?? — aaeainoaaiiy AIA ii ??aiyi i?e /ano ieaioaaiiy, ??aiiio
Oe?. I?e eeanoa??caoe?? a?aoiao?oueny eeaneo?eaoe?eia oa?aeoa?enoeea
eiaeii? aa?oeie ii “o?aiceoiino?”. Iaeaaeeoue a?aecia/eoe, ui
aeei?enoaiiy ia?e??oaaiiy aa?oei a?aoa ii iciaoe? o?aiceoiino? ?
aeeiiaiiy ia eiai iniia? eeanoa??caoe?? aeicaiey? iiaoaeoaaoe aaciaee
ieai ??oaiiy c iie?auaieie oa?aeoa?enoeeaie ii e?eueeino?
aeei?enoiaoaa?ieo i?ioeani??a oa ?o iaaaioaaeaiino?. Oea niinoa?aaeaiiy
iniiaaii ia ne?aeoth/iio oaa?aeaeaii?.

Oaa?aeaeaiiy 1.

E?euee?noue i?ioeani??a, iaiao?aeieo aeey ?ici?uaiiy i???ioiaaiiai
aoeeee?/iiai a?aoa, iaiueo aai aei??aith? iaeneiaeuei?e oe?ei? a?aoa.

Oeae i?aeo?ae aeicaieea caanoe NP-iiaio caaea/o a?eueoi? ?ici??iino? aei
NP-iiaii? caaea/? iaei? ?ici??iino?, o.y. i?e aeyaeaii? “o?aiceoiino?”
aa?oei iiooe aa??aioo ?o eeanoa??caoe?? aeeiio?oueny o?eueee a iaaeao
aeae?eaieo ??aiae a?aoo. Aeey aeeiiaiiy i?ioeaaeo? ai?eciioaeueii?
eeanoa??caoe?? a i?aoe? cai?iiiiiaaii aa??noe/iee aeai?eoi
iioei?coth/iai iaeoaaiiy ?ia?o. A aeai?eoi? aeei?enoiaaii noi?uaiiy
no?aoaa?e “iaea?eueo” ? “iaeiaiueo” i?aeoiaeyuee aeey ?ic?aooieo
i?ei?eoao?a ?ia?o, i?aeeyaath/eo ai?eciioaeuei?e eeanoa??caoe??.

Iaoith ?iaioe ieaioaaeueieea — aaeainoaaiiy a?aoo.

Aeeiiaoue aaeainoaaiiy a?aoa — oea caaeainoaaoe aaae ??aiae a?aoa.
Aaeainoaaiiy aeeiio?oueny oeyoii ci?iaiiy aeey aa?oei: i?eiaeaaeiino?
??aiy, aai ?o a?oioaaiiyi (eeanoa??caoe??th).

Iniiaia iaoa eeanoa??caoe?? aai a?oioaaiiy aa?oei — ciaiueoaiiy oe?eie
a?aoa ?, ioaea, ca?aeii oaa?aeaeaiith 1, ciaiueoaiiy e?eueeino?
i?ioeani??a, iaiao?aeieo aeey ae??oaiiy caaea/? a oe?eiio. Ciaiueoaiiy
oe?eie a?aoa oeyoii neeathaaiiy aa?oei ia iiaeiii ca?eueooaaoe e?eoe/iee
oeyo.

Aeey oeueiai aeei?enoiaothoueny ne?aeoth/? oeie eeanoa??caoe??:
ai?eciioaeueia, aa?oeeaeueia, a?oiiaa.

Ai?eciioaeueia eeanoa??caoe?y.

Oea neeathaaiiy aa?oei, iath/eo iciaeo “iayaii? o?aiceoiino?” aac
ca?eueoaiiy e?eoe/iiai oeyoo. I?e aeeiiaii? oe??? eeanoa??caoe?? o?aaa
a?aoiaoaaoe ianooiia:

— on? aa?oeie ia aeae?eaiiio ??ai? ni?oothoueny ia iniia? ianooiii?
oiiae :

(1)

?ioeie neiaaie m = Iaeneiaeueia aaaa ia ??ai? l .

.Aea: X ? iiaith aa?oeiith i?ney eeanoa??caoe?? aa?oei, iath/ith aaao
ia a?eueo m=max(l). Oea ?iaeoueny aeey oiai, uia a?oioaaoe iayai?
o?aiceoi? aa?oeie ? oaeei /eiii ciaiueoeoe oe?eio a?aoa, ioiae,
e?euee?noue i?ioeani??a.

Oaa?aeaeaiiy 2:

Iaoae ie i?aoeth?ii ia iaeiiio c ??ai?a ,a?aoa G, “i”. ( |Ai| = ni =
oe?eia a?aoa ia oeueiio ??ai?. Uia ae??oeoe ia?aeaeueii on? caaea/? ia
oeueiio ??ai? iai o?aaa aeae?eeoe eiaei?e aa?oei? iaeiiai i?ioeani?a, ?
oae aeoiaeeoue, ui e?euee?noue i?ioeani??a aei??aith? e?eueeino? aa?oei
= ni .

( xij ( Ai , if ( xik ,xim ( Ai / Txim (Txik+Txij / m ( Txim

ionoue Xil = (xik + xij ) ; ( A’i = Ai — xik — xij +Xil ( A’i = Ai –
1(aa?oeia)

ni = ni – 1

|A’i| = ni – 1 . Oea aeiaiaeeoue , ui e?euee?noue i?ioeani??a noaea
iaiueoa .

?iaeoa, oiaoi ia ( xik ,xim ( Ai / Txim (Txik+Txij / m ( Txim , oi
oiae? e?euee?noue i?ioeani??a aei??aith? ni = oe?ei? a?aoa.

Aeey ae??oaiiy caaea/? noaoe/iiai ieaioaaiiy c o?aooaaiiyi
eiioi?eaoe?eieo aeo?ao o ?iaio? cai?iiiiiaaiee aeai?eoi ?iciiae?eaiiy
caaea/ ii i?ioeani?ai a IIN, iniiaaiee ia aeei?enoaii? no?aoaa??
aeae?eaiiy, ia eiaei?e ?oa?aoe?? aeai?eoia, e?eoe/iiai oeyoo ?
?ici?uaiiy aa?oei e?eoe/iiai oeyoo ia iaeei i?ioeani?.

I?e ieaioaaii? c a?aooaaiiyi ia?aneeie iaiao?aeii aeeiiaoe ia?aoai?aiiy
ii/aoeiaiai a?aoa c cai?iith ia?aneeie aa?oeiaie a?aoa. Oaeei /eiii
i?ney ia?aoai?aiiy ii/aoeiaiai a?aoa n ia?aneeeaie, io??io?ii aeaaaeaiee
aoeeee?/iee a?ao c ioeueiaeie aaaaie ?aaa?..

Iaoae G(V,E,e,c) aoeeee?/iee i???ioiaaiee a?ao, (a.i.a) aea :

— aa?oeie a?aoa G.

— aeoae, oiaoi, A — oea noeoii?noue aeoa i?ae aa?oeiaie .

oea noeoii?noue aaa aa?oei.

n oea noeoii?noue aaa aeoa.

Ii/aoeiaee aeaeyae a?aoa G iiaeaiee ia iaethieo 1.

A?ao, io?eiaiee i?ney cai?ie eiioi?eaoe?e aa?oeiaie, iieno?oueny
o??eeith Gc (U,E’,e’). Gc (U,E’,e’) aoeeee?/iee i???ioiaaiee a?ao,
(a.i.a) aea :

— aa?oeie a?aoa Gc.

—aeoaa,

oiaoi, A’ — oea noeoii?noue aeoa i?ae aa?oeiaie / |E’|=2*|E| + |V|.

oea noeoii?noue aaa aa?oei.

Aeey aeeiiaiiy ae?e, ia?aaeaa/aieo cai?iiiiiaaiei aeai?eoiii oa
ia/eneaiiy e?eoe/ieo oeyo?a ? aecia/aiiy e?eoe/ieo aa?oei iaiao?aeii
aeeiiaoe aaciaa, iiia?aaei? ?iciiae?eaiiy caaea/ ii i?ioeani?ai. I?e
aaciaiio ?iciiae?eaiith i?eionea?oueny, ui e?euee?noue i?ioeani??a
aei??aith? e?eueeino? aa?oei (caaea/) ii/aoeiaiai a?aoa. I?e aoaeoaaii?
aaciaiai ?iciiae?eaiiy a?aoiaothoueny eiioi?eaoe?ei? aeo?aoe ia
ia?aaea/o ?ioi?iaoe?? i?ae aa?oeiaie. I?e aaciaiio ?iciiae?eaii?
i??ionea?oueny, ui an? ia?aneeee aeeiiothoueny iiai?noth. Ii aaciaiio
?iciiae?eaiith iiaeeeaee i?inoi?iaa-/aniaee iien eiaeii? aa?oeie
(caaea/?) ? aecia/aiiy Tb(xi)l, Tf(xi)l aea:

Tb(xi)l — /an ii/aoeo ??oaiiy caaea/? xi ia i?ioeani?? l.

.

Tf(xi)l — /an caaa?oaiiy caaea/? xi ia i?ioeani?? l.

.

Iiooe ieaio caa?ocee aeeiio?oueny a aeae?eueea yoai?a. Ia?oei yoaiii ?
aeeiiaiiy iia?aoe?e ca’ycaieo c aecia/aiiyi e?eoe/ieo oeyo?a ?
?ici?uaiiy (eeanoa??caoe?y) aa?oei ye? aoiaeyoue aei e?eoe/iiai
oeyoo/oeyoo ia iaeei i?ioeani?.

I?ney oiai, ye aecia/aii e?eoe/iee oeyo ? aa?oeie ye? aoiaeyoue a
iueiai, aeeo/a?ii oe? aa?oeie c a?aoo G, a caaea/?, a?aeiia?aei? oeei
aa?oeiai ?ici?uaaii ia iaeei i?ioeani?. sseui, i?ney ?aaeoeoe?? a?aoa
io?eio?i G1= G — Npc1, yeee ? oe?eei a?aoii, oiaoi G1 o naith /a?ao, ?
a?aoii (a.i.a.), oiae? i?iaeiaaeoaii ooeaoe ianooiiee e?eoe/iee oeyo
Cpc2.aei oeo i?? iiee noa-a?ao Gk = Gk-1 — Cpck ia? iciaee a.i.a.

Ieaioaaiiy aeeiiaiiy caaea/ ia iaeiiio i?ioeani?? i?eaiaeeoue aei
iaioeaiiy /ano eiioi?eaoe?? i?ae aa?oeiaie, ye? aoiaeyoue o e?eoe/iee
oeyo. Oaeei /eiii caa?ocea on?o aa?oei e?eoe/iiai oeyoo ia iaeei
i?ioeani? ciaiueoo? aai aeiaaeeio.

Oaa?aeaeaiiy :

I?e caa?ocoe? e?eoe/iiai oeyoo ia iaeei i?ioeani? ( T’Cpc< TCpc . Aeiaaaeaiiy : (TCpc = S1 + S2 -- ? /an e?eoe/iiai oeyoo. Aea i?e aai caa?ocoe? ia iaeei i?ioeani? S2 = 0 ?, ioaea, /an ae??oaiiy aei?eaith? T’Cpc= TCpc-S2 ( TCpc, oiio ui S2(0. Oaa?aeaeaiiy 3: Iaoae e?eoe/iee oeyo aei??aith? TCpc , yeui ( xi, xi+1 ( Cpc / Tf(xi) = Tb(xi+1) ( TCpc oi /an ieaioaaiiy iioeiaeueiee. Aeiaaaeaiiy : I?e iayaiino? aeae?eueeio e?eoe/ieo oeyo?a, eiaeai caa?oaea?oueny ia ie?aiee i?ioeani?. sseui R = 0, oi e?eoe/iee oeyo ia?ic?eaiee ? caa?ocea iioeiaeueia. oi aa?oeia xk ? i?e/eiith cao?eiee caaea/? (xi+1). I?e oeueiio iiaeeea? o?e aa??aioa. Cpc oiae?: caa?oaea?oueny ia oie i?ioeani?, aea caa?oaeaiee e?eoe/iee oeyo.. Cpc oiae? iiaeeea? aeaa aa??aioe : a) ?ici?noeoe xk ia i?ioeani?? aea caa?oaeaiee Cpc. b) ?ici?noeoe xk ia oiio i?ioeani?? aea tb(xk) i?i?iaeueii. Iiynieii ae?? ia i?eeeaae?. i?ney caa?ocee xk. Oiae? iaeaaeeoue i?iaiae?coaaoe aeeiiaiiy ianooiieo ia??aainoa: txk . 2) tb(xi+2) - t’b(xi+1) >0 .

sseui aeeiiothoueny 1) e 2) oiae? xk caa?oaea?oueny ia i?ioeani? aea
caa?oaeaiee Cpc.

.

3- sseui pred(xk) = A={ x1,x2,…,xm}/A=A1+A2 ; A1( Cpc , A2(Cpc.

Oiaoi yeui /anoeia ?c pred(xk) iaeaaeeoue N?n a ae?oaa /anoeia i?.

A oaeiio aeiaaeeo aecia/a?oueny pred (xk) oa succ(xk).

I?eionoeii, ui :

A1={x1,x2,…,xi} ,

A2={y1,y2,…,yj}/pred(xk)=A1+A2;

B1={X1,X2,…Xm},

B2={Y1,Y2,…,YK} /succ(xk)=B1+B2.

;

( >0 ( xk ( xi (pred(xk)

( <0 ( xk ( xj (succ(xk) ( =0 ( xk ( xi eee xj I?e aeeiiaii? oe??? oiiae iiaeeeaa aeeeth/aiiy, eiee A1({(} ?/aai B1({(} oa A1(Cpc1 , B1(Cpc2 , oiae? aeeiio?ii ianooii? ae??: Iaoae d1= |Tf(xi1) – Tb(xi1+1)|; d2= |Tf(xi2) – Tb(xi2+1)| ; oiae? : sseui d1( Txk e Tbsucc(xi+1)-Tbsucc(xi1+1) >0 , oi xk(Cpc1.

sseui d2( Txk e Tbsucc(xi+1)-Tbsucc(xi2+1)(0 , oi xk(Cpc2.

sseui di=0 aai di( Txk , oi xk( max ( Tbsucc(xk)i) .

Oaia? yeui succ(xi) (B1(xi(G ,oiae? iiaeeea? aeaa aa??aioe :

( |Tb(xi)-Tb(xi+1)| ( T(succ(xi)) ( succ(xi )(
Cpc

xi(Cpc ((

( |Tb(xi)-Tb(xi+1)| < T(succ(xi)) ( succ(xi) A oaeiio ?ac? aa?oeia cae??ieth?oueny ca nai?i i?ioeani?ii ? ia iiaea aooe eeanoa??ciaaia. 2) xi(Cpc , oi oiae? succ(xi) ( max ( Tb(succ(xi)). I?eaaaeai? a ?iaio? ?acoeueoaoe iiaeaethaaiiy aeicaieythoue c?iaeoe aeniiaie i?i aeinoia??i?noue cai?iiiiiaaieo iaoiae?a e oai?aoe/ieo aeine?aeaeaiue. *aniaa neeaaei?noue cai?iiiiiaaieo aeai?eoi?a a?aeiia?aea? ?ic?aooieia?e. Ii??aiyeueiee aiae?c ?acoeueoao?a ieaioaaiiy cai?iiiiiaaieie aeai?eoiaie c iaea?eueo a?aeiieie ii oaeei iieacieeai ye: /an ieaioaaiiy, /enei aeei?enoiaoaa?ieo i?ioeani??a, ia?aioneii? caeaoiino? IIN iieaco? ?o aenieo aoaeoeai?noue i?e caaeaieo iaiaaeaiiyo. ?en 1. Na?aaeiy e?euee?noue i?ioeani??a Iae. 2. Na?aaei?e /an ieaioaaiiy Iae. 3 Ii??aiyiiy /ano ieaioaaiiy aeey ?ica’ycaiiy caaea/? Aaona 8-ia aeai?eoiaie A oaae. 1 i?aaenoaaeaii n?aaiaiaiea au/eneeoaeueiie neiaeiinoe i?aaeeiaeaiiiai aeai?eoia n ecaanoiuie. Oaae 1 AEAI?EOI NEEAAeI?NOUe EZ O(e(e+V) MCP O(v2logv) MD O(v3) EFT O(pv2) DLS O(v3pf(p)) DSC O((e+v)logv) DCP O(v3) KIM O(v log v) DCPC I?iiiioaiee aeai?eoi O(v(v-1)+2e) INIIAI? IAOEIA? OA I?AEOE*I? ?ACOEUeOAOE ?IAIOE IIEssAATHOUe Nss A IANOOIIIIO Aeeiiaiee aiae?c no?oeoo?ii? i?aai?caoe?? ia?aeaeueieo nenoai ia?iaee ?ioi?iaoe??, iieacai? iniaeeaino? ia?aeaeueieo ia/enethaaeueieo nenoai ye? aieeaathoue ia aoaeoeai?noue iaai?caoe?? ia/enethaaeueiiai i?ioeana. I?iaiae?ciaai? ? aeine?aeaeai? iniaeeaino? nenoai ieaioaaiiy aeey oi?aae?iiy ? aeeniao/a?ecaoe?? ?ia?o a IN; iieacaia iaiao?aei?noue ?ac?iaee iiaeo aaaaoi??aiaaeo nenoai ieaioaaiiy, i?aeaeuaiiy ia?aioneii? caeaoiino? IN. Aeine?aeaeaia iiaeaeue nenoaie noaoe/iiai ieaioaaiiy a IIN, aeaia iaoaiaoe/ia iinoaiiaea caaea/? noaoe/iiai ?iciiae?eaiiy ?ia?o ii ?ano?nai. ?ic?iaeaiee iaoiae neaioth/iai i?inoi?iai-/aniaiai ieaioaaiiy aca?iica’ycaieo ?ia?o, a iaaeao yeiai ?aae?ciaaiee iiaee i?aeo?ae aei ??oaiiy caaea/? neeaaeaiiy ?iceeaaeo, iniiaaiee ia ?aea? no?oeoo?ii — naiaioe/iiai aiae?co a?aoa ii/aoeiai? caaea/? ? cae?eniaiiy ia eiai iniia? ???a?o?/ii? aeaeiiiiceoe?? ia/enethaaeueiiai i?ioeano ia a?aoiaiio ??ai?. Cai?iiiiiaaiee iiaee aeai?eoi iiooeo aa?oei, ye? aoiaeyoue a e?eoe/i? oeyoe, ui a niieo/aii? c no?oeoo?ii-naiaioe/iei aiae?cii ? aeaeiiiiceoe??th ii/aoeiaiai a?aoa, aeicaieeei aeae?eeoe a a?ao? "?aceaeaioi?", "o?aiceoi?" oa "ioeueoeo?aiceoi?" aa?oeie, caanoe yeniiiaioe?aeueio /aniao neeaaei?noue caaea/? a?eueoi? ?ici??iino? aei NP-iiaieo iaeeo aeene?aoieo caaea/ ? aeyeoth/e oeueiio io?eiaoe i?eionoeiee /an ?? ae??oaiiy. ?ic?iaeaia nenoaia iiaeaethaaiiy, aeicaieyth/a aeeiioaaoe oe?ieiianooaaia ii??aithaaeueia aeine?aeaeaiiy cai?iiiiiaaiiai iaoiaea ? cania?a noaoe/iiai ieaioaaiiy c a?aeiieie, iiaeaethaaiiy i?aeoaa?aeeei aoaeoeai?noue cai?iiiiiaaieo a aeena?oaoe?ei?e ?iaio? iaoiaea ? cania?a ieaioaaiiy. ?acoeueoaoe aeena?oaoe?? a?aeaeo? a ianooiieo iaoeiaeo ?iaioao. Naaaea Iooaiiaae Ae?, Neiiiaiei A.A., A?aoi - aiae?oe/iee iaoiae eieae?caoe?? ciie iiooeo ??oaiiy a nenoaiao ?iciiae?eaii? ia?iaee ?ioi?iaoe??, E., Ca??iee iaoeiaeo ?ia?o Ee?anueeiai i?aeia?iaeiiai oi?aa?neoaoo oeea?eueii? aa?aoe?? “I?iaeaie i?aeaeuaiiy aoaeoeaiino? ?io?ano?oeoo?e”, 1998 ?., 291-313 n. Naaaea Iooaiiaae Ae?, Neiiiaiei A.A., Ia?aaei?ioeani?ia ?iciiae?eaiiy ?ia?o aeey eeanoa?ieo ?iai/eo noaioe?e, E., Ca??iee iaoeiaeo ?ia?o Ee?anueeiai i?aeia?iaeiiai oi?aa?neoaoo oeea?eueii? aa?aoe?? “I?iaeaie i?aeaeuaiiy aoaeoeaiino? ?io?ano?oeoo?e”, 1998 ?., 314-327 n.. Naaaea Iooaiiaae Ae?, Neiiiaiei A.I., Caaaeueia noaia i?ioeano ieaioaaiiy i?ioean?a a ia?aeaeueieo ia/enethaaeueieo nenoaiao, E., A?niee Iaoe?iiaeueiiai oaoi?/iiai oi?aa?n?oaoo Oe?a?ie «EI?» , Na??y «?ioi?iao?ea, oi?aae?iiy oa ia/enethaaeueia oaoieea», ?31,1998 ?., 61-70. (Aeeiiaiee aiae?c iniae?ainoae nenoai ieaioaaiiy aeey ia?aeaeueieo ia/enethaaeueieo nenoai). Naaaea Iooaiiaae Ae?, Neiiiaiei A.I., Iniiaa no?oeoo?iiai aiae?co ii/aoeiaiai a?aoa aeey i?i?i?caoe?? /enea i?ioeani??a i?e ieaioaaii? a ia?aeaeueieo ia/enethaaeueieo nenoaiao, E., A?niee Iaoe?iiaeueiiai oaoi?/iiai oi?aa?n?oaoo Oe?a?ie «EI?» , Na??y «?ioi?iao?ea, oi?aae?iiy oa ia/enethaaeueia oaoieea», ?31,1998 ?., 71-80. (Aeeiiaii oai?aoe/ia iaa?oiooaaiiy no?oeoo?iiai aiae?co). Naaaea Iooaiiaae Ae?, Iaoiae ? caniae noaoe/iiai ieaioaaiiy caaea/ a ia?aeaeueieo ia/enethaaeueieo nenoaiao. —?oeiien. Aeena?oaoe?y ia caeiaoooy iaoeiaiai nooiaiy eaiaeeaeaoa oaoi?/ieo iaoe ca niaoe?aeueiinoth 05.13.13 ( ia/enethaaeuei? iaoeie, nenoaie ? ia?aae?, Iaoe?iiaeueiee oaoi?/iee oi?aa?neoao Oe?a?ie, “Ee?anueeee iie?oaoi?/iee ?inoeooo”, Ee?a, 1997. Aeena?oaoe?y i?enay/aia aeine?aeaeaiith ieoaiue i?aeaeuaiiy aoaeoeaiino? iaoiae?a ? aeai?eoi?a ae??oaiiy caaea/ noaoe/iiai ieaioaaiiy a ia?aeaeueieo ia/enethaaeueieo nenoaiao. Ae??oaia caaea/a ?ic?iaee aenieiaoaeoeaieo cania?a i?iaeooaaiiy aaeaioeaieo noaoe/ieo ieaioaaeueiee?a, caaacia/oth/eo a oiiaao i?inoi?iai-/aniaeo iaiaaeaiue noaoe/ii? i?aai?caoe?? ia/enethaaeueiiai i?ioeano. A aeena?oaoe?? cai?iiiiiaaiee iiaee i?aeo?ae aei ??oaiiy caaea/? ?iciiae?eaiiy ?ia?o c i?i?i?caoe??th caaaeueiiai /ano ??oaiiy ? eiioi?eaoe?eieo aeo?ao. ?ic?iaeaiee iaoiae ? caniae aeeiiaiiy i?ioeaaeo? ni?yiiaaiiai iiooeo ?iciiae?eaiiy ?ia?o a IIN c oeaio?ae?ciaaiei oi?aae?iiyi. Aecia/aie i?ioeaaeo?e ai?eciioaeueii? ? aa?oeeaeueii? eeanoa??caoe?? ye? ? iniiaith no?oeoo?iiai aiae?co ii/aoeiai? ?ioi?iaoe?? ? ?aae?coth/? iaoiae ? aeai?eoi neaioth/iai i?inoi?iai-/aniaiai ?iciiae?eaiiy. Eeth/ia? neiaa: ia?aeaeuei? ia/enethaaeuei? nenoaie, ieaioaaiiy, noaoe/ia ieaioaaiiy, aaaaoii?ioeanni?ia ?iciiae?eaiiy. Naaaea Iooaiiaae Aee, Iaoiae e n?aaenoaa noaoe/aneiai ieaie?iaaiey caaea/ a ia?aeeaeueiuo au/eneeoaeueiuo nenoaiao. —?oeiien. Aeenna?oaoeey ia nieneaiea o/aiie noaiaie eaioeaeaoa oaoie/aneeo iaoe ii niaoeeaeueiinoe 05.13.13 ( au/eneeoaeueiua iaoeiu, nenoaiu e naoe, Iaoeeiiaeueiue oaoie/aneee oieaa?neoao Oe?aeiu, “Eeaaneee iieeoaoie/aneee einoeooo”, Eeaa, 1997. Aeenna?oaoeey iinayuaia enneaaeiaaieth aii?inia iiauoaiey yooaeoeaiinoe iaoiaeia e aeai?eoiia ?aoaiey caaea/ noaoe/aneiai ieaie?iaaiey a ia?aeeaeueiuo au/eneeoaeueiuo nenoaiao. ?aoaia caaea/a ?ac?aaioee aunieiyooaeoeaiuo n?aaenoa i?iaeoe?iaaiey aaeaioeaiuo noaoe/aneeo ieaie?iaueeia, iaania/eaathueo a oneiaeyo i?ino?ainoaaiii-a?aiaiiuo ia?aie/aiee noaoe/aneie i?aaiecaoeeth au/eneeoaeueiiai i?ioeanna. A aeenna?oaoeee i?aaenoaaeai iiaue iiaeoiae e ?aoaieth caaea/e ?ani?aaeaeaiey ?aaio n ieieiecaoeeae iauaai a?aiaie ?aoaiey e eiiioieeaoeeiiiuo cao?ao. ?ac?aaioai iaoiae e n?aaenoaa auiieiaiey i?ioeaaeo? iai?aaeaiiiai iienea ?ani?aaeaeaiey ?aaio a IAN n oeaio?aeeciaaiiui oi?aaeaieai. Ii?aaeaeaiu i?ioeaaeo?u ai?eciioaeueiie e aa?oeeaeueiie eeanoa?ecaoeee yaeythueany iniiaie no?oeoo?iiai aiaeeca enoiaeiie eioi?iaoeee e ?aaeecothuea iaoiae e aeai?eoi neaie?othoaai i?ino?ainoaaiii-a?aiaiiiai ?ani?aaeaeaiey. Eeth/aaua neiaa: ia?aeeaeueiua au/eneeoaeueiua nenoaiu, ieaie?iaaiea, noaoe/aneia ieaie?iaaiea, iiiaii?ioeanni?iia ?anienaiea. Saade Mouhammed Ali, "Methods and means of statistical scheduling of tasks in parallel computer systems".- Manuscript. Thesis for a Ph.D degree by speciality 05.13.13 — computers, system and network, National technical university of Ukraine, "Kiev politechnical institute", Kiev, 1998. The dissertation is devoted to studies of efficiency increase in methods and algorithms of statistical scheduling task solutions in parallel computer systems. There has been a successful resolution of the task on development of highly efficient means of scheduling of adaptive statistical schedulers that would provide for statistical organization of computing process in the conditions of spatio-temporal limitations. The dissertation presented a new approach to resolution of the task on work scheduling while minimizing total runtime and communication costs. There have been developed methods and means for execution of addressed search procedures of work scheduling in central control parallel computer systems. There have been identified procedures of horizontal and vertical clustering being the basis of source data structural analyses and implementing scanning spatio-temporal scheduling method and algorithm. Key words: parallel computer systems, scheduling, statical scheduling, multiprocessor schedule. PAGE PAGE 4 0 ) ( ) ( f k k x succ x succ T T c - MAX(T (x ) x ? P b k j j rk " )

Похожие записи