Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://asa.guru.ru/papers/pap4.ps Äàòà èçìåíåíèÿ: Sat Aug 1 11:26:48 1998 Äàòà èíäåêñèðîâàíèÿ: Mon Oct 1 19:52:39 2012 Êîäèðîâêà: IBM-866

a. s. aNTONOW, wL. w. wOEWODIN, w. m. rEPIN
aLGORITM KANONIZACII OPISANIQ
STRUKTURY PROGRAMM W RAMKAH
LINEJNOJ MODELI \Lambda
1 wWEDENIE
dOKAZANO, ÓTO DLQ BOLX[OGO KLASSA PROGRAMM MOVNO POSTROITX PARAí
METRIÓESKOE OPISANIE IH GRAFA ALGORITMA (INFORMACIONNOJ ISTORII)
SREDSTWAMI TOLXKO STATIÓESKOGO ANALIZA W SLEDU@]EM WIDE [1,2]. dLQ
KAVDOGO WHODA KAVDOGO OPERATORA ANALIZIRUEMOJ PROGRAMMY UKAZYWAí
ETSQ KONEÓNOE ÓISLO TROEK (F; \Delta I ; \Delta N ). \Delta N --- LINEJNYJ MNOGOGRANNIK
W
PROSTRANSTWE\Omega N WNE[NIH PEREMENNYH PROGRAMMY, ZNAÓENIQ KOTOí
RYH NA MOMENT POSTROENIQ GRAFA NEIZWESTNY. \Delta I --- LINEJNYJ MNOGOí
GRANNIK W PROSTRANSTWE
ITERACIJ\Omega I , RAZMERY I POLOVENIE KOTOROGO
MOGUT ZAWISETX OT TOÓEK MNOGOGRANNIKA \Delta N . fUNKCIQ F LINEJNAQ I
IMEET WID F = Jx + \PhiN , GDE N --- ``TO WEKTOR WNE[NIH PEREMENNYH
PROGRAMMY, A J , \Phi --- CELOÓISLENNYE MATRICY. oBLASTX@ OPREDELENIQ
FUNKCII F QWLQETSQ MNOGOGRANNIK \Delta I . zNAÓENIQMI FUNKCIJ QWLQ@Tí
SQ TOÓKI PROSTRANSTWA ITERACIJ, PRIÓEM TOÓKA x ZADAET KONEÓNU@
WER[INU DUGI, A WYRAVENIE Jx + \PhiN --- NAÓALXNU@.
mNOGOGRANNIKI \Delta I I \Delta N ZADA@TSQ SISTEMAMI LINEJNYH URAWNENIJ
I NERAWENSTW S CELOÓISLENNYMI KO``FFICIENTAMI, I NIKAKIH DOPOLNIí
TELXNYH OGRANIÓENIJ NA NIH, WOOB]E GOWORQ, NE NAKLADYWAETSQ. wMEí
STE S TEM, ÓASTO WOZNIKAET NEOBHODIMOSTX PRIWESTI DANNOE OPISANIE K
KANONIÓESKOJ FORME, KOTORAQ PODRAZUMEWAET WYPOLNENIE SLEDU@]IH
USLOWIJ:
\Lambda rABOTA PODDERVANA rOSSIJSKIM fONDOM fUNDAMENTALXNYH iSSLEDOWANIJ, GRANT 96--
01--01433

ffl NIKAKIE IZ MNOGOGRANNIKOW \Delta I , \Delta N NE QWLQ@TSQ CELOÓISLENNO
PUSTYMI, T.E. WSE ONI SODERVAT HOTQ BY ODNU TOÓKU S CELOÓISLENNYMI
KOORDINATAMI;
ffl NI ODNO IZ OGRANIÓENIJ MNOGOGRANNIKOW \Delta I , \Delta N NE QWLQETSQ IZí
BYTOÓNYM;
ffl NI ODNO IZ REBER MNOGOGRANNIKOW \Delta I NE MOVET STQGIWATXSQ W TOÓí
KU NI PRI KAKIH ZNAÓENIQH WNE[NIH PEREMENNYH IZ SOOTWETSTWU@]EGO
MNOGOGRANNIKA \Delta N .
nEOBHODIMOSTX PRIWEDENIQ K KANONIÓESKOJ FORME WOZNIKAET PO MNOí
GIM PRIÓINAM. wOíPERWYH, W PROCESSE POSTROENIQ SAMOGO GRAFA ALGOí
RITMA VELATELXNO SRAZU WYKIDYWATX PUSTYE MNOGOGRANNIKI, TAK KAK
W PROTIWNOM SLUÓAE WREMQ POSTROENIQ MOVET ZNAÓITELXNO UWELIÓITXSQ
(ZDESX I DALEE POD PUSTOTOJ BUDEM PONIMATX OTSUTSTWIE W MNOGOGRANNIí
KE TOÓKI S CELOÓISLENNYMI KOORDINATAMI). wOíWTORYH, MNOGIE SWOJí
STWA PROGRAMM, OPREDELQEMYE PO WIDU FUNKCIJ F , MOGUT ISKAVATXSQ
IMENNO NA PUSTYH OBLASTQH, ÓTO NEDOPUSTIMO, I PO``TOMU WSE TROJKI S
PUSTYMI OBLASTQMI DOLVNY BYTX UDALENY. wíTRETXIH, DLQ GENERACII
``FFEKTIWNYH PROGRAMM W OPISANII MNOGOGRANNIKOW NE DOLVNO BYTX
IZBYTOÓNYH OGRANIÓENIJ, TAK KAK ``TO PRIWEDET K POQWLENI@ LI[NIH
PROWEROK W USLOWNYH OPERATORAH NOWOJ PROGRAMMY. i, NAKONEC, CEí
LYJ KLASS METODOW ANALIZA STRUKTURY I SWOJSTW PROGRAMM TREBUET
WYPOLNENIQ POSLEDNEGO USLOWIQ KANONIÓESKOGO OPISANIQ, KOTOROE GAí
RANTIRUET SOHRANNOSTX ``FORMY'' WSEH MNOGOGRANNIKOW \Delta I .
dANNAQ METODIKA KANONIZACII SRAZU ORIENTIROWANA NA PRAKTIÓEí
SKOE PRIMENENIE. sNAÓALA IZLAGA@TSQ PROSTYE, NO ``FFEKTIWNYE MEí
TODY, OSNOWANNYE NA DOSTATOÓNYH USLOWIQH I RABOTA@]IE W BOLX[INí
STWE REALXNYH SITUACIJ, I LI[X W KONCE IDET POLNAQ PROWERKA.
iTAK, PUSTX DANA OBLASTX W PROSTRANSTWE ITERACIJ \Delta I = fAI ß
BN +Cg, GDE I 2 Z n\Theta1 --- WEKTOR PARAMETROW CIKLOW, N 2 Z k\Theta1 --- WEKí
TOR WNE[NIH PEREMENNYH, A 2 Z m\Thetan , B 2 Z m\Thetak I C 2 Z m\Theta1 --- ZADANí
NYE MATRICY I WEKTOR. kROME TOGO, ZADANY OGRANIÓENIQ NA WNE[NIE
PEREMENNYE \Delta N = fFN ß Dg, GDE F 2 Z l\Thetak I D 2 Z l\Theta1 --- ZADANNYE
MATRICA I WEKTOR. w NEKOTORYH SLUÓAQH W OPISANII OBLASTEJ \Delta N I \Delta I

WMESTO NERAWENSTW MOGUT BYTX RAWENSTWA. w DALXNEJ[EM, I RAWENSTWA,
I NERAWENSTWA BUDEM NAZYWATX OGRANIÓENIQMI.
oPISYWAEMYJ DALEE ALGORITM KANONIZACII OPIRAETSQ NA RABOTU
[3]. wSE DEJSTWIQ ALGORITMA PROIZWODQTSQ NAD OGRANIÓENIQMI S CEí
LOÓISLENNYMI KO``FFICIENTAMI. w DALXNEJ[EM SU]ESTWENNO, ÓTO NI
ODNO DEJSTWIE ALGORITMA NE NARU[AET ``TOGO USLOWIQ.
2 oPISANIE ALGORITMA KANONIZACII
2.1 nORMALIZACIQ
sNAÓALA PROIZWODITSQ PROCESS, NAZYWAEMYJ W [3] NORMALIZACIEJ. oN
ZAKL@ÓAETSQ W PRIWEDENII nod KO``FFICIENTOW PRI PEREMENNYH W OPIí
SANII OBLASTEJ \Delta I I \Delta N K 1. kROME TOGO, ÓTO NORMALIZACIQ NEOBHODIí
MA DLQ PROWEDENIQ oMEGAíTESTA, OPISYWAEMOGO DALEE, ONA POLEZNA I PO
DRUGIM SOOBRAVENIQM. wOíPERWYH, UMENX[A@TSQ ABSOL@TNYE ZNAÓEí
NIQ KO``FFICIENTOW PRI PEREMENNYH. wOíWTORYH, W NEKOTORYH SLUÓAQH
POSLE NORMALIZACII OBLASTX SUVAETSQ, ILI UPRO]AETSQ DALXNEJ[IJ
ANALIZ. nAPRIMER, PRI POISKE PARALLELXNYH GIPERPLOSKOSTEJ DO NORí
MALIZACII NUVNO ISKATX OGRANIÓENIQ S PROPORCIONALXNYMI KO``FFIí
CIENTAMI, A POSLE NORMALIZACII --- LI[X S ODINAKOWYMI PO MODUL@
KO``FFICIENTAMI.
dLQ TOGO, ÓTOBY NORMALIZOWATX OGRANIÓENIE a 1 i 1 + : : : + a n i n ß
b 1 n 1 + : : : + b k n k + c, WYÓISLQETSQ NAIBOLX[IJ OB]IJ DELITELX g KO``Fí
FICIENTOW a 1 ; : : : ; a n ; b 1 ; : : : ; b k , I WSE KO``FFICIENTY, WKL@ÓAQ c, DELQTí
SQ NA g. eSLI c NE DELITSQ NACELO NA g, TO W KAÓESTWE SWOBODNOGO ÓLENA
BERèETSQ bc=gc, PRI ``TOM GIPERPLOSKOSTX W
PROSTRANSTWE\Omega I
\Theta\Omega N , SOí
OTWETSTWU@]AQ OGRANIÓENI@, SDWIGAETSQ DO BLIVAJ[EJ CELOÓISLENí
NOJ TOÓKI, A ANALIZIRUEMAQ OBLASTX SUVAETSQ. eSLI NORMALIZUETSQ
OGRANIÓENIEíRAWENSTWO a 1 i 1 + : : : + a n i n = b 1 n 1 + : : : + b k n k + c, I S
NE DELITSQ NACELO NA g, TO DANNOE URAWNENIE NE IMEET CELOÓISLENNYH
RE[ENIJ, I, SLEDOWATELXNO, WSQ OBLASTX BUDET CELOÓISLENNO PUSTOJ.
tAKIM OBRAZOM NORMALIZU@TSQ OGRANIÓENIQ KAK IZ \Delta I , TAK I IZ \Delta N .

2.2 iSKL@ÓENIE PEREMENNYH IZ RAWENSTW
dLQ ISKL@ÓENIQ PEREMENNOJ IZ RAWENSTWA NEDOSTATOÓNO DEJSTWOWATX
OBYÓNYM METODOM --- DOMNOVENIEM KO``FFICIENTOW OGRANIÓENIQ NA KOí
``FFICIENT IZ DRUGOGO OGRANIÓENIQ PRI ISKL@ÓAEMOJ PEREMENNOJ, TAK
KAK W ``TOM SLUÓAE MOVNO RE[ITX TOLXKO ZADAÓU OPREDELENIQ RACIOí
NALXNOJ NEPUSTOTY OBLASTI, POSLE ÓEGO OSTAETSQ NERE[ENNYM WOPROS,
PRINADLEVIT LI OBLASTI HOTQ BY ODNA CELOÓISLENNAQ TOÓKA.
iSKL@ÓENIE PEREMENNYH IZ RAWENSTW, IZLOVENNOE W [3], POZWOLQET
UMENX[ITX RAZMERNOSTX RASSMATRIWAEMOJ OBLASTI I UPROSTITX WSE POí
SLEDU@]IE ALGORITMY. pRI ``TOM KO``FFICIENT PRI ISKL@ÓAEMOJ PEREí
MENNOJ WSEGDA PRIWODITSQ K EDINICE, ÓTO POZWOLQET RE[ITX NE TOLXKO
ZADAÓU OPREDELENIQ RACIONALXNOJ NEPUSTOTY, NO I ZADAÓU OPREDELENIQ
CELOÓISLENNOJ NEPUSTOTY.
2.2.1 iSKL@ÓENIE PEREMENNYH IZ RAWENSTW, WHODQ]IH W OPIí
SANIE OBLASTI IZ PROSTRANSTWA WNE[NIH PEREMENNYH
~TOBY ISKL@ÓITX PEREMENNU@ IZ RAWENSTWA f 1 n 1 + : : : + f k n k = d, WHOí
DQ]EGO W OPISANIE OBLASTI IZ PROSTRANSTWA WNE[NIH PEREMENNYH, SNAí
ÓALA PROWERIM, NET LI TAKOGO j, ÓTO jf j j = 1. eSLI TAKOE j ESTX, TO
PROSTO WYRAVAEM PEREMENNU@ n j ÓEREZ OSTALXNYE PEREMENNYE I SWOí
BODNYJ ÓLEN, POSLE ÓEGO WYRAVENIE DLQ n j PODSTAWLQEM WO WSE OSTALXí
NYE OGRANIÓENIQ.
eSLI OGRANIÓENIE NE SODERVIT KO``FFICIENTOW, PO MODUL@ RAWNYH
1, TO OBOZNAÓIM ÓEREZ p KO``FFICIENT S NAIMENX[IM ABSOL@TNYM ZNAí
ÓENIEM, I PUSTX s = jf p j + 1. oPREDELIM d
mod SLEDU@]IM OBRAZOM:
a d
mod b = a \Gamma bba=b + 1=2c:
oPREDELIM NOWU@ PEREMENNU@ oe TAKU@, ÓTO
soe =
X
j
(f j
d
mod s)n j + d d
mod s:

zAMETIM, ÓTO f p
d
mod s = \Gammasign(f p ). pO``TOMU WYRAZIM IZ DANNOGO
RAWENSTWA PEREMENNU@ n p :
n p = \Gammasign(f p )soe +
X
j 6=p
sign(f p )(f j
d
mod s)n j + sign(f p )d d
mod s
I PODSTAWIM WO WSE OGRANIÓENIQ. dLQ ISHODNOGO RAWENSTWA POSLE PODí
STANOWOK I NORMALIZACII POLUÓIM
\Gammajf p joe +
X
j 6=p
i
bf j =s + 1=2c + (f j
d
mod s)
j
n j + bd=s + 1=2c + d d
mod s = 0:
mODULX KO``FFICIENTA PRI PEREMENNOJ oe POLUÓAETSQ RAWNYM MODUL@
KO``FFICIENTA PRI ISHODNOJ PEREMENNOJ n p , A WSE OSTALXNYE KO``FFIí
CIENTY UMENX[A@TSQ PO KRAJNEJ MERE W POLTORA RAZA. pO``TOMU POSLE
NESKOLXKIH POWTORENIJ ``TOGO ALGORITMA PRI KAKOJíNIBUDX PEREMENNOJ
POLUÓITSQ KO``FFICIENT, PO MODUL@ RAWNYJ 1, ÓTO POZWOLIT NAM ISí
KL@ÓITX ``TU PEREMENNU@.
tAKIM OBRAZOM MOVNO ISKL@ÓITX STOLXKO PEREMENNYH, SKOLXKO IMEí
ETSQ RAWENSTW W OPISANII OBLASTI \Delta N . sOOTWETSTWENNO NA STOLXKO VE
UMENX[ITSQ RAZMERNOSTX
PROSTRANSTW\Omega N
I\Omega I
\Theta\Omega N .
2.2.2 iSKL@ÓENIE PEREMENNYH IZ RAWENSTW, WHODQ]IH W OPIí
SANIE OBLASTI IZ PROSTRANSTWA ITERACIJ
iSKL@ÓATXSQ IZ RAWENSTW, WHODQ]IH W OPISANIE OBLASTI PROSTRANSTWA
ITERACIJ, DOLVNY TOLXKO PEREMENNYE PROSTRANSTWA ITERACIJ, LIBO,
ESLI POSLE NEKOTOROGO KOLIÓESTWA ISKL@ÓENIJ W RAWENSTWE OSTANUTSQ
TOLXKO WNE[NIE PEREMENNYE, TO ISKL@ÓAETSQ ODNA IZ NIH S ZAPOMINAí
NIEM WYPOLNQEMYH PODSTANOWOK. pODSTANOWKI PRI ISKL@ÓENII I PRI
WWEDENII NOWYH PEREMENNYH DOLVNY ZAPOMINATXSQ DLQ POSLEDU@]EGO
DOBAWLENIQ K OPISANIQM CELOÓISLENNO NEPUSTYH OBLASTEJ.
rASSMOTRIM ODNO IZ OGRANIÓENIJíRAWENSTW, WHODQ]IH W OPISANIE
OBLASTI PROSTRANSTWA ITERACIJ: \Gamma = a 1 i 1 + : : : + a n i n = b 1 n 1 + : : : +
b k n k + c. pOSLE NORMALIZACII NAIBOLX[IJ OB]IJ DELITELX KO``FFIí
CIENTOW PRI WSEH PEREMENNYH RAWEN 1, ODNAKO DLQ KO``FFICIENTOW PRI

PEREMENNYH PROSTRANSTWA ITERACIJ ``TO MOVET BYTX NE TAK. pUSTX g
--- NAIBOLX[IJ OB]IJ DELITELX KO``FFICIENTOW PRI PEREMENNYH PROí
STRANSTWA ITERACIJ. tOGDA
ffl ESLI g = 0, TO W OGRANIÓENIE WHODQT TOLXKO WNE[NIE PEREMENNYE;
W ``TOM SLUÓAE OPISANNYM RANEE OBRAZOM ISKL@ÓAETSQ ODNA IZ NIH
S ZAPOMINANIEM PROIZWODIMYH PODSTANOWOK;
ffl ESLI g = 1, TO ISKL@ÓAEM ODNU IZ PEREMENNYH PROSTRANSTWA
ITERACIJ ANALOGIÓNO TOMU, ÓTO BYLO OPISANO DLQ PROSTRANSTWA
WNE[NIH PEREMENNYH;
ffl ESLI g ? 1, TO WWODIM NOWU@ PEREMENNU@ oe I DOBAWLQEM OGRANIí
ÓENIE
goe =
n
X
j=1
(a j
d
mod g)i j \Gamma
k
X
j=1
(b j
d
mod g)n j \Gamma (c d
mod g):
pEREMENNU@ oe W DALXNEJ[EM ISPOLXZUEM KAK WNE[N@@ PEREMENí
NU@. pOSLE ISKL@ÓENIQ PEREMENNOJ IZ POLUÓENNOGO RAWENSTWA I
NORMALIZACII POLUÓAEM, ÓTO W ISHODNOM RAWENSTWE NAIBOLX[IJ
OB]IJ DELITELX KO``FFICIENTOW PRI PEREMENNYH PROSTRANSTWA
ITERACIJ RAWEN 1.
tAKIM OBRAZOM MOVNO ISKL@ÓITX STOLXKO PEREMENNYH, SKOLXKO IMEí
ETSQ RAWENSTW W OPISANII OBLASTI \Delta I . sOOTWETSTWENNO NA STOLXKO VE
UMENX[ITSQ RAZMERNOSTX
PROSTRANSTW\Omega I
I\Omega I
\Theta\Omega N .
2.3 ---WRISTIÓESKIE METODY
pRIMENQEMYE ZDESX ``WRISTIKI NE DA@T POLNOGO I TOÓNOGO RE[ENIQ W
OB]EM SLUÓAE, NO, KAK POKAZYWAET PRAKTIKA, POZWOLQ@T POKRYTX DOí
STATOÓNO BOLX[OJ KLASS REALXNYH FRAGMENTOW PROGRAMM. pRI ``TOM
WAVNO, ÓTO OPISYWAEMYE ``WRISTIKI DOSTATOÓNO PROSTYE I PROWERQ@Tí
SQ BYSTRO. sNAÓALA I]EM PARALLELXNYE GIPERPLOSKOSTI
\Gamma i = a i1 i 1 + : : : + a in i n ß b i1 n 1 + : : : + b ik n k + c i ;

\Gamma j = a j1 i 1 + : : : + a jn i n ß b j1 n 1 + : : : + b jk n k + c j ; 1 ß i 6= j ß m,
TAKIE, ÓTO a i1
a j1
= : : : = a ik
a jk
= p.
uMNOVAQ OGRANIÓENIE \Gamma i NA ja j1 j I OGRANIÓENIE \Gamma j NA ja i1 j; POLUÓIM
\Gamma 0
i = a 0
i1 i 1 + : : : + a 0
in i n ß b 0
i1 n 1 + : : : + b 0
ik n k + c 0
i ;
\Gamma 0
j = a 0
j1 i 1 + : : : + a 0
jn i n ß b 0
j1 n 1 + : : : + b 0
jk n k + c 0
j ; 1 ß i 6= j ß m,
GDE a 0
i1
a 0
j1
= : : : = a 0
ik
a 0
jk
= p 0 , GDE p 0 = 1 ILI p 0 = \Gamma1.
w PERWOM SLUÓAE (p 0 = 1) I]EM I OTBRASYWAEM IZBYTOÓNYE NERAWENí
STWA: ESLI b 0
i1 n 1 +: : :+b 0
ik n k +c 0
i ß b 0
j1 n 1 +: : :+b 0
jk n k +c 0
j , TO OGRANIÓENIE \Gamma 0
j
QWLQETSQ IZBYTOÓNYM, I EGO MOVNO OTBROSITX, INAÓE MOVNO OTBROSITX
IZBYTOÓNOE OGRANIÓENIE \Gamma 0
i . pRI ``TOM WSQ
OBLASTX\Omega N PROSTRANSTWA
WNE[NIH PEREMENNYH MOVET RAZBITXSQ NA DWE PODOBLASTI, W ODNOJ IZ
KOTORYH IZBYTOÓNO OGRANIÓENIE \Gamma 0
i , A W DRUGOJ --- \Gamma 0
j . w DALXNEJ[EM
DLQ OBEIH OBLASTEJ STROITSQ KANONIÓESKOE PREDSTAWLENIE.
wO WTOROM SLUÓAE (p 0 = \Gamma1) POLUÓAEM SLOJ, W KOTOROM MOGUT RASPOí
LAGATXSQ CELOÓISLENNYE TOÓKI:
\Gamma(b 0
j1 n 1 + : : : + b 0
jk n k + c 0
j ) ß a 0
i1 n 1 + : : : + a 0
ik n k ß b 0
i1 n 1 + : : : + b 0
ik n k + c 0
i .
dLQ NEGO PROIZWODIM SLEDU@]IE PROWERKI:
1. pROWERKA NA PROTIWOREÓIWOSTX (RACIONALXNAQ PUSTOTA): ESLI
DLQ KAKOJíLIBO PARY PARALLELXNYH GIPERPLOSKOSTEJ \Gamma(b 0
j1 n 1 +
: : : + b 0
jk n k + c 0
j ) ? b 0
i1 n 1 + : : : + b 0
ik n k + c 0
i , TO OBLASTX QWLQETSQ
RACIONALXNO (A ZNAÓIT I CELOÓISLENNO) PUSTOJ, PO``TOMU PROTIí
WOPOLOVNOE USLOWIE DOBAWLQETSQ K OGRANIÓENIQM PROSTRANSTWA
WNE[NIH PEREMENNYH.
2. pOISK PROTIWOPOLOVNYH NERAWENSTW, ZAMENA IH NA RAWENSTWA I
ISKL@ÓENIE PEREMENNYH IZ ``TIH RAWENSTW: ESLI \Gamma(b 0
j1 n 1 + : : : +
b 0
jk n k +c 0
j ) = b 0
i1 n 1 +: : :+b 0
ik n k +c 0
i , TO ZAMENQEM ``TI DWA NERAWENSTWA
NA RAWENSTWO a 0
i1 n 1 +: : :+a 0
ik n k = b 0
i1 n 1 +: : :+b 0
ik n k +c 0
i I PROIZWODIM
ISKL@ÓENIE PEREMENNOJ IZ DANNOGO RAWENSTWA.
3. nEOBHODIMOE USLOWIE CELOÓISLENNOJ NEPUSTOTY OBLASTI, W OPISAí
NIE KOTOROJ WHODQT PARY PARALLELXNYH GIPERPLOSKOSTEJ --- MEVí
DU TAKIMI GIPERPLOSKOSTQMI DOLVNA BYTX PO KRAJNEJ MERE ODNA

CELOÓISLENNAQ TOÓKA: DOLVNO 9s 2 Z :
\Gamma(b 0
j1 n 1 + : : : + b 0
jk n k + c 0
j ) ß s ß b 0
i1 n 1 + : : : + b 0
ik n k + c 0
i
I a 0
i1 n 1 + : : : + a 0
ik n k = s. wTOROE WERNO , s = rq, GDE r 2 Z, A q =
nod (a 0
i1 ; : : : ; a 0
ik ): pO``TOMU DOLVNO 9r 2 Z : \Gamma(b 0
j1
n 1 +:::+b 0
jk
n k +c 0
j
)
q
ß
r ß b 0
i1 n 1 +:::+b 0
ik
n k +c 0
i
q
. ---TIM DOBAWLQETSQ DOPOLNITELXNOE OGRANIÓEí
NIE NA WNE[NIE PEREMENNYE. dLQ PARALLELXNYH GIPERPLOSKOSTEJ
W PROSTRANSTWE WNE[NIH PEREMENNYH PROWERKA TAKOGO USLOWIQ ZAí
KL@ÓAETSQ TOLXKO W SRAWNENII SWOBODNYH ÓLENOW.
4. eSLI OBLASTX ZADANA PARAMI GIPERPLOSKOSTEJ, PARALLELXNYH OSQM
KOORDINAT, TO PREDYDU]EE USLOWIE STANOWITSQ NEOBHODIMYM I
DOSTATOÓNYM: POSKOLXKU L@BYE OGRANIÓENIQ IME@T WID \Gamma(b 0
j1 n 1 +
: : : + b 0
jk n k + c 0
j ) ß a 0
it i t ß b 0
i1 n 1 + : : : + b 0
ik n k + c 0
i , TO ESLI IZ KAVDOGO
TAKOGO DWOJNOGO NERAWENSTWA OPREDELIM PEREMENNU@ i t , TO POLUí
ÓIM CELOÓISLENNU@ TOÓKU PROSTRANSTWA ITERACIJ, UDOWLETWORQí
@]U@ WSEM OGRANIÓENIQM. dLQ PARALLELXNYH GIPERPLOSKOSTEJ W
PROSTRANSTWE WNE[NIH PEREMENNYH, KAK I W PREDYDU]EM PUNKTE,
DOSTATOÓNO PROIZWESTI SRAWNENIE SWOBODNYH ÓLENOW.
2.4 iSKL@ÓENIQ fURXEímOCKINA
pRQMOJ HOD METODA fURXEímOCKINA[4] POZWOLQET OPREDELITX RACIOí
NALXNU@ PUSTOTU ILI NEPUSTOTU ISHODNOJ OBLASTI. oDNAKO, ESLI DLQ
POSLEDNEJ ISKL@ÓAEMOJ PRI POMO]I ``TOGO METODA PEREMENNOJ CELOÓIí
SLENNOJ TOÓKI NET, TO MOVNO UTWERVDATX, ÓTO I WSQ OBLASTX CELOÓIí
SLENNO PUSTA, TO ESTX W TAKOM SLUÓAE ZADAÓA BUDET RE[ENA DO KONCA.
oDIN [AG ISKL@ÓENIJ fURXEímOCKINA SOSTOIT W SLEDU@]EM. sNAí
ÓALA WYBIRAETSQ PEREMENNAQ z, KOTORAQ BUDET ISKL@ÓATXSQ NA ``TOM
[AGE. eSLI WSE OGRANIÓENIQ NA z IME@T WID LIBO fi ß bz, LIBO az ß ff,
GDE a I b --- POLOVITELXNYE CELYE ÓISLA, TO PRI WYBORE DOSTATOÓNO
BOLX[OGO ILI, SOOTWETSTWENNO, DOSTATOÓNO MALENXKOGO ZNAÓENIQ PEREí
MENNOJ z MOVNO UDOWLETWORITX WSE TAKIE NERAWENSTWA. pO``TOMU WSE

NERAWENSTWA, SODERVA]IE ``TU PEREMENNU@, MOVNO UDALITX I DALX[E
NE RASSMATRIWATX. pUSTX TEPERX SU]ESTWU@T OGRANIÓENIQ KAK TOGO,
TAK I DRUGOGO TIPA. tOGDA DLQ KAVDOJ PARY OGRANIÓENIJ fi ß bz I
az ß ff SOSTAWIM DWOJNOE NERAWENSTWO afi ß abz ß bff. dLQ TOGO, ÓTOBY
SU]ESTWOWALA RACIONALXNAQ TOÓKA, UDOWLETWORQ@]AQ ``TOMU NERAWENí
STWU, NEOBHODIMO, ÓTOBY WYPOLNQLOSX USLOWIE afi ß bff. wYPOLNIW
TAKOE DEJSTWIE DLQ WSEH PAR OGRANIÓENIJ, POLUÓIM OPISANIE OBLASTI
W PROSTRANSTWE NA EDINICU MENX[EJ RAZMERNOSTI, KOTORAQ NAZYWAETSQ
real shadow.
eSLI NA KAKOMíLIBO [AGE ISKL@ÓENIJ POLUÓIM, ÓTO ODNO IZ OGRAí
NIÓENIJ SWERHU NA NEKOTORU@ PEREMENNU@ MENX[E KAKOGOíLIBO OGRANIí
ÓENIQ SNIZU NA TU VE PEREMENNU@, TO MOVNO UTWERVDATX, ÓTO OBLASTX
RACIONALXNO PUSTA. eSLI DLQ POSLEDNEJ ISKL@ÓAEMOJ PEREMENNOJ NE
POLUÓIM PROTIWOREÓIQ, TO MOVNO UTWERVDATX, ÓTO OBLASTX QWLQETSQ
RACIONALXNO NEPUSTOJ. eSLI MEVDU MAKSIMALXNYM IZ OGRANIÓENIJ
SNIZU I MINIMALXNYM IZ OGRANIÓENIJ SWERHU NA POSLEDN@@ ISKL@ÓAí
EMU@ PEREMENNU@ NET NI ODNOJ CELOÓISLENNOJ TOÓKI, TO MOVNO UTWERí
VDATX, ÓTO ISHODNAQ OBLASTX CELOÓISLENNO PUSTA. oBRATNOE, WOOB]E
GOWORQ, NE WERNO.
pOSLE ISKL@ÓENIQ WSEH PEREMENNYH PROSTRANSTWA ITERACIJ POLUí
ÓAETSQ DOPOLNITELXNYJ NABOR OGRANIÓENIJ NA WNE[NIE PEREMENNYE.
---TO PRIWODIT K SUVENI@ OBLASTI PROSTRANSTWA WNE[NIH PEREMENNYH.
w DALXNEJ[EM CELOÓISLENNU@ TOÓKU IMEET SMYSL ISKATX TOLXKO W POí
LUÓENNOJ OBLASTI.
2.5 iSKL@ÓENIQ oMEGAíTESTA
oMEGAíTEST POZWOLQET OPREDELITX CELOÓISLENNU@ NEPUSTOTU DLQ BOLXí
[OGO ÓISLA OBLASTEJ.
oDIN [AG ISKL@ÓENIJ oMEGAíTESTA SOSTOIT W SLEDU@]EM. sNAÓALA
WYBIRAETSQ PEREMENNAQ z, KOTORAQ BUDET ISKL@ÓATXSQ NA ``TOM [AGE.
eSLI WSE OGRANIÓENIQ NA z IME@T WID LIBO fi ß bz, LIBO az ß ff,
GDE a I b --- POLOVITELXNYE CELYE ÓISLA, TO PRI WYBORE DOSTATOÓNO
BOLX[OGO ILI, SOOTWETSTWENNO, DOSTATOÓNO MALENXKOGO ZNAÓENIQ PEREí

MENNOJ z MOVNO UDOWLETWORITX WSE TAKIE NERAWENSTWA. pO``TOMU WSE
NERAWENSTWA, SODERVA]IE ``TU PEREMENNU@, MOVNO UDALITX I DALX[E
NE RASSMATRIWATX. pUSTX TEPERX SU]ESTWU@T OGRANIÓENIQ KAK TOGO,
TAK I DRUGOGO TIPA. tOGDA DLQ KAVDOJ PARY OGRANIÓENIJ fi ß bz I
az ß ff SOSTAWIM DWOJNOE NERAWENSTWO afi ß abz ß bff.
oPREDELIM USLOWIE, PRI KOTOROM SU]ESTWUET CELOÓISLENNOE RE[Eí
NIE NERAWENSTWA afi ß bff, NO NE SU]ESTWUET CELOÓISLENNOGO RE[ENIQ
afi ß abz ß bff, TO ESTX MEVDU afi I bff NET CELYH ÓISEL, DELQ]IHSQ NA
ab. pUSTX i = bfi=bc. tOGDA
ab i ! afi ß bff ! ab(i + 1):
tAK KAK ab(i + 1) \Gamma bff ? 0 I WSE KO``FFICIENTY CELOÓISLENNYE )
ab(i + 1) \Gamma bff Ö 1 ) a(i + 1) \Gamma ff Ö 1=b )
a(i + 1) \Gamma ff Ö 1 ) ab(i + 1) \Gamma bff Ö b:
aNALOGIÓNO afi \Gamma abi Ö a. oTS@DA bff \Gamma afi ß ab \Gamma a \Gamma b: pO``TOMU ESLI WYí
POLNQETSQ OBRATNOE NERAWENSTWO bff \Gamma afi ? ab \Gamma a \Gamma b+1 = (a \Gamma 1)(b \Gamma 1),
TO SU]ESTWUET CELOÓISLENNOE RE[ENIE ISHODNOGO DWOJNOGO NERAWENí
STWA. oBLASTX W PROSTRANSTWE NA 1 MENX[EJ RAZMERNOSTI, OPREDELQEí
MAQ USLOWIQMI
bff \Gamma afi ? (a \Gamma 1)(b \Gamma 1)
DLQ KAVDOJ PARY NERAWENSTW fi ß bz I az ß ff, NAZYWAETSQ dark shadow.
eSLI DLQ WSEH OGRANIÓENIJ SNIZU b = 1 ILI DLQ WSEH OGRANIÓENIJ
SWERHU a = 1, TO dark shadow SOWPADAET S real shadow, POLUÓENIE KOTOí
ROJ OPISANO W PREDYDU]EM PUNKTE. w ``TOM SLUÓAE RACIONALXNAQ NEPUí
STOTA OBLASTI WLEÓèET ZA SOBOJ CELOÓISLENNU@ NEPUSTOTU. ~EM MENX[E
KO``FFICIENTY a I b, TEM BLIVE GRANICA dark shadow K GRANICE real
shadow, A ZNAÓIT, TEM BOLX[AQ ÓASTX OBLASTI BUDET ISÓERPANA PRI
PROWERKE oMEGAíTESTA. pO``TOMU DLQ ISKL@ÓENIQ WYBIRAETSQ W PERWU@
OÓEREDX PEREMENNAQ S WOZMOVNO MENX[IMI KO``FFICIENTAMI.
eSLI DLQ POSLEDNEJ ISKL@ÓAEMOJ PEREMENNOJ BUDET NAJDENO CELOí
ÓISLENNOE ZNAÓENIE, UDOWLETWORQ@]EE WSEM OGRANIÓENIQM, TO MOVNO

UTWERVDATX, ÓTO ISHODNAQ OBLASTX QWLQETSQ CELOÓISLENNO NEPUSTOJ, A
ZNAÓIT ZADAÓA BUDET RE[ENA DO KONCA.
iSKL@ÓIW TAKIM OBRAZOM WSE PEREMENNYE PROSTRANSTWA ITERACIJ,
POLUÓIM DOPOLNITELXNYJ NABOR OGRANIÓENIJ NA WNE[NIE PEREMENNYE.
oBLASTX W PROSTRANSTWE WNE[NIH PEREMENNYH PRI ``TOM RAZBIWAETSQ
NA DWE, W ODNOJ IZ KOTORYH (GDE UDOWLETWORQ@TSQ USLOWIQ, POLUÓENí
NYE W REZULXTATE RABOTY oMEGAíTESTA) OPREDELENO, ÓTO CELOÓISLENNAQ
TOÓKA ESTX I, SLEDOWATELXNO, OSTAETSQ TOLXKO POLUÓITX NEIZBYTOÓNOE
OPISANIE, A W DRUGOJ (ESLI ONA NE PUSTA) NUVNO PRODOLVATX POISK.
2.6 pEREBOR GIPERPLOSKOSTEJ
eSLI ISKL@ÓENIQMI oMEGAíTESTA NE POLUÓILI CELOÓISLENNOJ TOÓKI,
TO OSTAèETSQ PROWERITX TOLXKO TOÓKI MEVDU GRANICAMI dark shadow
I real shadow. wY[E POKAZANO, ÓTO ESLI SU]ESTWUET CELOÓISLENNAQ
TOÓKA, TO DOLVNO WYPOLNQTXSQ
ab \Gamma a \Gamma b + afi Ö bff Ö abz Ö afi:
oPREDELIM MAKSIMALXNYJ IZ KO``FFICIENTOW a W OGRANIÓENIQH SWERHU
NA z, I DLQ KAVDOGO OGRANIÓENIQ SNIZU bz Ö fi PROWERQEM, SU]ESTWUET
LI CELOÓISLENNAQ TOÓKA NA GIPERPLOSKOSTI bz = fi + i DLQ WSEH i TAKIH,
ÓTO (ab \Gamma a \Gamma b)=a Ö i Ö 0:
pEREBOR GIPERPLOSKOSTEJ, NAHODQ]IHSQ W OBYÓNO DOSTATOÓNO UZí
KOJ OBLASTI MEVDU GRANICAMI real shadow I dark shadow, POZWOLQí
ET RE[ITX ZADAÓU OPREDELENIQ CELOÓISLENNOJ PUSTOTY ILI NEPUSTOTY
DO KONCA. pRI ``TOM PEREBOR, PROIZWODIMYJ OPISANNYM WY[E SPOSOí
BOM, POZWOLQET MINIMIZIROWATX KOLIÓESTWO PEREBIRAEMYH GIPERPLOSí
KOSTEJ. ---TOT PROCESS MOVET BYTX WESXMA DOLGIM, NO, K SÓASTX@, ON
REDKO NEOBHODIM NA PRAKTIKE, PO``TOMU ON PROIZWODITSQ W POSLEDN@@
OÓEREDX. rE[ENIE ZADAÓI DLQ KAVDOJ TAKOJ GIPERPLOSKOSTI MOVET
PRIWESTI K NOWOMU RAZBIENI@ OBLASTI W PROSTRANSTWE WNE[NIH PEREí
MENNYH. pEREBOR ZAKANÓIWAETSQ, ESLI OKAZYWAETSQ ISÓERPANNOJ WSQ
OBLASTX \Delta N ILI ESLI BUDUT PEREBRANY WSE GIPERPLOSKOSTI.

2.7 pOLUÓENIE NEIZBYTOÓNOGO OPISANIQ
nA ``TAPE PROWERKI ``WRISTIK MY IZBAWILISX OT IZBYTOÓNYH GIPERPLOSí
KOSTEJ, PARALLELXNYH DRUGIM GIPERPLOSKOSTQM. tEPERX DLQ POLUÓENí
NYH OPISANIJ CELOÓISLENNO NEPUSTYH OBLASTEJ REALIZUEM OSNOWNOJ
ALGORITM POLUÓENIQ NEIZBYTOÓNOGO OPISANIQ. dLQ KAVDOJ GIPERPLOSí
KOSTI \Gamma = a 1 i 1 + : : : + a n i n ß b 1 n 1 + : : : + b k n k + c RASSMATRIWAEM GIí
PERPLOSKOSTX \Gamma 0 = a 1 i 1 + : : : + a n i n Ö b 1 n 1 + : : : + b k n k + c + 1, I ESLI
OBLASTX(\Omega I n \Gamma) `` \Gamma 0 CELOÓISLENNO PUSTA DLQ L@BYH ZNAÓENIJ WNE[NIH
PEREMENNYH, TO OGRANIÓENIE \Gamma QWLQETSQ IZBYTOÓNYM, I MY MOVEM EGO
OTBROSITX. eSLI VE ``TA OBLASTX CELOÓISLENNO PUSTA LI[X DLQ NEKOí
TORYH ZNAÓENIJ WNE[NIH PEREMENNYH, TO SOOTWETSTWU@]AQ OBLASTX W
PROSTRANSTWE WNE[NIH PEREMENNYH RAZBIWAETSQ NA DWE PODOBLASTI, W
ODNOJ IZ KOTORYH OGRANIÓENIE \Gamma IZBYTOÓNO, A W DRUGOJ SU]ESTWENNO.
2.8 gARANTIQ SOHRANNOSTI FORMY MNOGOGRANNIKOW
dLQ ZAWER[ENIQ KANONIZACII OPISANIQ POLUÓENNYH MNOGOGRANNIKOW
NUVNO GARANTIROWATX, ÓTO W KAVDOJ IZ POLUÓENNYH CELOÓISLENNO NEí
PUSTYH OBLASTEJ S NEIZBYTOÓNYM OPISANIEM NI ODNO REBRO NE STQGIí
WAETSQ W TOÓKU. ---TO OZNAÓAET, ÓTO NUVNO PROIZWESTI NOWOE PODRAZBIEí
NIE OBLASTI PROSTRANSTWA WNE[NIH PEREMENNYH TAKIM OBRAZOM, ÓTOBY
OPISANIE KAVDOJ POLUÓENNOJ PODOBLASTI BYLO KANONIÓESKIM.
uSLOWIE NESTQGIWANIQ REBER MNOGOGRANNIKA W TOÓKU ``KWIWALENTí
NO TOMU, ÓTO NIKAKIE DWE WER[INY NE DOLVNY SOWPASTX PRI IZMENEí
NII ZNAÓENIJ WNE[NIH PEREMENNYH. ---TO MOVNO PROWERITX SLEDU@]IM
OBRAZOM. dLQ POISKA WER[IN W PROSTRANSTWE ITERACIJ PEREBIRAEM WSE
NABORY IZ n OGRANIÓENIJ. eSLI SISTEMA, SOSTAWLENNAQ IZ ``TIH OGRAí
NIÓENIJ, SOWMESTNA, TO DLQ PRINADLEVNOSTI WER[INY MNOGOGRANNIKU
NEOBHODIMO, ÓTOBY ONA UDOWLETWORQLA WSEM OSTALXNYM OGRANIÓENIQM.
eSLI WER[INA UDOWLETWORQET ``TIM OGRANIÓENIQM TOLXKO DLQ NEKOTOí
ROJ PODOBLASTI W OBLASTI \Delta N PROSTRANSTWA WNE[NIH PEREMENNYH, TO
``TO PRIWODIT K DOPOLNITELXNOMU PODRAZBIENI@ OBLASTI \Delta N .

3 zAKL@ÓENIE
nA OSNOWANII OPISYWAEMYH METODOW W RAMKAH PROEKTA VíRay RAZRABOí
TAN KOMPLEKS PROGRAMM, KOTORYJ DLQ ZADANNOJ OBLASTI PROSTRANSTWA
ITERACIJ WYDAET SPISOK CELOÓISLENNO NEPUSTYH PODOBLASTEJ I, ESLI
TREBUETSQ, DLQ POLUÓENNYH OBLASTEJ STROITSQ NEIZBYTOÓNOE OPISAí
NIE. wAVNO OTMETITX, ÓTO OPISYWAEMYJ I REALIZOWANNYJ ALGORITM
POZWOLQET RE[ITX POSTAWLENNU@ ZADAÓU DO KONCA DLQ L@BOJ ISHODNOJ
OBLASTI. oDNAKO, KAK POKAZYWAET PRAKTIKA ANALIZA REALXNYH PROí
GRAMM, POÓTI WSE SLUÓAI RAZRE[A@TSQ DO KONCA UVE NA ``TAPE PROWERKI
``WRISTIK, I KRAJNE REDKO PRIHODITSQ PROIZWODITX PEREBOR GIPERPLOSí
KOSTEJ.
l I T E R A T U R A
[1] wOEWODIN. w. w. mATEMATIÓESKIE OSNOWY PARALLELXNYH WYÓISLEí
NIJ// m.: iZD. mOSK. UNíTA, 1991. 345S.
[2] wOEWODIN. wL. w. tEORIQ I PRAKTIKA ISSLEDOWANIQ PARALLELIZMA
POSLEDOWATELXNYH PROGRAMM// pROGRAMMIROWANIE. 1992. N ffi 3. C.
38í53.
[3] Pugh. W. A Practical Algorithm for Exact Array Dependence Analí
ysis// Communications of the ACM. August 1992. Vol. 35, N ffi 8. P.
102í114.
[4] Danzig G., Eaves. B. C. Fourierímotzkin elimination and its dual//
Journal of Combinatorial Theory. 1973. A(14). P. 288í297.