Полиномиальные инварианты линейных циклов
Розглянуто задачу генерації поліноміальних інваріантів спеціального типу ітераційних циклів з лінійним відображенням у тілі циклу. Запропоновано нову техніку побудови таких інваріантів, основану на аналізі характеристичних поліномів лінійних відображень. The problem of generating polynomial invarian...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45252 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Полиномиальные инварианты линейных циклов / М.С. Львов // Кибернетика и системный анализ. — 2010. — № 4. — С. 159-168. — Бібліогр.: 16 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859716683880464384 |
|---|---|
| author | Львов, М.С. |
| author_facet | Львов, М.С. |
| citation_txt | Полиномиальные инварианты линейных циклов / М.С. Львов // Кибернетика и системный анализ. — 2010. — № 4. — С. 159-168. — Бібліогр.: 16 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто задачу генерації поліноміальних інваріантів спеціального типу ітераційних циклів з лінійним відображенням у тілі циклу. Запропоновано нову техніку побудови таких інваріантів, основану на аналізі характеристичних поліномів лінійних відображень.
The problem of generating polynomial invariants of special type for an iterative loop with the linear mapping in an iteration body is considered. A technique is proposed to develop such invariants based on the analysis of characteristic polynomials of linear mappings.
|
| first_indexed | 2025-12-01T08:12:27Z |
| format | Article |
| fulltext |
ÓÄÊ 004.421.6
Ì.Ñ. ËÜÂÎÂ
ÏÎËÈÍÎÌÈÀËÜÍÛÅ ÈÍÂÀÐÈÀÍÒÛ ËÈÍÅÉÍÛÕ ÖÈÊËÎÂ
Êëþ÷åâûå ñëîâà: ñòàòè÷åñêèé àíàëèç ïðîãðàìì, ïîëèíîìèàëüíûå èíâàðèàíòû
öèêëîâ, çàäà÷à àâòîìàòè÷åñêîé ãåíåðàöèè.
ÂÂÅÄÅÍÈÅ
Ïðîáëåìà ïîèñêà èíâàðèàíòîâ öèêëîâ â èìïåðàòèâíûõ ïðîãðàììàõ ïîñòàâëåíà
â ðàáîòàõ Ð. Ôëîéäà [1] è Ñ. Õîàðà [2] êàê êëþ÷åâàÿ ïðîáëåìà ïðîöåññà àíàëèçà
ñâîéñòâ ïðîãðàìì. Îòìåòèì, ÷òî ñóùåñòâîâàíèå è ýôôåêòèâíîñòü àëãîðèòìîâ ãå-
íåðàöèè ïðîãðàììíûõ èíâàðèàíòîâ çàâèñÿò îò ïðåäìåòíîé îáëàñòè, ò.å. îò ñâîéñòâ
àëãåáð äàííûõ, ñ êîòîðûìè ðàáîòàåò ïðîãðàììà. Èññëåäîâàíèÿ çàäà÷è àâòîìàòè-
÷åñêîé ãåíåðàöèè ïðîãðàììíûõ èíâàðèàíòîâ äëÿ ðàçëè÷íûõ àëãåáð äàííûõ âûïîë-
íÿëèñü íà÷èíàÿ ñ 70-õ ãîäîâ â Èíñòèòóòå êèáåðíåòèêè; èõ îñíîâíûå ðåçóëüòàòû
ïðåäñòàâëåíû â [3, 4].
Íàèáîëåå âàæíûå ñ òî÷êè çðåíèÿ ïðàêòèêè — ÷èñëîâûå àëãåáðû äàííûõ.  ðà-
áîòå [5] èçëîæåíû äâà ìåòîäà ïîñòðîåíèÿ ïîëèíîìèàëüíûõ èíâàðèàíòîâ òèïà ðà-
âåíñòâ â ïðîãðàììàõ, àëãåáðîé äàííûõ êîòîðûõ ÿâëÿåòñÿ îáëàñòü öåëîñòíîñòè (ïî-
ëèíîìèàëüíî îïðåäåëåííûå ïðîãðàììû) èëè ïîëå (ðàöèîíàëüíî îïðåäåëåííûå ïðî-
ãðàììû). Îäèí èç íèõ çàêëþ÷àåòñÿ â ïîñòðîåíèè àëãåáðàè÷åñêèõ çàâèñèìîñòåé
ìåæäó ôóíêöèÿìè — ïðàâûìè ÷àñòÿìè îïåðàòîðà ïðèñâàèâàíèÿ â òåëå öèêëà; äðó-
ãîé — ìåòîä íåîïðåäåëåííûõ êîýôôèöèåíòîâ — ñòðîèò âñå èíâàðèàíòû äàííîãî
âèäà â ïðîèçâîëüíîé êîíòðîëüíîé òî÷êå ïðîãðàììû. Âèä èíâàðèàíòà çàäàåòñÿ
ïîëèíîìèàëüíîé ôîðìîé ñ íåîïðåäåëåííûìè êîýôôèöèåíòàìè. Ìåòîä îñíîâàí íà
ñâîéñòâå íåòåðîâîñòè êîëåö ïîëèíîìîâ ìíîãèõ ïåðåìåííûõ.
Ýòó èäåþ M. M��uller-Olm è H. Seidl èñïîëüçîâàëè â [6] ïðè ðåøåíèè çàäà÷è ïî-
ñòðîåíèÿ ïîëèíîìèàëüíûõ èíâàðèàíòîâ îãðàíè÷åííîé ñòåïåíè äëÿ ïîëèíîìèàëüíî
îïðåäåëåííûõ ïðîãðàìì. Ïðè ýòîì ó÷èòûâàþòñÿ ïðîãðàììíûå óñëîâèÿ òèïà
f X( ) � 0 , ãäå f X( ) — ìíîãî÷ëåíû îò ïåðåìåííûõ ïðîãðàììû. Òå æå àâòîðû [7]
ïðåäëîæèëè ìåòîä âû÷èñëåíèÿ ïîëèíîìèàëüíûõ ïðîãðàììíûõ èíâàðèàíòîâ îãðà-
íè÷åííîé ñòåïåíè â ëèíåéíî-îïðåäåëåííûõ (àôôèííûõ) ïðîãðàììàõ, ñîäåðæàùèõ
ðåêóðñèâíûå âûçîâû ïðîöåäóð.
 ðàáîòå [8] S. Sankaranarayanan, H. Sipma, Z. Manna ïðåäñòàâèëè ìåòîä âû-
÷èñëåíèÿ ïîëèíîìèàëüíûõ èíâàðèàíòîâ öèêëîâ â âèäå ïîëèíîìèàëüíûõ ôîðì
(template polynomlals) c èñïîëüçîâàíèåì àëãîðèòìà âû÷èñëåíèÿ áàçèñîâ Ãðåáíåðà.
M. Caplain [9] îïèñàë ìåòîä ïîñòðîåíèÿ íåëèíåéíûõ è, âîîáùå ãîâîðÿ, íåïîëèíî-
ìèàëüíûõ èíâàðèàíòíûõ ñîîòíîøåíèé äëÿ ëèíåéíûõ öèêëîâ. Ìåòîä èñïîëüçóåò
ñîáñòâåííûå çíà÷åíèÿ è ñîáñòâåííûå âåêòîðû ëèíåéíîãî îïåðàòîðà â òåëå öèêëà.
Àëãåáðàè÷åñêèå îñíîâû çàäà÷è ïîèñêà ïîëèíîìèàëüíûõ èíâàðèàíòîâ öèêëîâ
èçëîæèëè â [10] E. Rodriguez-Carbonell è D. Kapur. Îñíîâíîé ðåçóëüòàò ýòîé ðàáî-
òû — àëãîðèòì âû÷èñëåíèÿ âñåõ ïîëèíîìèàëüíûõ èíâàðèàíòîâ äëÿ öèêëîâ ñ òàê
íàçûâàåìûìè ðàçðåøèìûìè îïåðàòîðàìè ïðèñâàèâàíèÿ.  ÷àñòíîñòè, ðàçðåøèìû-
ìè ÿâëÿþòñÿ àôôèííûå îïåðàòîðû ñ ïîëîæèòåëüíûìè âåùåñòâåííûìè ñîáñòâåííû-
ìè çíà÷åíèÿìè. Ýòè æå àâòîðû â [11] ïðåäëîæèëè ìåòîä ãåíåðàöèè ïîëèíîìèàëü-
íûõ èíâàðèàíòîâ öèêëîâ, âêëþ÷àÿ âëîæåííûå öèêëû, à òàêæå ïðîãðàììíûå
óñëîâèÿ êàê â âèäå ïîëèíîìèàëüíûõ ðàâåíñòâ, òàê è íåðàâåíñòâ. Â ñòàòüå ðàññìàòðè-
âàåòñÿ áîëüøîå êîëè÷åñòâî ïðèìåðîâ; ïðèâîäÿòñÿ òàáëèöû âðåìåíè ðàáîòû àëãî-
ðèòìà â çàâèñèìîñòè îò òåõíè÷åñêèõ ïàðàìåòðîâ àíàëèçèðóåìûõ ïðîãðàìì.
 ðàáîòå [12] L. Kov�cs, T. Jebelean ïðåäëîæèëè àëãîðèòì ïîèñêà èíâàðèàíòîâ
öèêëîâ, îñíîâàííûé íà ïîñòðîåíèè ñèñòåìû ðåêóððåíòíûõ ñîîòíîøåíèé îò ïåðå-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 159
© Ì.Ñ. Ëüâîâ, 2010
ìåííûõ öèêëà è ïàðàìåòðà n — ÷èñëà ïîâòîðåíèé öèêëà. Àëãîðèòì èùåò ðåøåíèå
ýòîé ñèñòåìû, çàâèñÿùåå îò n. Îí ðåàëèçîâàí â ïðîãðàììíîé ñèñòåìå Òåîðåìà
(Theorema System); åãî ðàáîòà ïîäðîáíî èëëþñòðèðîâàíà ïðèìåðàìè.
L-ÈÍÂÀÐÈÀÍÒÛ ËÈÍÅÉÍÛÕ ÎÒÎÁÐÀÆÅÍÈÉ È ÈÍÂÀÐÈÀÍÒÛ ËÈÍÅÉÍÛÕ ÖÈÊËÎÂ
Îïðåäåëåíèå 1. Ïóñòü W — n-ìåðíîå âåêòîðíîå ïðîñòðàíñòâî íàä ïîëåì ðàöè-
îíàëüíûõ ÷èñåë Q è Q — àëãåáðàè÷åñêîå çàìûêàíèå ïîëÿ Q. Îáîçíà÷èì
X x xn� ( , , )1 � n-ìåðíûé âåêòîð ïåðåìåííûõ. Ðàöèîíàëüíàÿ ôóíêöèÿ p X Q X( ) ( )�
íàçûâàåòñÿ L-èíâàðèàíòîì ëèíåéíîãî îïåðàòîðà A W W: � , åñëè äëÿ ëþáîãî âåê-
òîðà b W� èìååò ìåñòî ñîîòíîøåíèå
p Ab p b( ) ( )� . (1)
Ïðèìåð 1 (ëèíåéíûé îïåðàòîð ñ õàðàêòåðèñòè÷åñêèì ìíîãî÷ëåíîì x3 2� ).
Ðàññìîòðèì ëèíåéíûé îïåðàòîð ñ ìàòðèöåé
A X x y z�
�
�
�
�
�
�
�
0 1 0
0 0 1
2 0 0
, ( , , ) .
Ïîêàæåì, ÷òî ðàöèîíàëüíîå âûðàæåíèå
p x y z
x y z x y z
x y z
( , , )
( )( )
( )
�
� � � �
� �
1
2
1 3
2
3
2
2
2
2
, (2)
ãäå � � � � �1
3
2
3
3
3 22 2 2� � �, , , à �
� �
� �
�
�
�
�
�
�
�cos sin
2
3
2
3
i — ïåðâîîáðàçíûé
êîðåíü ñòåïåíè 3 èç 1 — L-èíâàðèàíò ýòîãî îïåðàòîðà:
p A x y z
y z x y z x
y z
T( ( , , ) )
( )( )
(
�
� � � �
� �
1
2
1 3
2
3
2
2
2
2 2
2x)2
�
�
�
� � � � � �
� � �
1 1 1
2
3 3 3
2
2
2
2 2
2 2
( ) ( )
( )
y z x y z x
y z x
�
�
� �
�
� � � �
� �
�
1 3
2
2
1
2
1 3
2
3
2
2
2
2
1
2( )( )
( )
(x y z x y z
x y z
x y z x y z
x y z
� � �
� �
1 3
2
3
2
2
2
2
)( )
( )
.
Îïðåäåëåíèå 2. Ïóñòü X x xn� ( , , )1 � , b b bn� ( , , )1 � — äâà íàáîðà ïåðåìåí-
íûõ. Ëèíåéíûì öèêëîì íàçîâåì ôðàãìåíò èìïåðàòèâíîé ïðîãðàììû âèäà
X := b;
While Q(X, b) do X := A*X
Çàìå÷àíèå. Îïåðàòîðû X:=b, X:=A*X èíòåðïðåòèðóþòñÿ êàê îäíîâðåìåí-
íûå ïðèñâîåíèÿ ïåðåìåííûì ëåâûõ ÷àñòåé çíà÷åíèé ïðàâûõ ÷àñòåé.  äàëüíåéøåì
óñëîâèå Q(X, b) áóäåì èãíîðèðîâàòü, ñ÷èòàÿ ëèíåéíûé öèêë áåñêîíå÷íûì, à åãî
âûïîëíåíèå íåäåòåðìèíèðîâàííûì. Òàêèì îáðàçîì, ðàññìàòðèâàþòñÿ öèêëû âèäà
X := b;
While True|False do X := A*X
Ïðåäëîæåíèå 1. Åñëè p X
r X
q X
( )
( )
( )
� — L-èíâàðèàíò ëèíåéíîãî îïåðàòîðà A,
ìíîãî÷ëåí r X q b q X r b( ) ( ) ( ) ( )� — èíâàðèàíò ëèíåéíîãî öèêëà íàä ïîëåì Q . Òàêèå
èíâàðèàíòû öèêëîâ áóäåì òàêæå íàçûâàòü L-èíâàðèàíòàìè (ëèíåéíûõ öèêëîâ).
160 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
Ïðèìåð 2 (ëèíåéíûé öèêë ñ îïåðàòîðîì ïðèìåðà 1). Ëèíåéíûé öèêë, ñîîòâå-
òñòâóþùèé îïåðàòîðó A, èìååò âèä
(x, y, z) := (a, b, c);
While True|False do (x, y, z) := (y, z, 2*x)
L-èíâàðèàíò ýòîãî öèêëà îïðåäåëåí ôîðìóëîé (2):
P x y z a b c x y z x y z a b c( , , , , , ) ( )( )(�
� � � � � �
1
2
1 3
2
3 2
2
2 )2 �
�
( ) ( )( )� � � � � �
2
2
2
2
1
2
1 3
2
3x y z a b c a b c . (3)
Îòìåòèì, ÷òî L-èíâàðèàíò öèêëà P x y z a b c( , , , , , ) îïðåäåëåí íàä ïîëåì
Q ( , , )� � �1 2 3 . Îäíàêî åìó ñîîòâåòñòâóåò íàáîð L-èíâàðèàíòîâ ñ êîýôôèöèåíòàìè
èç ïîëÿ Q, êîòîðûå ìîæíî ïîñòðîèòü, ïðèâåäÿ (3) ê êàíîíè÷åñêîìó âèäó — ìíîãî-
÷ëåíó îò � � �1 2 3, , , çàòåì — ê ìíîãî÷ëåíó îò � 2 , èñïîëüçóÿ ñîîòíîøåíèå
� � �1 3 2
2� è ñîîòíîøåíèÿ Âèåòà. Ïðîäåìîíñòðèðóåì òåõíèêó âû÷èñëåíèÿ
L-èíâàðèàíòîâ íàä ïîëåì Q.
Ââåäåì îáîçíà÷åíèÿ:
r x y z x y z x y z( , , ) ( )( )�
� � � �
1
2
1 3
2
3 , q x y z x y z( , , ) ( )�
� �
2
2
2
2 .
Ìíîãî÷ëåíû r q, îïðåäåëåíû íàä ïîëåì Q( )� 2 . Âû÷èñëèâ r x y z q x y z( , , ), ( , , )
â âèäå ìíîãî÷ëåíîâ îò � 2 , ïîëó÷èì
r x y z r x y z r x y z r x y z( , , ) ( , , ) ( , , ) ( , , ) ,�
0 1 2 2 2
2� �
q x y z q x y z q x y z q x y z( , , ) ( , , ) ( , , ) ( , , )�
0 1 2 2 2
2� � ,
ãäå
r x y z z xy0
2 2( , , ) � � , r x y z x yz1
22( , , ) � � , r x y z y xz2
2( , , ) .� � ,
q x y z z xy0
2 4( , , ) �
, q x y z x yz1
2( , , ) �
, q x y z y xz2
2 2( , , ) .�
Äðîáü
r x y z
q x y z
( , , )
( , , )
ïðåäñòàâèìà â âèäå ìíîãî÷ëåíà îò � 2 ñ êîýôôèöèåíòàìè èç
Q x y z( , , ) :
r x y z
q x y z
r x y z r x y z r x y z( , , )
( , , )
( , , ) ( , , ) ( , , )
�
0 1 2 2 2
� �2
0 1 2 2 2
2 2 2
2
q x y z q x y z q x y z
U V W
( , , ) ( , , ) ( , , )
�
� �
� � ,
U V W Q x y z, , ( , , )� ; (4)
Âûðàæåíèå U x y z V x y z W x y z( , , ), ( , , ), ( , , ) ìîæíî âû÷èñëèòü ìåòîäîì íåîïðåäåëåííûõ
êîýôôèöèåíòîâ, èñïîëüçóÿ ðàâåíñòâî (4). Çàìåòèì, ÷òî U x y z V x y z W x y z( , , ), ( , , ), ( , , ) —
L-èíâàðèàíòû îïåðàòîðà A. Â ñàìîì äåëå,
p x y z p a b c U x y z U a b c V x y z V( , , ) ( , , ) ( ( , , ) ( , , )) ( ( , , ) (� � �
� a b c, , ))� 2
�( ( , , ) ( , , )) .W x y z W a b c �
2
2
Ïîñêîëüêó p b c a p a b c( , , ) ( , , )2 0
� , èìååì
( ( , , ) ( , , )) ( ( , , ) ( , , )) ( ( ,U b c a U a b c V b c a V a b c W b c2 2 2�
�
� , ) ( , , ))2 0
2
2a W a b c� �� .
Ââèäó ëèíåéíîé íåçàâèñèìîñòè âåêòîðîâ 1 2 2
2, ,� � íàä Q
U b c a U a b c( , , ) ( , , )2 0� � , V b c a V a b c( , , ) ( , , )2 0� � , W b c a W a b c( , , ) ( , , )2 0� � ,
ò.å U x y z( , , ) , V x y z( , , ) , W x y z( , , ) — L-èíâàðèàíòû íàä Q.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 161
Îòìåòèì, ÷òî åñëè ïåðåìåííûì a b c, , ïðèäàòü ÷èñëîâûå çíà÷åíèÿ, L-èíâàðèàíò
ïðåîáðàçóåòñÿ â èíâàðèàíò öèêëà.
Ìåòîä ïîñòðîåíèÿ L-èíâàðèàíòîâ çàêëþ÷àåòñÿ â âû÷èñëåíèè è àíàëèçå ñîá-
ñòâåííûõ çíà÷åíèé è ñîáñòâåííûõ âåêòîðîâ ëèíåéíûõ îïåðàòîðîâ.
Ïðåäëîæåíèå 2. Ïóñòü � �1 , ,� m — ñîáñòâåííûå çíà÷åíèÿ ëèíåéíîãî îïåðà-
òîðà A è s sm1 , ,� — ñîîòâåòñòâóþùèå èì ñîáñòâåííûå âåêòîðû ñîïðÿæåííîãî
îïåðàòîðà A * . Ïðåäïîëîæèì, ÷òî ñóùåñòâóþò òàêèå öåëûå ÷èñëà k km1 , ,� , ÷òî
� �
1
1 1
k
m
km� � �� . (5)
Òîãäà
p X s X s X
k
m
km( ) ( , ) ( , )� � �1
1 � (6)
— L-èíâàðèàíò ëèíåéíîãî îïåðàòîðà A.
Äîêàçàòåëüñòâî. Ïóñòü � �
1
1 1
k
m
km� � �� . Òîãäà
( , ) ( , ) ( , ) ... ( , ) ( ,*s AX s AX s A X s A X A s
k
m
k k
m
km m
1 1 1
1 1� � � �� X A s X
k
m
km) ... ( , )*1 �
� �( , ) ... ( , ) ( , ) ... ( ,� � � �1 1 1 1
1 1 1s X s X s X s X
k
m m
k k
m
k k
m
m m� )
km �
� ( , ) ... ( , ) .s X s X
k
m
km
1
1
Ñîîòíîøåíèå (5) íàçîâåì ìóëüòèïëèêàòèâíûì ñîîòíîøåíèåì (ìåæäó êîðíÿìè
õàðàêòåðèñòè÷åñêîãî ìíîãî÷ëåíà), îïðåäåëÿþùèì L-èíâàðèàíò (6).
Ïðèìåð 3 (ïðîäîëæåíèå ïðèìåðà 2). Ðàññìîòðèì ìåòîä ïðåäëîæåíèÿ 2 ïðèìå-
íèòåëüíî ê ïðèìåðó 2. Âû÷èñëèì ñîáñòâåííûå ÷èñëà îïåðàòîðà A:
A h A E�
�
�
�
�
�
�
� � �
�
�
�
� �
0 1 0
0 0 1
2 0 0
1 0
0 1
2 0
3, ( ) | |� �
�
�
�
�
2.
Òàêèì îáðàçîì, õàðàêòåðèñòè÷åñêèé ìíîãî÷ëåí èìååò âèä h x x( ) � �3 2 . Åãî êîð-
íè — � � � � �1
3
2
3
3
3 22 2 2� � �, , , �
� �
� �
�
�
�
�
�
�
�cos sin
2
3
2
3
i (� — ïåðâîîáðàç-
íûé êîðåíü ñòåïåíè 3 èç 1).
Âû÷èñëèì äàëåå ñîáñòâåííûå âåêòîðû ìàòðèöû A * �
�
�
�
�
�
�
0 0 2
1 0 0
0 1 0
. Ðåøèì ñèñòå-
ìó îäíîðîäíûõ ëèíåéíûõ óðàâíåíèé ( )*A E
x
y
z
�
�
�
�
�
�
�
�� 0 , ïðè÷åì âû÷èñëåíèÿ áóäåì
îñóùåñòâëÿòü â ïîëå Q( )� ïî ìîäóëþ �3 2� . Ïîëó÷èì ñèñòåìó ëèíåéíûõ óðàâíå-
íèé
�
�
�
x z
x y
y z
� �
� �
� �
�
�
�
�
�
2 0
0
0
,
,
,
ðàíã êîòîðîé ðàâåí 2. Ôóíäàìåíòàëüíîå ðåøåíèå ýòîé ñèñòåìû —
âåêòîð s � ( , , )� �2 1 . Ñîáñòâåííûìè âåêòîðàìè îïåðàòîðà A * ÿâëÿþòñÿ
s s s1 1
2
1 2 2
2
2 3 3
2
31 1 1� � �( , , ), ( , , ), ( , , )� � � � � � .
Ëåãêî óñòàíîâèòü, ÷òî
� �
�
1 3
2
2
1� . Ïîýòîìó îïåðàòîð A èìååò L-èíâàðèàíò, îïðå-
äåëåííûé ðàâåíñòâîì (2).
162 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
Ñëåäñòâèå 1. Åñëè õàðàêòåðèñòè÷åñêèé (ìèíèìàëüíûé) ìíîãî÷ëåí h x( ) ëèíåé-
íîãî îïåðàòîðà A èìååò ñâîáîäíûé ÷ëåí, ðàâíûé �1 (ò.å. det( )A � �1), ëèíåéíûé
îïåðàòîð A îáëàäàåò L-èíâàðèàíòîì.
Äîêàçàòåëüñòâî. Ïóñòü c — ñâîáîäíûé ÷ëåí ìíîãî÷ëåíà h x( ). Òîãäà
c m� � �� � �1 2 1� . Ïîýòîìó ëèáî ( , ) ( , )s X s Xm1 � �� , ëèáî (( , ) ( , )) —s X s Xm1
2� ��
L-èíâàðèàíò îïåðàòîðà A. Îòìåòèì, ÷òî êîýôôèöèåíòû ýòîãî ïîëèíîìà ïðèíàäëå-
æàò Q, ïîñêîëüêó îíè ñèììåòðè÷íû îòíîñèòåëüíî ïåðåñòàíîâîê êîðíåé � �1 , ,� m .
Ïðèìåð 4. Öèêë ïîâîðîòà òî÷êè ïëîñêîñòè ( , )a b íà óãîë arctan
4
3
�
�
�
� :
(x,y) := (a,b);
While True|False do (x, y):= (4/5*x - 3/5*y, 3/5*x + 4/5*y)
Âû÷èñëèì ñîáñòâåííûå çíà÷åíèÿ è ñîáñòâåííûå âåêòîðû îïåðàòîðà A * :
A h A E�
��
�
�
�� � � �
� �4 5 3 5
3 5 4 5
4 5 3 5
3 5 4
/ /
/ /
, ( ) | |
/ /
/ /
� �
�
5
8
5
12
�
� �
�
� � ,
� �1 2
4
5
3
5
4
5
3
5
� � �
i i, , s i s i1 21 1� � �( , ), ( , ).
Ïîñêîëüêó � �1 2 1� , L-èíâàðèàíò îïåðàòîðà A èìååò âèä
p x y ix y ix y x y( , ) ( )( )�
�
�
2 2 .
Åìó ñîîòâåòñòâóåò èíâàðèàíò öèêëà x y a b2 2 2 2
� � .
Ïðèìåð 5. Öèêë âû÷èñëåíèÿ ïîñëåäîâàòåëüíîñòè Ôèáîíà÷÷è, íà÷èíàÿ ñ ïàðû
( , )a b , èìååò âèä
(x,y) := (a,b);
While True|False do (x, y):= (x + y, x)
Âû÷èñëèì ñîáñòâåííûå çíà÷åíèÿ è ñîáñòâåííûå âåêòîðû îïåðàòîðà A * :
A h A E�
�
�
�
�� � � �
�
�
� � �
1 1
1 0
1 1
1
12, ( ) | |� �
�
�
� � ,
� �1 2
1
2
1
2
5
1
2
1
2
5� � �
, ,
s s1 1 2 21
1
2
1
2
5 1 1
1
2
1
2
5 1� � ��
�
�
� � �
�
�
�
�( , ) , , ( , ) ,� � .
Ïîñêîëüêó � �1 2 1� � , L-èíâàðèàíò îïåðàòîðà A èìååò âèä
p x y x y x y x xy y( , ) (( )( )) ( )�
� � �� �1 2
2 2 2 2 .
Èíâàðèàíòíîå ñîîòíîøåíèå öèêëà: ( ) ( )x xy y a ab b2 2 2 2 2 2� � � � � .
Ñëåäñòâèå 2. Åñëè õàðàêòåðèñòè÷åñêèé (ìèíèìàëüíûé) ìíîãî÷ëåí h X( ) ëèíåé-
íîãî îïåðàòîðà A èìååò âèä x am � , ëèíåéíûé îïåðàòîð îáëàäàåò L-èíâàðèàíòàìè.
Äîêàçàòåëüñòâî. Êîðíè � i õàðàêòåðèñòè÷åñêîãî ìíîãî÷ëåíà x am � îïðåäåëåíû
ôîðìóëîé � �i
m ia� , ãäå � — ïåðâîîáðàçíûé êîðåíü ñòåïåíè m èç 1. Ëåãêî âèäåòü, ÷òî
åñëè k km1 , ,� — öåëûå ÷èñëà òàêèå, ÷òî k km1 0
�� , òî � �
1
1k
m
km� �� — íåêîòî-
ðàÿ ñòåïåíü �. Â ñàìîì äåëå,
� � � � � � �
1
2 01 1 2k
m
k m k k k mk m K Km i ma a� � � � � � � �� �( ) ( ) ,
ãäå K iki� � . Ïîýòîìó ïðîèçâåäåíèå � �
1
1k
m
km� �� â ïîäõîäÿùåé ñòåïåíè ðàâíî 1.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 163
Èòàê, L-èíâàðèàíòû îïåðàòîðà A ñóùåñòâóþò è âû÷èñëÿþòñÿ àíàëîãè÷íî
òîìó, êàê ýòî ñäåëàíî â ïðèìåðå 3.  ÷àñòíîñòè, L-èíâàðèàíòàìè îïåðàòîðà A ÿâëÿ-
þòñÿ ðàöèîíàëüíûå âûðàæåíèÿ
p X
s X
s X
i mi
i
Ki
( )
( , )
( , )
, , ,�
�
�
�
�� �
1
2 � ,
ãäå si — ñîáñòâåííûå âåêòîðû A * , à K i — íàèìåíüøèå íàòóðàëüíûå ÷èñëà òà-
êèå, ÷òî iK i êðàòíî m: K i mi � im div gcd( ( , )) .
ÑÂÎÉÑÒÂÀ L-ÈÍÂÀÐÈÀÍÒÎÂ ËÈÍÅÉÍÛÕ ÎÒÎÁÐÀÆÅÍÈÉ
Ðàññìîòðèì íåêîòîðûå ñâîéñòâà L-èíâàðèàíòîâ ëèíåéíûõ îòîáðàæåíèé.
Ïðåäëîæåíèå 3. Ïóñòü h x( ) — ìíîãî÷ëåí îò ïåðåìåííîé x ñ ðàöèîíàëüíûìè
êîýôôèöèåíòàìè è � � ( , , )� �1 � m — âñå åãî êîðíè èç àëãåáðàè÷åñêîãî çàìûêà-
íèÿ Q ïîëÿ Q. Ðàññìîòðèì ìíîæåñòâî G h x x
k
m
k k
m
km m( ) :� � � � � �{ }
1 1
1 1 1� �� � — ìíî-
æåñòâî ìîíîìîâ èç ïîëÿ ðàöèîíàëüíûõ âûðàæåíèé Q X( ) (âîçìîæíî, ñ îòðèöàòåëü-
íûìè ñòåïåíÿìè), êîòîðûå ïðè ïîäñòàíîâêå � i âìåñòî xi ïîëó÷àþò çíà÷åíèå 1.
Òîãäà G h( ) — ìóëüòèïëèêàòèâíàÿ àáåëåâà ãðóïïà ñ êîíå÷íûì ÷èñëîì îáðàçóþùèõ.
Äîêàçàòåëüñòâî. Êàæäîìó ìîíîìó M X x x
k
m
km( ) � � �
1
1 � ïîñòàâèì â ñîîòâå-
òñòâèå áèíîì êîëüöà Q X[ ] B X x x x x
i
k
il
k
j
k
jl
k
i il jl jl( ) � � � � � �
1 1
1 � � ñëåäóþùèì îáðàçîì:
ìîíîì M X( ) ïðåäñòàâèì â âèäå äðîáè
r X
q X
( )
( )
, â ÷èñëèòåëå êîòîðîé çàïèøåì ñòåïåíè
ïåðåìåííûõ ñ ïîëîæèòåëüíûìè ïîêàçàòåëÿìè, à â çíàìåíàòåëå — ñòåïåíè ïåðåìåííûõ
ñ îòðèöàòåëüíûìè ïîêàçàòåëÿìè, âçÿòûìè ñî çíàêîì «ìèíóñ»: B X r X q X( ) ( ) ( )� � .
Ãðóïïà G h( ) , î÷åâèäíî, ìîæåò áûòü çàäàíà è ìíîæåñòâîì îïðåäåëåííûõ âûøå
áèíîìîâ: G h r X q X r q( ) ( ) ( )| ( ) ( )� � � �{ }� � 0 . Âî ìíîæåñòâå áèíîìîâ G h( ) ìîæíî
âûäåëèòü êîíå÷íîå ïîäìíîæåñòâî GB , êîòîðîå îáðàçóåò áàçèñ èäåàëà êîëüöà Q X[ ] ,
ïîðîæäåííîãî ìíîæåñòâîì G h( ) : I G I G hB( ) ( ( ))� . Ïîñòðîèì áàçèñ Ãðåáíåðà ýòîãî
èäåàëà, îïèðàÿñü íà áàçèñ GB . Ëåãêî âèäåòü, ÷òî S-ïîëèíîì ïàðû áèíîìîâ òàêæå
ÿâëÿåòñÿ áèíîìîì. Êðîìå òîãî, ðåäóêöèÿ áèíîìà çàêëþ÷àåòñÿ â çàìåíå r X( ) íà
q X( ) . Ïîýòîìó ïðîöåññ ïîñòðîåíèÿ áàçèñà Ãðåáíåðà ïðèâîäèò ê êîíå÷íîìó ìíî-
æåñòâó áèíîìîâ, êîòîðîå îáîçíà÷èì G hGr ( ). Êàæäûé ýëåìåíò G hGr ( ) , â ñâîþ î÷å-
ðåäü, îïðåäåëÿåò ìîíîì ðàññìàòðèâàåìîãî âèäà. Îáîçíà÷èì ìíîæåñòâî òàêèõ ìî-
íîìîâ M hGr ( ). Îñòàëîñü ïîêàçàòü, ÷òî M hGr ( ) îáðàçóåò ìíîæåñòâî, ïîðîæäàþùåå
ãðóïïó G h( ) .
Ïóñòü
r X
q X
G h
( )
( )
( )� , r X q X( ) ( )� . Îáîçíà÷èì r q r q i ki i i i� �, , , ,� �1 , áèíîìû
èç G hGr ( ) — ýëåìåíòû áàçèñà Ãðåáíåðà. (Îáîçíà÷åíèÿ ïåðåìåííûõ â ôîðìóëàõ
îïóñêàåì.) Ïîñêîëüêó G hGr ( ) — áàçèñ Ãðåáíåðà, áèíîì r q� ðåäóöèðóåòñÿ ê íóëþ
«èñ÷åðïûâàíèåì» ñ ïîìîùüþ ýëåìåíòîâ G hGr ( ) . Ýòî îçíà÷àåò, ÷òî íà êàæäîì øàãå
ðåäóöèðîâàíèÿ ñóùåñòâóåò òàêîé íîìåð i áàçèñíîãî ýëåìåíòà, ÷òî r sri� . Øàã ðåäó-
öèðîâàíèÿ èñ÷åðïûâàíèåì ñîñòîèò â ïðåîáðàçîâàíèè sr q sq qi i� � � . Ýòîìó ïðåîá-
ðàçîâàíèþ ïîñòàâèì â ñîîòâåòñòâèå ñëåäóþùåå ïðåîáðàçîâàíèå ìîíîìà — ýëåìåí-
òà G h( ) :
r
q
r s
q
r
q
q s
q
i i
i
i� � .
Òàêèì îáðàçîì, øàã ðåäóöèðîâàíèÿ ïðèìåíèòåëüíî ê ýëåìåíòàì G h( ) ñîñòîèò
â âûäåëåíèè â ìîíîìå rq�1 ñîìíîæèòåëÿ r qi i
�1. Ðåäóöèðîâàííûé áèíîì, åñëè ýòî
íåîáõîäèìî, ñëåäóåò ïåðåóïîðÿäî÷èòü òàê, ÷òîáû ïåðâûé åãî ìîíîì áûë áîëüøå
âòîðîãî. Ïðåîáðàçîâàíèå ñîñòîèò â ñëåäóþùåì: r q q r� � � . Ïîíÿòíî, ÷òî ïîñëå
ýòîãî â ìîíîìå rq�1 âûäåëÿþòñÿ ñîìíîæèòåëè çíàìåíàòåëÿ: r q r qi i i i
� � ��1 1 1( ) .
164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
Èòàê, ïîêàçàíî, ÷òî ïðîöåññ ðåäóöèðîâàíèÿ èñ÷åðïûâàíèåì ñîîòâåòñòâóåò ïðîöåñ-
ñó ðàçëîæåíèÿ ìîíîìà rq�1 â ïðîèçâåäåíèå áàçèñíûõ ìîíîìîâ (âîçìîæíî,
ñ îòðèöàòåëüíûìè ïîêàçàòåëÿìè).
Òåîðåìà äîêàçàíà.
Ïðèìåð 6 (ïðîäîëæåíèå ïðèìåðà 3). Ëåãêî âèäåòü, ÷òî äëÿ ìíîãî÷ëåíà
h x x( ) � �3 2 èìåþò ìåñòî ñëåäóþùèå ìóëüòèïëèêàòèâíûå ñîîòíîøåíèÿ ìåæäó åãî
êîðíÿìè:
� � � � � � � � � � �
1
2
2 3 1 2 3
2
1 3 2
2
2
3
3
3� � � �, , , .
Ýòèì ñîîòíîøåíèÿì ñîîòâåòñòâóþò áèíîìû
x x x x x x x x x x x
1
2
2 3 1 2 3
2
1 3 2
2
2
3
3
3� � � �, , , ,
êîòîðûå îáðàçóþò áàçèñ Ãðåáíåðà èäåàëà I G I G hB( ) ( ( ))� .
Ñëåäñòâèå 3. Ïóñòü h x( ) — ìíîãî÷ëåí îò ïåðåìåííîé x ñ ðàöèîíàëüíûìè êî-
ýôôèöèåíòàìè è � � ( , , )� �1 � m — âñå åãî êîðíè èç àëãåáðàè÷åñêîãî çàìûêàíèÿ
Q ïîëÿ Q. Ðàññìîòðèì ìíîæåñòâî G h x x QQ
k
m
k k
m
km m( ) :� � � � � �{ }
1 1
1 1� �� � — ìíîæåñ-
òâî ìîíîìîâ èç ïîëÿ ðàöèîíàëüíûõ âûðàæåíèé Q X( ) (âîçìîæíî, ñ îòðèöàòåëüíû-
ìè ñòåïåíÿìè), êîòîðûå ïðè ïîäñòàíîâêå � i âìåñòî xi ïîëó÷àþò ðàöèîíàëüíûå çíà-
÷åíèÿ. Òîãäà G hQ ( ) — ìóëüòèïëèêàòèâíàÿ àáåëåâà ãðóïïà ñ êîíå÷íûì ÷èñëîì
îáðàçóþùèõ.
Äîêàçàòåëüñòâî, ïî ñóòè, ïîâòîðÿåò äîêàçàòåëüñòâî ïðåäëîæåíèÿ 3. Âìåñòî áèíî-
ìîâ âèäà r X q X( ) ( )� ñëåäóåò ðàññìàòðèâàòü áèíîìû âèäà r X cq X( ) ( ),� c Q� . Áîëåå
òîãî, âìåñòî ïîëÿ Q ìîæíî ðàññìàòðèâàòü ëþáóþ ìóëüòèïëèêàòèâíóþ ïîäãðóïïó
R Q� .
Ñëåäñòâèå 4. Ìíîæåñòâî âñåõ L-èíâàðèàíòîâ îïåðàòîðà A îáðàçóåò ïîëå ðà-
öèîíàëüíûõ âûðàæåíèé.
Äîêàçàòåëüñòâî î÷åâèäíî. Ïîëå L-èíâàðèàíòîâ îïåðàòîðà A, ïîðîæäåííîå
ýëåìåíòàìè G h( ) , èìååò êîíå÷íîå ÷èñëî îáðàçóþùèõ — ýëåìåíòîâ M hGr ( ) .
Ïðîáëåìó îïèñàíèÿ âñåõ L-èíâàðèàíòîâ ëèíåéíîãî îïåðàòîðà ìîæíî òåïåðü óòî÷-
íèòü êàê ïðîáëåìó ïîñòðîåíèÿ êîíå÷íîãî ìíîæåñòâà îáðàçóþùèõ ãðóïïû G h( ) .
Ïðåäëîæåíèå 4. Ïóñòü p x( ) — íåïðèâîäèìûé íàä ïîëåì Q ïðèâåäåííûé ìíî-
ãî÷ëåí è { }� � �1 2, , ,� m — ìíîæåñòâî åãî êîðíåé íàä ïîëåì Q . Åñëè ìåæäó åãî
êîðíÿìè ñóùåñòâóåò íåòðèâèàëüíîå ìóëüòèïëèêàòèâíîå ñîîòíîøåíèå � �
1
1 1
k
m
km� �
ñ öåëûìè ïîêàçàòåëÿìè k km1 , ,� , òî ñâîáîäíûé ÷ëåí am ìíîãî÷ëåíà f x( ) ðàâåí �1
ëèáî ki
i
m
�
� �
1
0.
Äîêàçàòåëüñòâî. Ïóñòü Q — ïîëå ðàöèîíàëüíûõ ÷èñåë, p x( ) — íåïðèâîäèìûé
ìíîãî÷ëåí íàä ïîëåì Q ñòåïåíè m, m � 1. Ïóñòü { }� � �1 2, ,... , m — ìíîæåñòâî âñåõ
êîðíåé ìíîãî÷ëåíà p x( ). Ïîëîæèì L Q m� ( , ,... , )� � �1 2 , r — ñòåïåíü ðàñøèðåíèÿ
ïîëÿ L íàä ïîëåì Q , r — ÷èñëî, êðàòíîå m.
1. Ãðóïïà Ãàëóà G ïîëÿ L íàä ïîëåì Q ÿâëÿåòñÿ òðàíçèòèâíîé ãðóïïîé ïîä-
ñòàíîâîê íà ìíîæåñòâå êîðíåé ìíîãî÷ëåíà p x( ) [15].
2. Ïóñòü H — ïîäãðóïïà ãðóïïû G, ñîñòîÿùàÿ èç âñåõ ýëåìåíòîâ ãðóïïû G,
êîòîðûå êîðåíü �1 ïåðåâîäÿò â ñåáÿ. Îáîçíà÷èì s ïîðÿäîê ïîäãðóïïû H è çàïèøåì
ðàçëîæåíèå ãðóïïû G íà ëåâûå ñìåæíûå êëàññû ïî ïîäãðóïïå
H G H g H g Hm: �
2 � . Ïóñòü w — ýëåìåíò ãðóïïû G, ïðèíàäëåæàùèé ñìåæíî-
ìó êëàññó g Hi . Òîãäà, ïî îïðåäåëåíèþ ëåâîãî ñìåæíîãî êëàññà, w g hi� , ãäå h —
íåêîòîðûé ýëåìåíò ïîäãðóïïû H. Îòñþäà ñëåäóåò, ÷òî h( )� �1 1� . Ïîýòîìó
w g h g h gi i i( ) ( ) ( ( )) ( )� � � �1 1 1 1� � � .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 165
Ïîñêîëüêó g Hi � , òî g i ( )� �1 1� . Òàê êàê ëþáàÿ ïîäñòàíîâêà g èç ãðóïïû Ãà-
ëóà G ïîëÿ L íàä ïîëåì Q ïåðåâîäèò êîðåíü �1 íåïðèâîäèìîãî ìíîãî÷ëåíà p x( )
â êîðåíü òîãî æå ìíîãî÷ëåíà, g i i( )� �1 � ; çäåñü � i — êîðåíü ìíîãî÷ëåíà p x( ) , îò-
ëè÷íûé îò �1, 1� �i m. Òîãäà, ïî äîêàçàííîìó, äëÿ ëþáîãî ýëåìåíòà w g Hi�
w g i i( ) ( )� � �1 1� � .
Ïðåäïîëîæèì, ÷òî ýëåìåíò u G� , ïðè÷åì u H� è u g Hi� . Êàê áûëî óñòàíîâëå-
íî âûøå, u( )� �1 1� .
Ïîêàæåì, ÷òî u i( )� �1 � . Ïðåäïîëîæèì ïðîòèâíîå: u i( )� �1 � . Òîãäà
g i i
� �1
1( )� � . Ïîýòîìó g u g u gi i i i
� � �� � �1
1
1
1
1
1( ) ( ( )) ( )� � � � . Îòñþäà ïîëó÷àåì,
÷òî g u Hi
� �1 , à çíà÷èò, u g Hi� . Ïî ïðåäïîëîæåíèþ u g Hi� . Ïîëó÷åííîå ïðîòèâî-
ðå÷èå äîêàçûâàåò, ÷òî u i( )� �1 � .
Ñëåäîâàòåëüíî, ýëåìåíòû ãðóïïû G, ïðèíàäëåæàùèå ðàçëè÷íûì ëåâûì ñìåæ-
íûì êëàññàì ïî ïîäãðóïïå H, ïåðåâîäÿò êîðåíü �1 ìíîãî÷ëåíà p x( ) â ðàçëè÷íûå
êîðíè òîãî æå ìíîãî÷ëåíà.  ñèëó òðàíçèòèâíîñòè ãðóïïû Ãàëóà ÷èñëî ëåâûõ
ñìåæíûõ êëàññîâ ãðóïïû G ïî ïîäãðóïïå G ðàâíî ÷èñëó êîðíåé ìíîãî÷ëåíà p x( ) ,
ò.å. ðàâíî m.
Ïîêàæåì, ÷òî ÷èñëî ýëåìåíòîâ â ëþáîì ñìåæíîì êëàññå ãðóïïû G ïî ïîäãðóï-
ïå H ðàâíî ïîðÿäêó ïîäãðóïïû H.
 ñàìîì äåëå, ïî îïðåäåëåíèþ g H g h h Hi i� �{ }| . Îòîáðàæåíèå �:h g hi�
áèåêòèâíî, ïîýòîìó | | | |g H H si � � . Òàêèì îáðàçîì, èç ðàññóæäåíèé, ïðèâåäåííûõ
âûøå, ñëåäóåò, ÷òî â ãðóïïå G ñóùåñòâóåò â òî÷íîñòè s ýëåìåíòîâ, êîòîðûå êîðåíü
�1 ïåðåâîäÿò â êîðåíü � i äëÿ ëþáîãî íîìåðà i , 1� �i m.
3. Ïîêàæåì, ÷òî ñïðàâåäëèâî ñîîòíîøåíèå g
g G
i
s
i
n
i
i
n
s
( )� � �1
1 1� � �
� � �� �
�
�
�
�
�
. Äåé-
ñòâèòåëüíî, èç ï. 2 ñëåäóåò, ÷òî g
g g H
i
s
i
( )� �1
�
� � , ïîýòîìó
g g
g G g g Hi
n
i
s
i
n
i
i
n
i
( ) ( )� � � �1 1
1 1 1� �� � �
� �� ��
�
�
�
�
�
� � �
�
�
�
�
�
s
.
Óòâåðæäåíèå ï. 3 äîêàçàíî.
4. Ïîêàæåì, ÷òî åñëèU — ïîäãðóïïà âñåõ ïîäñòàíîâîê, êîòîðûå îñòàâëÿþò íå-
ïîäâèæíûì êîðåíü � i , i � 1, òî U g Hgi i� �1. Ïîñêîëüêó ïî óñëîâèþ g i i( )� �1 � , òî
g i i
� �1
1( )� � . Ïîýòîìó äëÿ ëþáîãî ýëåìåíòà h H� èìååò ìåñòî ñîîòíîøåíèå
g hg g h g g h gi i i i i i i i i
� �� � � �1 1
1 1( ) ( ( ( ))) ( ( )) ( ) .� � � � �
Èòàê, ëþáîé ýëåìåíò èç ïîäãðóïïû g Hgi i
�1 ïåðåâîäèò êîðåíü � i â ñåáÿ. Èìå-
åì âêëþ÷åíèå g Hg Ui i
� �1 . Ïðåäïîëîæèì òåïåðü, ÷òî äëÿ ýëåìåíòà g G� ñïðàâåä-
ëèâî ðàâåíñòâî g i i( )� �� , ò.å. g U� . Òîãäà g g gi i i i
� �� �1 1
1( ( )) ( )� � � , èëè
g g gi i
� �1
1 1( ( ( )))� � . Òàêèì îáðàçîì, g gg h Hi i
� � �1 , à òîãäà g g hgi i� �1 . Ïîýòîìó
èìååò ìåñòî âêëþ÷åíèå U g Hgi i� �1. Ñëåäîâàòåëüíî, U g Hgi i� �1.
5. Ïîñêîëüêó ïîðÿäêè ñîïðÿæåííûõ ïîäãðóïï H è g Hgi i
�1 ðàâíû, â ñèëó ï. 3
g j i
s
i
n
g G
i
i
n
s
( ) .� � �� �
�
�
�
�
�
�� �
�� �
1 1
6. Åñëè �
i
k
i
n
i
�
� �
1
1 , òî g
i
k
i
n
g G
i
i
n
s k
i
i
� �
�� �
�� �
�
�
�
�
�
�
�
�
�
�
�
�
�
1 1
1.
166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
Òàê êàê g — àâòîìîðôèçì ïîëÿ L , èìååì
g g g
i
k
i
n
g G
i
k
i
n
g G
i i� �
�� ��
�� ��
�
�
�
�
�
�
�
�
�
�
�
�
1 1
( ) (�
i
k
g Gi
n
i )
��
��
�
�
�
�
�
�
1
�
�
�
�
�
�
�
�
�
�
�
�
�� ��
�� �( ( )) ( )g gi
k
g Gi
n
i
g G
k
i
i
i
� �
1 1
n
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�� ��
�� ��� � �j
s
j
n
k
i
n
j
j
n
sk
i
ni i
11 11
j
j
n
s ki
�
�
�
�
�
�
�
�
�
1
1.
7. Ïî ôîðìóëå Âèåòà � j
j
n
n
na
�
� � �
1
1( ) . Ïîýòîìó ñïðàâåäëèâî ñîîòíîøåíèå
( )� � �1 1n
n
s k
a i . Ñëåäîâàòåëüíî, an
s k ni� � �( )1 è | |an � 1; ïîñêîëüêó a Qn � , ëèáî
an � �1, ëèáî s k
i� � 0 . Òàê êàê s — íàòóðàëüíîå ÷èñëî, ki� � 0.
Îïðåäåëåíèå 3. L-èíâàðèàíòû îïåðàòîðà A, îïðåäåëåííûå ìóëüòèïëèêàòèâ-
íûì ñîîòíîøåíèåì ìåæäó êîðíÿìè õàðàêòåðèñòè÷åñêîãî ìíîãî÷ëåíà
� �1 1� � � �� m , íàçîâåì öåëûìè. L-èíâàðèàíòû îïåðàòîðà A, îïðåäåëåííûå ìóëü-
òèïëèêàòèâíûì ñîîòíîøåíèåì � �
1
1 1 0
k
m
k
i
m k� � � ��� , , — ðàöèîíàëüíûìè.
Ïðåäëîæåíèå 5. Åñëè õàðàêòåðèñòè÷åñêèé ìíîãî÷ëåí îïåðàòîðà A èìååò âèä
h x kk( ), � 1, îïåðàòîð A îáëàäàåò ðàöèîíàëüíûìè L-èíâàðèàíòàìè.
Äîêàçàòåëüñòâî. Ïóñòü � �1 , ,� l — êîðíè ìíîãî÷ëåíà h y( ) . Òîãäà h xk( ) �
� � �( )... ( )x xk k
l� �1 . Êàæäûé èç ñîìíîæèòåëåé âèäà xk
i� � îïðåäåëÿåò ðàöèî-
íàëüíûå L-èíâàðèàíòû, êîòîðûå âû÷èñëÿþòñÿ àíàëîãè÷íî òîìó, êàê ýòî ñäåëàíî
â ñëåäñòâèè 2 ïðåäëîæåíèÿ 2.
ÇÀÊËÞ×ÅÍÈÅ
Çàäà÷à èçó÷åíèÿ L-èíâàðèàíòîâ ëèíåéíûõ îïåðàòîðîâ â íàñòîÿùåé ñòàòüå íå çà-
âåðøåíà. Íàèáîëåå èíòåðåñíûìè è âàæíûìè ÿâëÿþòñÿ ñëåäóþùèå ïðîáëåìû.
1. Â ðàáîòå äàíî îáùåå îïðåäåëåíèå L-èíâàðèàíòà ëèíåéíîãî îïåðàòîðà è äî-
êàçàíî ïðåäëîæåíèå 2 — äîñòàòî÷íîå óñëîâèå ñóùåñòâîâàíèÿ L-èíâàðèàíòîâ. Âîç-
íèêàåò âîïðîñ: âñå ëè L-èíâàðèàíòû îïèñûâàþòñÿ ìóëüòèïëèêàòèâíûìè ñîîòíîøå-
íèÿìè (5) è ôîðìóëîé (6) ïðåäëîæåíèÿ 2? Èíûìè ñëîâàìè, ìîæíî ëè îáðàòèòü
ïðåäëîæåíèå 2?
2. Äëÿ îïåðàòîðîâ ñ íåïðèâîäèìûìè õàðàêòåðèñòè÷åñêèìè ìíîãî÷ëåíàìè âûäå-
ëåíû äâà êëàññà, äëÿ êîòîðûõ ñóùåñòâóþò L-èíâàðèàíòû. Ïåðâûé êëàññ îáðàçóþò
îïåðàòîðû, ñâîáîäíûå ÷ëåíû õàðàêòåðèñòè÷åñêèõ ìíîãî÷ëåíîâ êîòîðûõ ðàâíû �1.
L-èíâàðèàíòû öèêëîâ äëÿ òàêèõ îïåðàòîðîâ èìåþò âèä p X p b p X Q X( ) ( ), ( ) [ ]� � .
Ýòè èíâàðèàíòû íàçâàíû öåëûìè. Âòîðîé êëàññ îáðàçóþò îïåðàòîðû, õàðàêòåðèñ-
òè÷åñêèå ìíîãî÷ëåíû êîòîðûõ èìåþò âèä h x kk( ), � 1. L-èíâàðèàíòû öèêëîâ äëÿ
òàêèõ îïåðàòîðîâ èìåþò âèä p X p b p X Q X( ) ( ), ( ) ( )� � . Ýòè èíâàðèàíòû íàçâàíû
ðàöèîíàëüíûìè. Âîïðîñ: èñ÷åðïûâàþòñÿ ëè äàííûìè äâóìÿ êëàññàìè âñå ëèíåé-
íûå îïåðàòîðû, îáëàäàþùèå L-èíâàðèàíòàìè? Äðóãèìè ñëîâàìè, âñå ëè ðàöèî-
íàëüíûå L-èíâàðèàíòû ïðèíàäëåæàò âòîðîìó êëàññó?
3. Åñëè õàðàêòåðèñòè÷åñêèé ìíîãî÷ëåí h x( ) îïåðàòîðà A ïðèâîäèì íàä Q,
ìîæíî ïîñòðîèòü L-èíâàðèàíòû äëÿ êàæäîãî íåïðèâîäèìîãî äåëèòåëÿ h x( ). Êðîìå
òîãî, ìîæíî ñòðîèòü L-èíâàðèàíòû, îïèðàÿñü íà ìóëüòèïëèêàòèâíûå ñîîòíîøåíèÿ
ìåæäó ñâîáîäíûìè ÷ëåíàìè íåïðèâîäèìûõ äåëèòåëåé h x( ) . Èìåííî, åñëè
h x i li ( ), , ,� 1 � , — íåïðèâîäèìûå ïðèâåäåííûå äåëèòåëè h x( ) è ai — ñâîáîäíûå
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 167
÷ëåíû h xi ( ) , òî ëþáîå ñîîòíîøåíèå âèäà a a a
k k
l
kl
1 2
1 2 1� � �� îïðåäåëÿåò L-èíâàðè-
àíò. Ïîñêîëüêó ai — ðàöèîíàëüíûå ÷èñëà, çàäà÷à âû÷èñëåíèÿ k kl1 , ,� ñâîäèòñÿ
ê ðåøåíèþ ñèñòåìû îäíîðîäíûõ ëèíåéíûõ óðàâíåíèé îò íåèçâåñòíûõ k kl1 , ,�
â öåëûõ ÷èñëàõ. Âîïðîñ: âñå ëè L-èíâàðèàíòû îïåðàòîðà A áóäóò ïîñòðîåíû?
Èíûìè ñëîâàìè, êàê íàéòè ñèñòåìó îáðàçóþùèõ ãðóïïû G h( ) èç ïðåäëîæåíèÿ 3?
4. Â [5, 7] îïèñàí àëãîðèòì ïîñòðîåíèÿ áàçèñà âåêòîðíîãî ïðîñòðàíñòâà âñåõ
èíâàðèàíòîâ îãðàíè÷åííîé ñòåïåíè äëÿ ïðîèçâîëüíîãî öèêëà ñ ðàöèîíàëüíûì îòî-
áðàæåíèåì â òåëå öèêëà.  ñâÿçè ñ ýòèì àêòóàëüíîé ÿâëÿåòñÿ çàäà÷à îöåíêè ñòåïåíè
L-èíâàðèàíòîâ. Ðàññìîòðèì ëèíåéíûé öèêë âèäà
(x, y) := (a, b);
While True|False do (x,y) := (2*x, 2^n*y)
ãäå n — íàòóðàëüíîå ÷èñëî. Ìóëüòèïëèêàòèâíîå ñîîòíîøåíèå:
�
�
1
2
1
n
� . Òàêèì
îáðàçîì, L-èíâàðèàíò èìååò âèä
x
y
a
b
n n
� . Èç ýòîãî ñëåäóåò, ÷òî ñòåïåíü L-èíâà-
ðèàíòà çàâèñèò, âîîáùå ãîâîðÿ, íå òîëüêî îò ðàçìåðíîñòè îïåðàòîðà A, íî è îò
åãî êîýôôèöèåíòîâ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. F l o y d R . W . Assigning meanings to programs // Proc. of Symp. on Applied Mathematics /
J.T. Schwartz (Ed.); Amer. Math. Soc. — Providence: R.I., 1967. — 19. — P. 19–32.
2. H o a r e C . A . R . An axiomatic basis for computer programming // Comm. ACM. — 1969. — N 12(10).
— P. 576–580.
3. L e t i c h e v s k y A . A . About one approach to program analysis // Cybernetics. — 1979. — N 6. —
P. 1–8.
4. G o d l e v s k y A . B . , K a p i t o n o v a Y . V . , K r i v o y S . L . , L e t i c h e v s k y A . A . Iterative
methods of program analysis // Ibid. — 1989. — N 2. — P. 9–19.
5. L e t i c h e v s k y A . , L v o v M . Discovery of invariant equalities in programs over data fields // Appli-
cable Algebra in Engineering, Communication and Computing. — 1993. — N 4. — P. 21–29.
6. M ��ul l e r - O l m M . , S e i d l H . Precise interprocedural analysis through linear algebra // Proc. of Symp.
on Principles of Programming Languages (Venice, Italy, Jan. 14–16, 2004). — New York: ACM, 2004. —
P. 330–341.
7. L v o v M . About one algorithm of program polynomial invariants generation // Proc. Workshop on In-
variant Generation: (Techn. rep.) / Univ. of Linz; Eds. M. Giese, T. Jebelean. — N 07–07 (RISC Report
Series). — Linz (Austria), 2007. — P. 85–99 (electronic).
8. M ��ul l e r - O l m M . , S e i d l H . Computing polynomial program invariants // Inform. Process. Lett. —
2004. — 91, N 5. — P. 233–244.
9. S a n k a r a n a r a y a n a n S . , S i p m a H . , M a n n a Z . Non-linear loop invariant generation using
Gr��obner bases // Proc. of Symp. on Principles of Programming Languages (Venice, Italy, Jan. 14–16,
2004). — New York: ACM, 2004. — P. 318–329.
10. C a p l a i n M . Finding invariant assertions for proving programs // Proc. of the Intern. Conf. on Reliable
Software (Los Angeles, USA, Apr. 21–23, 1975). — New York: ACM, 1975. — P. 165–171.
11. R o d r i g u e z - C a r b o n e l l E . , K a p u r D . Automatic generation of polynomial loop invariants: alge-
braic foundations // Proc. of Intern. Symp. on Symbolic and Algebraic Computation (Santander, Spain,
July 4–7, 2004). — New York: ACM, 2004. — P. 266–273.
12. R o d r i g u e z - C a r b o n e l l E . , K a p u r D . Automatic generation of polynomial invariants of bounded
degree using abstract interpretation // Sci. Comput. Program. — 2007. — 64, N 1. — P. 54–75.
13. K o v � c s L . I . , J e b e l e a n T . An algorithm for automated generation of invariants for loops with
conditionals // Proc. of Intern. Symp. on Symbolic and Numeric Algorithms for Scientific Computing
(Timisoara, Romania, 25–29 Sept., 2005). — S.l.: IEEE Computer Soc., 2005. — P. 245–249.
14. Ê ó ð î ø À . Ã . Òåîðèÿ ãðóïï. — 3-å èçä. — Ì.: Íàóêà, 1967. — 648 c.
15. Ï î ñ ò í è ê î â Ì . Ì . Òåîðèÿ Ãàëóà. — Ì.: Ôèçìàòãèç, 1963. — 220 ñ.
16. Á ó õ á å ð ã å ð Á . Áàçèñû Ãðåáíåðà. Àëãîðèòìè÷åñêèé ìåòîä â òåîðèè ïîëèíîìèàëüíûõ èäåàëîâ //
Êîìïüþòåðíàÿ àëãåáðà. Ñèìâîëüíûå è àëãåáðàè÷åñêèå âû÷èñëåíèÿ / Ïåð. c àíãë. ïîä ðåä.
Á. Áóõáåðãåðà, Äæ. Êîëëèíçà, Ð. Ëîîñà. — Ì.: Ìèð, 1986. — C. 331–383.
Ïîñòóïèëà 21.04.2010
168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
New Table of Contents
ÏÎËÈÍÎÌÈÀËÜÍÛÅ ÈÍÂÀÐÈÀÍÒÛ ËÈÍÅÉÍÛÕ ÖÈÊËÎÂ
ÂÂÅÄÅÍÈÅ. ÎÁÇÎÐ ÐÀÁÎÒ
L-ÈÍÂÀÐÈÀÍÒÛ ËÈÍÅÉÍÛÕ ÎÒÎÁÐÀÆÅÍÈÉ È ÈÍÂÀÐÈÀÍÒÛ ËÈÍÅÉÍÛÕ ÖÈÊËÎÂ
Çàêëþ÷åíèå
|
| id | nasplib_isofts_kiev_ua-123456789-45252 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-01T08:12:27Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Львов, М.С. 2013-06-10T18:58:11Z 2013-06-10T18:58:11Z 2010 Полиномиальные инварианты линейных циклов / М.С. Львов // Кибернетика и системный анализ. — 2010. — № 4. — С. 159-168. — Бібліогр.: 16 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45252 004.421.6 Розглянуто задачу генерації поліноміальних інваріантів спеціального типу ітераційних циклів з лінійним відображенням у тілі циклу. Запропоновано нову техніку побудови таких інваріантів, основану на аналізі характеристичних поліномів лінійних відображень. The problem of generating polynomial invariants of special type for an iterative loop with the linear mapping in an iteration body is considered. A technique is proposed to develop such invariants based on the analysis of characteristic polynomials of linear mappings. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Программно-технические комплексы Полиномиальные инварианты линейных циклов Поліноміальні інваріанти лінійних циклів Polynomial invariants for linear loops Article published earlier |
| spellingShingle | Полиномиальные инварианты линейных циклов Львов, М.С. Программно-технические комплексы |
| title | Полиномиальные инварианты линейных циклов |
| title_alt | Поліноміальні інваріанти лінійних циклів Polynomial invariants for linear loops |
| title_full | Полиномиальные инварианты линейных циклов |
| title_fullStr | Полиномиальные инварианты линейных циклов |
| title_full_unstemmed | Полиномиальные инварианты линейных циклов |
| title_short | Полиномиальные инварианты линейных циклов |
| title_sort | полиномиальные инварианты линейных циклов |
| topic | Программно-технические комплексы |
| topic_facet | Программно-технические комплексы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45252 |
| work_keys_str_mv | AT lʹvovms polinomialʹnyeinvariantylineinyhciklov AT lʹvovms polínomíalʹníínvaríantilíníinihciklív AT lʹvovms polynomialinvariantsforlinearloops |