Алгоритм построения базиса множества решений систем линейных диофантовых уравнений в кольце целых чисел
Запропоновано поліноміальний алгоритм побудови мінімальної породжуючої множини (пред-базиса) і базиса множини всіх розв’язків системи лінійних діофантових рівнянь в кільці цілих чисел. Цей алгоритм грунтується на модифікованому TSS-методі. A polynomial algorithm is proposed to construct the minimal...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2009 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/44480 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритм построения базиса множества решений систем линейных диофантовых уравнений в кольце целых чисел / С.Л. Крывый // Кибернетика и системный анализ. — 2009. — № 6. — С. 36-41. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859516801597046784 |
|---|---|
| author | Крывый, С.Л. |
| author_facet | Крывый, С.Л. |
| citation_txt | Алгоритм построения базиса множества решений систем линейных диофантовых уравнений в кольце целых чисел / С.Л. Крывый // Кибернетика и системный анализ. — 2009. — № 6. — С. 36-41. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано поліноміальний алгоритм побудови мінімальної породжуючої множини (пред-базиса) і базиса множини всіх розв’язків системи лінійних діофантових рівнянь в кільці цілих чисел. Цей алгоритм грунтується на модифікованому TSS-методі.
A polynomial algorithm is proposed to construct the minimal generating set of solutions and the basis of the solution set for systems of linear Diophantine equations over the ring of integer numbers. The algorithm is based on the modified TSS-method.
|
| first_indexed | 2025-11-25T20:42:24Z |
| format | Article |
| fulltext |
ÓÄÊ 51.681.3
Ñ.Ë. ÊÐÛÂÛÉ
ÀËÃÎÐÈÒÌ ÏÎÑÒÐÎÅÍÈß ÁÀÇÈÑÀ ÌÍÎÆÅÑÒÂÀ ÐÅØÅÍÈÉ
ÑÈÑÒÅÌ ËÈÍÅÉÍÛÕ ÄÈÎÔÀÍÒÎÂÛÕ ÓÐÀÂÍÅÍÈÉ
 ÊÎËÜÖÅ ÖÅËÛÕ ×ÈÑÅË
Êëþ÷åâûå ñëîâà: êîëüöî öåëûõ ÷èñåë, ëèíåéíûå äèîôàíòîâûå óðàâíåíèÿ, ïðåä-
áàçèñ, áàçèñ ìíîæåñòâà ðåøåíèé.
Ëèíåéíûå äèîôàíòîâûå óðàâíåíèÿ è ñèñòåìû òàêèõ óðàâíåíèé ÷àñòî âñòðå÷àþò-
ñÿ â ðàçëè÷íûõ ïðèêëàäíûõ îáëàñòÿõ íàóêè î âû÷èñëåíèÿõ. Ê ðåøåíèþ òàêèõ
óðàâíåíèé è èõ ñèñòåì ñâîäÿòñÿ çàäà÷è ëèíåéíîãî öåëî÷èñëåííîãî ïðîãðàììèðî-
âàíèÿ, ðàñïîçíàâàíèÿ îáðàçîâ è ìàòåìàòè÷åñêèõ èãð [1, 2], êðèïòîãðàôèè [3],
óíèôèêàöèè [4], ðàñïàðàëëåëèâàíèÿ öèêëîâ [5] è ò.ä. Ïðè ýòîì ìíîæåñòâîì,
ê êîòîðîìó ïðèíàäëåæàò êîýôôèöèåíòû óðàâíåíèé, ÿâëÿåòñÿ ëèáî ìíîæåñòâî öå-
ëûõ ÷èñåë, ëèáî êîëüöî âû÷åòîâ, ëèáî ïîëå âû÷åòîâ ïî ìîäóëþ íåêîòîðîãî ÷èñ-
ëà, à ìíîæåñòâîì, â êîòîðîì èùóòñÿ ðåøåíèÿ, ÿâëÿåòñÿ ëèáî êîëüöî öåëûõ ÷è-
ñåë, ëèáî ìíîæåñòâî íàòóðàëüíûõ ÷èñåë, ëèáî êîíå÷íûå ïîëÿ è êîëüöà âû÷åòîâ.
Àëãîðèòìû ïîèñêà ðåøåíèé ñèñòåì ëèíåéíûõ äèîôàíòîâûõ óðàâíåíèé â ìíî-
æåñòâå íàòóðàëüíûõ ÷èñåë îïèñàíû âî ìíîãèõ ïóáëèêàöèÿõ [6–12].  íàñòîÿùåé
ñòàòüå ðàññìàòðèâàåòñÿ àëãîðèòì ðåøåíèÿ ñèñòåì ëèíåéíûõ äèîôàíòîâûõ óðàâ-
íåíèé â êîëüöå öåëûõ ÷èñåë.  îñíîâå ïðåäëàãàåìîãî àëãîðèòìà ëåæèò
TSS-ìåòîä, êîòîðûé ïðèìåíÿëñÿ äëÿ ïîñòðîåíèÿ ìèíèìàëüíîãî ïîðîæäàþùåãî
ìíîæåñòâà ðåøåíèé ñèñòåìû ëèíåéíûõ îäíîðîäíûõ äèîôàíòîâûõ óðàâíåíèé
â ìíîæåñòâå íàòóðàëüíûõ ÷èñåë [1].
1. ÏÐÅÄÂÀÐÈÒÅËÜÍÛÅ ÑÂÅÄÅÍÈß
Ñèñòåìîé ëèíåéíûõ äèîôàíòîâûõ óðàâíåíèé (ÑËÄÓ) â êîëüöå öåëûõ ÷èñåë Z
áóäåì íàçûâàòü ñèñòåìó âèäà
S
L x a x a x b
L x a x a x b
n n
n n
�
� � � �
� � � �
1 11 1 1 1
2 21 1 2
( ) ... ,
( ) ... 2
1 1
,
... ... ... ... ... ... ... ... ...
( ) ...L x a x a xq q qn n� � � �
�
�
�
�
�
�
� bq ,
(1)
ãäå a b x Z i n j qij i i, , , , , , , ,� � �1 1� � . Ðåøåíèåì ÑËÄÓ (1) íàçûâàåòñÿ òàêîé
âåêòîð c c c cn� ( , , , )1 2 � , êîòîðûé ïðè ïîäñòàíîâêå âìåñòî x
j
çíà÷åíèé c j â
L xi ( ) îáðàùàåò L c bi i( ) â òîæäåñòâî äëÿ âñåõ i q� 1 2, , ,� . ÑËÄÓ íàçûâàåòñÿ
îäíîðîäíîé (ÑËÎÄÓ), åñëè âñå bi ðàâíû íóëþ; â ïðîòèâíîì ñëó÷àå — íåîäíî-
ðîäíîé (ÑËÍÄÓ).
2. TSS-ÌÅÒÎÄ ÐÅØÅÍÈß ÑËÎÄÓ
Ðàññìîòðèì ÑËÎÄÓ S âèäà (1), e e en1 21 0 0 0 1 0 0 0 1� � �( , , , ), ( , , , ), , ( , , , )—� � � �
åäèíè÷íûå âåêòîðû, êîòîðûå íàçûâàþòñÿ âåêòîðàìè êàíîíè÷åñêîãî áàçèñà ìíî-
æåñòâà Z n .
Ïóñòü M — ìíîæåñòâî ðåøåíèé ñèñòåìû S . Ïîñêîëüêó îíà îäíîðîäíàÿ, òî íó-
ëåâîé âåêòîð âñåãäà ÿâëÿåòñÿ åå ðåøåíèåì è íàçûâàåòñÿ òðèâèàëüíûì, à âñÿêîå ðå-
øåíèå ñèñòåìû S , îòëè÷íîå îò íóëåâîãî, — íåòðèâèàëüíûì.
ÑËÎÄÓ S áóäåò íåñîâìåñòíà, åñëè ìíîæåñòâî M ñîñòîèò òîëüêî èç òðèâèàëü-
íîãî ðåøåíèÿ, â ïðîòèâíîì ñëó÷àå S ñîâìåñòíà.
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
Ñ.Ë. Êðûâûé, 2009
TSS-ìåòîä, î êîòîðîì ðå÷ü ïîéäåò äàëüøå, è åãî ðåàëèçàöèÿ äëÿ ñèñòåì óðàâ-
íåíèé íàä ìíîæåñòâîì íàòóðàëüíûõ ÷èñåë ïîäðîáíî îïèñàíû â [1]. Ðàññìîòðèì
ìîäèôèêàöèþ ýòîãî ìåòîäà äëÿ ñëó÷àÿ êîëüöà öåëûõ ÷èñåë Z.
Ñëó÷àé ëèíåéíîãî îäíîðîäíîãî äèîôàíòîâîãî óðàâíåíèÿ (ËÎÄÓ). Ïóñòü
äàíî ËÎÄÓ
L x a x a x a xi i n n( ) ,� � � � � �1 1 0� � (2)
ãäå a x Z i ni i, , , ,� � 1 � .
Ðàññìîòðèì ìíîæåñòâî âåêòîðîâ êàíîíè÷åñêîãî áàçèñà M e en0 1� { }, ,�
è ôóíêöèþ L x a x a x a xn n( ) � � � �1 1 2 2 � ËÎÄÓ (2). Íå îãðàíè÷èâàÿ îáùíîñòè,
ïðåäïîëîæèì, ÷òî â ôóíêöèè L x( ) ïåðâûì íåíóëåâûì êîýôôèöèåíòîì áóäåò a1 è
a1 0� . Ïîñòðîèì ìíîæåñòâî âåêòîðîâ
B e a a e a a� � � � �{ 1 2 1 2 3 10 0 0 0 0( , , , , ), ( , , , , , ),� �
e a a Mq q� � �
1 1 00 0 0( , , , , , )� } ,
ãäå M e L er r0 0� �{ }: ( ) , ïðè÷åì åñëè äëÿ íåêîòîðîãî ai � 0 íàèáîëüøèé îáùèé äå-
ëèòåëü (ÍÎÄ) (a ai , )1 1� , òî ñîêðàòèì êîîðäèíàòû òàêîãî âåêòîðà íà ýòîò ÍÎÄ.
Âûáðàííûé íåíóëåâîé êîýôôèöèåíò a1 íàçîâåì îñíîâíûì. Òàêèì îáðàçîì, ìîæíî
ñ÷èòàòü, ÷òî âñå âåêòîðû â ìíîæåñòâå B òàêîâû, ÷òî ai è a1 âçàèìíî ïðîñòû. Èíû-
ìè ñëîâàìè, ìíîæåñòâî B ñòðîèòñÿ ïóòåì êîìáèíèðîâàíèÿ ïåðâîãî íåíóëåâîãî êî-
ýôôèöèåíòà ñ îñòàëüíûìè íåíóëåâûìè êîýôôèöèåíòàìè, âçÿòûìè ñ ïðîòèâîïîëîæ-
íûìè çíàêàìè, è ïîïîëíåíèÿ âåêòîðàìè êàíîíè÷åñêîãî áàçèñà, êîòîðûå ñîîòâåò-
ñòâóþò íóëåâûì êîýôôèöèåíòàì ËÎÄÓ (2). Ïîñòðîåííîå òàêèì îáðàçîì ìíîæåñòâî
áóäåì íàçûâàòü TSS-ìíîæåñòâîì, èëè ïðåäáàçèñîì. Î÷åâèäíî, ÷òî âåêòîðû èç ìíî-
æåñòâà B âûñòóïàþò ðåøåíèÿìè ËÎÄÓ (2), à ñàìî ìíîæåñòâî B çàìêíóòî îòíîñè-
òåëüíî ñëîæåíèÿ, âû÷èòàíèÿ è óìíîæåíèÿ íà ýëåìåíò èç êîëüöà Z.
Ëåììà 1. Ïóñòü x c c cq� ( , , , )1 2 � — íåêîòîðîå ðåøåíèå ËÎÄÓ (2), òîãäà åñëè
x B� , òî x ïðåäñòàâëÿåòñÿ â âèäå íåîòðèöàòåëüíîé ëèíåéíîé êîìáèíàöèè âèäà
a x c e c e c eq q1 2 1 3 2 1� � � � �� ,
ãäå e B i qi � � �, , ,1 1� .
Äîêàçàòåëüñòâî. Åñëè x c c Mq� �( , , )1 � , òî âåêòîð
c e c e c e c a c a c a c a c aq q q q q2 1 3 2 1 2 2 3 3 2 1 1� � � � � � � ��� � �( , , , ) �
� � �( , , , ) ( , , , )c a c a c a a c c c a xq q1 1 2 1 1 1 1 2 1� �
â ñèëó òîãî, ÷òî x — ðåøåíèå ËÎÄÓ (2), ò.å. a c a c a c a cq q1 1 2 2 3 3� � � � �� .
Çàìåòèì, ÷òî åñëè íåêîòîðûé âåêòîð e j èç B ÿâëÿåòñÿ âåêòîðîì êàíîíè÷åñêîãî
áàçèñà è j-ÿ êîîðäèíàòà âåêòîðà x ðàâíà c j , òî â ïðåäñòàâëåíèè âåêòîðà x âåêòîð e j
âõîäèò ñ êîýôôèöèåíòîì a c j1 .
Ëåììà äîêàçàíà.
Èç ëåììû âûòåêàåò ïîëåçíîå ñëåäñòâèå.
Ñëåäñòâèå 1. Åñëè ñðåäè êîýôôèöèåíòîâ ËÎÄÓ èìååòñÿ õîòÿ áû îäèí êîýô-
ôèöèåíò, ðàâíûé 1, òî ìíîæåñòâî B — áàçèñ ìíîæåñòâà âñåõ ðåøåíèé ËÎÄÓ.
Äåéñòâèòåëüíî, åñëè a1 1� , òî ýëåìåíòû ìíîæåñòâà B èìåþò âèä
{e a e a e aq q1 2 2 3 11 0 0 0 1 0 0 0 0� � � � � ��( , , , , ), ( , , , , , ), ( , ,� � , , , )� 0 1 0}
M ,
ò.å. â ðàçëîæåíèè ïðîèçâîëüíîãî ðåøåíèÿ x ïî âåêòîðàì èç ìíîæåñòâà B îñíîâ-
íîé êîýôôèöèåíò ñîãëàñíî ëåììå 1 áóäåò ðàâíûì åäèíèöå. À ýòî è îçíà÷àåò,
÷òî ìíîæåñòâî B áóäåò áàçèñîì.
Ïðèìåð 1. Ïîñòðîèòü TSS ËÎÄÓ L x x y z u( ) � � � � � �3 2 01 � . Ïðåäáàçèñ, èëè
TSS ýòîãî ËÎÄÓ èìååò âèä
e e e e1 2 3 413 0 0 0 10 3 0 0 2 0 0 3 0� � � � � �( , , , , ), ( , , , , ), ( , , , , ), ( , , , , )�10 0 0 3 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 37
Ðåøåíèÿ ËÎÄÓ x x1 20 2 3 0 1 1 1 0 2 0� � �( , , , , ), ( , , , , ) èìåþò ïðåäñòàâëåíèÿ
3 2 3 3 21 1 2 4 2 1 3x e e e x e e� � � � �, . Åñëè â êà÷åñòâå îñíîâíîãî êîýôôèöèåíòà âû-
áðàòü a2 1� , òî áàçèñîì ìíîæåñòâà âñåõ ðåøåíèé äëÿ ËÎÄÓ áóäåò ìíîæåñòâî
B e e e� � � � � �{ 1 2 31 3 0 0 0 0110 0 0 2 010( , , , , ), ( , , , , ), ( , , , , ), e4 0 10 01� �( , , , , ) .}
 ýòîì áàçèñå âåêòîðû x1 è x2 èìåþò ïðåäñòàâëåíèå x e e1 2 43� � , x e e2 1 32� � .
Ñëó÷àé ñèñòåìû ëèíåéíûõ îäíîðîäíûõ äèîôàíòîâûõ óðàâíåíèé. Ðàññìîò-
ðèì òåïåðü ÑËÎÄÓ
S
L x a x a x
L x a x a x
n n
n n
�
� � � �
� � � �
1 11 1 1
2 21 1 2
0
0
( ) ... ,
( ) ... ,
... ... ... ... ... ... ... ... ...
( ) ...L x a x a xq q qn n� � � �1 1 0,
�
�
�
�
�
�
�
(3)
ãäå a x Z i q j nij i, , , , , , ,� � �1 1� � .
Ïîñòðîèì ïðåäáàçèñ B e e e
q1 1
1
2
1
1
1�
�
{ }, , ,� äëÿ ïåðâîãî óðàâíåíèÿ L x1 0( ) � è
âû÷èñëèì çíà÷åíèÿ L e bi i2
1( ) � , ãäå e B b Zi i
1
1� �, . Ñîñòàâèì óðàâíåíèå
b y b y b yi i q q1 1 1 1 0� � � � �� �� � (4)
è ïîñòðîèì äëÿ íåãî ïðåäáàçèñ � � �B s sq1 1 2{ }, ,� . Âåêòîðàì si èç �Bi ñîîòâåòñòâó-
þò âåêòîðû-ðåøåíèÿ B e e
q2 1
2
2
2�
�
{ }, ,� ÑËÎÄÓ L x L x1 20 0( ) ( )� � � .
Ëåììà 2. Ìíîæåñòâî âåêòîðîâ B2 ñîñòàâëÿåò ïðåäáàçèñ ÑËÎÄÓ L x1 0( ) � �
� �L x2 0( ) , ò.å. ëþáîå ðåøåíèå x ýòîé ÑËÎÄÓ èìååò ïðåäñòàâëåíèå mx l e� �1 1
2
�
... � � �
l eq q2 2
2 , ãäå e B l Z i qi i
2
2 1 2� � � �, , , ,� , m Z� .
Äîêàçàòåëüñòâî. Ïóñòü x — ïðîèçâîëüíîå ðåøåíèå ÑËÎÄÓ L x1 0( ) � �
� �L x2 0( ) . Ïîñêîëüêó x — ðåøåíèå L x1 0( ) � , òî â ñèëó ëåììû 1 x ìîæíî ïðåäñòà-
âèòü â âèäå
dx a e a eq q
� � � � �1 1
1
1 1
1
� ,
ãäå e B a Z i qi i
1
1 1 1� � � �, , , ,� . Òîãäà â ñèëó òîãî, ÷òî x — ðåøåíèå L x2 0( ) � ,
ïîëó÷àåì L dx a b a bq q2 1 1 1 1 0( ) � � � �� �� , ãäå b L e j qj j� � �2
1 1 1( ), , ,� . Ñëåäî-
âàòåëüíî, âåêòîð a a aq� �( , , )1 1� — ðåøåíèå ËÎÄÓ (4) è â ñèëó ëåììû 1 ïîëó-
÷àåì ka d s d sq q� � � � �1 1 2 2� , ãäå s B d Z i qi i� � � � �1 1 2, , , ,� , à k — îñíîâíîé
êîýôôèöèåíò ËÎÄÓ. Îòñþäà ñëåäóåò, ÷òî kdx d e d eq q
� � � � �1 1
2
2 2
2
� , ãäå e Bi
2
2� ,
i q� �1 2, ,� , m k d� � .
Ëåììà äîêàçàíà.
Ñ ïîìîùüþ ìàòåìàòè÷åñêîé èíäóêöèè è ëåìì 1 è 2 äîêàæåì ñïðàâåäëèâîñòü òåîðåìû.
Òåîðåìà 1. TSS ÑËÎÄÓ (2) B, ïîñòðîåííîå îïèñàííûì âûøå ñïîñîáîì, ÿâëÿ-
åòñÿ ïðåäáàçèñîì ìíîæåñòâà âñåõ ðåøåíèé ÑËÎÄÓ.
Ïðèìåð 2. Íàéäåì ïðåäáàçèñ äëÿ ÑËÎÄÓ
S
L x x x x x x
L x x x x x x
�
� � � � � �
� � � � �
1 1 2 3 4 5
2 1 2 3 4
3 2 0
2 3 0 2
( ) ,
( ) 5 0�
�
�
� .
Áàçèñ äëÿ ïåðâîãî óðàâíåíèÿ ïîñòðîåí â ïðèìåðå 1:
B e e e1 1
1
2
1
3
11 3 0 0 0 0110 0 0 2 01� � � � � �{ ( , , , , ), ( , , , , ), ( , , , , ), ( , , , , ) .0 0 10 01
4
1e � � }
Çíà÷åíèÿ L x2 ( ) íà ýòèõ âåêòîðàõ ðàâíû ñîîòâåòñòâåííî � � �7 3 7 1, , , . Ñîñòàâëÿåì
óðàâíåíèå � � � � �7 3 7 01 2 3 4y y y y è ñòðîèì ïðåäáàçèñ ìíîæåñòâà ðåøåíèé ËÎÄÓ:
� � � � � � �B s s s1 1 2 33 7 0 0 1010 10 0 7{ }( , , , ), ( , , , ), ( , , , ) .
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
Ýòèì âåêòîðàì ñîîòâåòñòâóþò TSS -âåêòîðû (ïðåäáàçèñ) èñõîäíîé ÑËÎÄÓ
B e e e2 1
2
2
2
3
23 2 7 0 0 11010 1 4 0� � � � � � � �{ ( , , , , ), ( , , , , ), ( , , , , ) .0 7 }
Åñëè ïðè ïîñòðîåíèè ïðåäáàçèñà óðàâíåíèÿ � � � � �7 3 7 01 2 3 4y y y y êîìáèíè-
ðîâàíèå âåñòè ïî ïîñëåäíåìó çíà÷åíèþ (ò.å. ïî –1), òî ïîëó÷àåì òàêîé áàçèñ ìíî-
æåñòâà âñåõ ðåøåíèé äàííîé ÑËÎÄÓ:
{e e e
1
2
2
2
3
214 0 0 7 0 210 3 0 5 01 7� � � � � �( , , , , ), ( , , , , ), ( , , , , )}.
Ïðèíèìàÿ âî âíèìàíèå ñëåäñòâèå 1, ðåçóëüòàò òåîðåìû 1 ìîæíî óñèëèòü ââå-
äåíèåì èçáûòî÷íîñòè â ïðåäáàçèñ íà îñíîâàíèè òîãî, ÷òî çíà÷åíèÿ êîýôôèöèåíòîâ
â óðàâíåíèè L x a x a x a xn n1 11 1 12 2 1 0( ) � � � � �� âçàèìíî ïðîñòû. Áëàãîäàðÿ ýòîìó
âñåãäà ìîæíî äîáèòüñÿ, ÷òîáû ñðåäè çíà÷åíèé L x1 ( ) áûëà åäèíèöà. Íå îãðàíè÷èâàÿ
îáùíîñòè, áóäåì ïðåäïîëàãàòü, ÷òî ÍÎÄ(a a a11 12 13, , ) = 1, ò.å. ïåðâûå òðè êîýôôè-
öèåíòà âçàèìíî ïðîñòû â L x1 ( ) . Òîãäà ñóùåñòâóþò ÷èñëà d d d1 2 3, , òàêèå, ÷òî íà
âåêòîðå y d d d� ( , , , , , )1 2 3 0 0� çíà÷åíèå L y1 1( ) � . Äîáèâøèñü ýòîãî, âû÷èñëèì çíà-
÷åíèÿ L x1 ( ) íà âåêòîðàõ êàíîíè÷åñêîãî áàçèñà. Ïîñòðîèì ïðåäáàçèñ B1, êîìáèíè-
ðóÿ âåêòîð y ñ îñòàëüíûìè âåêòîðàìè äëÿ ïîëó÷åíèÿ ïðåäáàçèñà. Çàìåòèì, ÷òî
âåêòîðû èç B1 èìåþò âèä
� � � � � � � �e a y e e a y e1 11 1 2 12 2, ,
(5)
� � � � � � � � � � � �e a y e e a y e e a y en n n3 13 3 4 14 4 1, , ,� ,
ãäå ei — âåêòîðû êàíîíè÷åñêîãî áàçèñà, aij — êîýôôèöèåíòû â óðàâíåíèè
L x1 0( ) � . Â êîîðäèíàòíîé ôîðìå âåêòîðû �ei èìåþò ñëåäóþùèé âèä:
� � � � � �e a d a d a d1 11 1 11 2 11 31 0 0( , , , , , ),�
� � � � � �e a d a d a d2 12 1 12 2 12 31 0 0( , , , , , ),�
� � � � � �e a d a d a d3 13 1 13 2 13 3 10 0( , , , , , ),�
� � � � �e a d a d a d4 14 1 14 2 14 3 1 0( , , , , , ),�
................................................................
� � � � �e a d a d a dn n n n( , , , , , ).1 1 1 2 1 3 0 1�
Èìååò ìåñòî òåîðåìà 2.
Òåîðåìà 2. TSS ËÎÄÓ (2) B1, ïîñòðîåííîå îïèñàííûì âûøå ñïîñîáîì, ÿâëÿ-
åòñÿ áàçèñîì ìíîæåñòâà âñåõ ðåøåíèé ýòîãî ËÎÄÓ.
Ñëîæíîñòü ïîñòðîåíèÿ áàçèñà ïðîïîðöèîíàëüíà âåëè÷èíå l3 , ãäå l — ìàêñè-
ìàëüíîå èç ÷èñåë m è n, n — ÷èñëî íåèçâåñòíûõ â ËÎÄÓ, à m — ìàêñèìàëüíàÿ äëè-
íà äâîè÷íîãî ïðåäñòàâëåíèÿ êîýôôèöèåíòîâ ËÎÄÓ.
Äîêàçàòåëüñòâî. Ïóñòü x c c cn� ( , , , )1 2 � — ðåøåíèå ËÎÄÓ L x1 0( ) � . Òîãäà
âåêòîð x èìååò ïðåäñòàâëåíèå
x c e c e c e c e c en n� � � � � � � � � � � �1 1 2 2 3 3 4 4 �
( [ ],� � � � � � �c a d c c a d c a d c a d c a dn n1 11 1 1 2 12 1 3 13 1 4 14 1 1 1�
[ ],� � � � � � �c a d c a d c c a d c a d c a dn n1 11 2 2 12 2 2 3 13 2 4 14 2 1 2�
[ ],� � � � � � �c a d c a d c a d c c a d c a d cn n1 11 3 2 12 3 3 13 3 3 4 14 3 1 3 4� , , )� cn �
� ( , , , , , )c c c c cn1 2 3 4 �
â ñèëó òîãî, ÷òî L x a c a c a cn n( ) � � � � �11 1 12 2 1 0� .
Ñëîæíîñòü äàííîãî àëãîðèòìà îïðåäåëÿåòñÿ ñëîæíîñòüþ ðàñøèðåííîãî àëãî-
ðèòìà Åâêëèäà, êîòîðûé âìåñòå ñ ÍÎÄ âû÷èñëÿåò è ëèíåéíóþ êîìáèíàöèþ, ïðåä-
ñòàâëÿþùóþ ýòîò ÍÎÄ. Èçâåñòíî (ñì. [3]), ÷òî ýòà ñëîæíîñòü âûðàæàåòñÿ âåëè÷è-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 39
íîé O m m( )log , ãäå m — äëèíà äâîè÷íîé çàïèñè ìàêñèìàëüíîãî èç êîýôôèöèåíòîâ
ËÎÄÓ. Ýòîò àëãîðèòì ïðèìåíÿåòñÿ íå áîëåå n ðàç è òîãäà èìååì îöåíêó
O mn m( )log . Ïîñòðîåíèå áàçèñà B1 òðåáóåò íå áîëüøå n3 îïåðàöèé. Ñëåäîâàòåëü-
íî, îáùàÿ îöåíêà âðåìåííîé ñëîæíîñòè àëãîðèòìà âûðàæàåòñÿ âåëè÷èíîé O l( )3 ,
ãäå l m n� max( , ) .
Òåîðåìà äîêàçàíà.
Èç ýòîé òåîðåìû âûòåêàåò òàêîå ñëåäñòâèå.
Ñëåäñòâèå 2. Âðåìåííàÿ ñëîæíîñòü ïîñòðîåíèÿ áàçèñà ìíîæåñòâî âñåõ ðåøå-
íèé ÑËÎÄÓ âèäà (3) ïðîïîðöèîíàëüíà âåëè÷èíå O ql( )3 , ãäå q — ÷èñëî óðàâíåíèé
ÑËÎÄÓ, à l m n� max( , ) .
Çàìåòèì, ÷òî ïåðâûå òðè âåêòîðà � � �e e e1 2 3, , â ïðåäñòàâëåíèè (5) ëèíåéíî çàâè-
ñèìû. Äåéñòâèòåëüíî, â ñèëó òîãî, ÷òî a d a d a d11 1 12 2 13 3 1� � � , èìååì
d e d e d e1 1 2 2 3 3 0� � � � � � ,
a èñïîëüçóÿ êîîðäèíàòíîå ïðåäñòàâëåíèå âåêòîðîâ, ïîëó÷àåì
d e d e d e a d d a d d a d d a d1 1 2 2 3 3 12 1 2 13 1 3 11 1 2 11 3� � � � � � � � �( , , , , , )0 0� �
� � � � �( , , , , )a d d a d d a d d a d d12 1 2 11 1 2 13 2 3 2 312 0 0�
� � � � �( , , , , )a d d a d d a d d a d d13 1 3 13 2 3 11 1 3 12 2 3 0 0 0� .
Òàêèì îáðàçîì, îäèí èç âåêòîðîâ � � �e e e1 2 3, , ìîæíî óäàëèòü èç áàçèñà ðåøåíèé.
3. TSS-ÌÅÒÎÄ ÐÅØÅÍÈß ÑËÍÄÓ
Ïóñòü S — ÑËÍÄÓ âèäà (1) è bq � 0 . Âûïîëíÿÿ ýëèìèíàöèþ ñâîáîäíûõ ÷ëåíîâ
â ïåðâûõ q �1 óðàâíåíèÿõ, ïðåîáðàçóåì èñõîäíóþ ÑËÍÄÓ ê âèäó
S
L x a x a x
L x a x a
n n
� �
� � � � � � �
� � � � � �
1 11 1 1
2 21 1
0( ) ... ,
( ) ... 2
1 11
0n n
q q
x
L x a x
�
� � �� �
,
... ... ... ... ... ... ... ... ...
( ) 1 1
1 1
0� � � �
� � � � � � �
�
�
�
��
�... ,
( ) ... .
a x
L x a x a x b
q n n
q q qn n q�
�
�
�
(6)
Ïîñòðîèì áàçèñ ìíîæåñòâà ðåøåíèé ÑËÎÄÓ, ñîñòîÿùåé èç q �1ïåðâûõ óðàâ-
íåíèé ñèñòåìû (6). Ïóñòü ýòî áóäóò âåêòîðû { }s sk1 , ,� . Íàéäåì çíà÷åíèÿ
L s a j kq j j( ) , , ,� � 1 � , äëÿ êîòîðûõ âåðíà ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 3. ÑËÍÄÓ âèäà (6) (à âìåñòå ñ íåé è ÑËÍÄÓ (1)) ñîâìåñòíà òîãäà è
òîëüêî òîãäà, êîãäà ËÍÄÓ a y a y a y bk k q1 1 2 2� � � �� èìååò õîòÿ áû îäíî ðåøå-
íèå â ìíîæåñòâå öåëûõ ÷èñåë.
Äîêàçàòåëüñòâî. Åñëè óðàâíåíèå a y a y a y bk k q1 1 2 2� � � �� èìååò ðåøåíèå
( , , , )c c ck1 2 � , òî î÷åâèäíî, ÷òî âåêòîð s c s c s c sk k� � � �1 1 2 2 � — ðåøåíèå
ÑËÍÄÓ.
Åñëè ÑËÍÄÓ ñîâìåñòíà è s k k kn� ( , , , )1 2 � — åå ðåøåíèå, òî ïðåäñòàâèì s â
âèäå ëèíåéíîé êîìáèíàöèè ÷åðåç áàçèñíûå âåêòîðû ïîäñèñòåìû, ñîñòîÿùåé èç
ïåðâûõ q �1îäíîðîäíûõ óðàâíåíèé ñèñòåìû (6), ò.å. s c s c s c sk k� � � �1 1 2 2 � . Òîã-
äà L s c a c a c s bq k k q( ) � � � � �1 1 2 2 � äîëæíî èìåòü õîäÿ áû îäíî ðåøåíèå, ïî-
ñêîëüêó s — ðåøåíèå ÑËÍÄÓ.
Òåîðåìà äîêàçàíà.
Èçâåñòíî, ÷òî îáùåå ðåøåíèå ÑËÍÄÓ èìååò âèä y x a xi
i
k
i� �
�
�
1
, ãäå x — ÷àñò-
íîå ðåøåíèå ÑËÍÄÓ, xi — áàçèñíûå ðåøåíèÿ ñîîòâåòñòâóþùåé ÑËÎÄÓ, ai — ïðîèç-
âîëüíûå öåëûå ÷èñëà, à k — êîëè÷åñòâî áàçèñíûõ ðåøåíèé. Òàêèì îáðàçîì, äëÿ ïîë-
íîãî ðåøåíèÿ ÑËÍÄÓ íåîáõîäèìî ïîñòðîèòü áàçèñ ìíîæåñòâà ðåøåíèé åå ÑËÎÄÓ
40 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
è íàéòè îäíî èç ðåøåíèé ÑËÍÄÓ. Ïîèñê òàêîãî ðåøåíèÿ, êàê ñëåäóåò èç èçëîæåííîãî
âûøå, ñâîäèòñÿ ê ïîèñêó ðåøåíèÿ óðàâíåíèÿ a y a y a y bk k q1 1 2 2� � � �� . Ýòî ðåøå-
íèå ìîæíî íàéòè, íàïðèìåð, ìåòîäîì íàèìåíüøåãî êîýôôèöèåíòà.
Ïðèìåð 3. Ïðîâåðèòü íà ñîâìåñòíîñòü ÑËÍÄÓ
S
L x x x x x x
L x x x x x x
�
� � � � � �
� � � � �
1 1 2 3 4 5
2 1 2 3 4 5
2 3 0 1
3 0
( ) ,
( ) � �
�
�
� 2.
Ïðåîáðàçîâàííàÿ ÑËÍÄÓ èìååò âèä
S
L x x x x x x
L x x x x x
� �
� � � � � � �
� � � �
1 1 2 3 4 5
2 1 2 3 4
7 5 3 2 0
3 0
( ) ,
( ) � � �
�
�
� x5 2.
Áàçèñ ËÎÄÓ L x1 0( )� � ñîñòàâëÿþò âåêòîðû (çäåñü íå íóæíî âû÷èñëÿòü ÍÎÄ
êîýôôèöèåíòîâ, ïîñêîëüêó èìååòñÿ êîýôôèöèåíò, ðàâíûé 1)
( , , , , ), ( , , , , ), ( , , , , ), ( , , , , )10 0 0 7 010 0 5 0 010 3 0 0 012� .
Çíà÷åíèÿ L x2 ( ) íà ýòèõ âåêòîðàõ ðàâíû – 4, 6, –2, –2, èõ íàèáîëüøèé îáùèé
äåëèòåëü ðàâåí 2 è ÿâëÿåòñÿ äåëèòåëåì ñâîáîäíîãî ÷ëåíà b2 2� � . Ñëåäîâàòåëüíî,
ÑËÍÄÓ èìååò ðåøåíèå, ò.å. ñîâìåñòíà.
Åñëè äàíà ñèñòåìà
S
L x x x x x x
L x x x x x
� �
� � � � � � �
� � � �
1 1 2 3 4 5
2 1 2 3 4
7 5 3 2 0
3 0
( ) ,
( ) � � �
�
�
� x5 3,
òî îíà íå èìååò ðåøåíèé â êîëüöå öåëûõ ÷èñåë, ïîñêîëüêó ÍÎÄ (–4, 6, –2, –2) = 2 íå äå-
ëèò ñâîáîäíûé ÷ëåí – 3 è ïîýòîìó óðàâíåíèå � � � � � �4 6 2 2 3x y z u íå èìååò ðåøåíèé.
 çàêëþ÷åíèå çàìåòèì, ÷òî ïðèâåäåííûå îöåíêè âðåìåííûõ ñëîæíîñòåé ìîæ-
íî óòî÷íÿòü, åñëè ïðîñëåæèâàòü âñå äåòàëè ïðîöåññà âû÷èñëåíèé, ïðîèñõîäÿùåãî â
TSS-àëãîðèòìå.  äàííîé ðàáîòå îãðàíè÷èìñÿ óñòàíîâëåíèåì òîãî, ÷òî ýòè àëãîðèò-
ìû ïîëèíîìèàëüíû â àðèôìåòè÷åñêîé ìîäåëè ñëîæíîñòè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ê ð û â û é Ñ . Ë . Àëãîðèòìû ðåøåíèÿ ñèñòåì ëèíåéíûõ äèîôàíòîâûõ óðàâíåíèé â öåëî÷èñëåííûõ
îáëàñòÿõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 2. — Ñ. 3–17.
2. Ä î í å ö à . À . Ðåøåíèå çàäà÷è î ñåéôå íà (0,1)-ìàòðèöàõ // Òàì æå. — 2002. — ¹ 1. — Ñ. 98–105.
3. × å ð å ì ó ø ê è í À .  . Ëåêöèè ïî àðèôìåòè÷åñêèì àëãîðèòìàì â êðèïòîãðàôèè. — Ì.: ÌÖÍÌÎ,
2002. — 103 ñ.
4. B a a d e r F . , Z i e k m a n n J . Unification theory. Handbook of Logic in Artificial Intelligence and
Logic Programming. — Oxford: University Press, 1994. — P. 1–85.
5. A l l e n R . , K e n n e d y K . Automatic translation of FORTRAN program to vector form // ACM Trans-
actions on Programming Languages and systems. — 1987. — 9, N 4. — P. 491–542.
6. C o n t e j a n E . , A j i l i F . Avoiding slack variables in the solving of linear diophantine equations and
inequations // Theoret. Comput. Sci. — 1997. — 173. — P. 183–208.
7. P o t t i e r L . Minimal solution of linear diophantine systems: bounds and algorithms // Proc. of the
Fourth Intern. Conf. on Rewriting Techn. and Appl. — Como. — Italy. — 1991. — P. 162–173.
8. D o m e n j o u d E . Outils pour la deduction automatique dans les theories associatives-commutatives //
Thesis de Doctorat d’Universite: Universite de Nancy I. — 1991.
9. C l a u s e n M . , F o r t e n b a c h e r A . Efficient solution of linear diophantine equations // J. Symbolic
Comput. — 1989. — 8, N 1, 2. — P. 201–216.
10. R o m e u f J . F . A polinomial Algorithm for Solvin systems of two linear Diophantine equations // TCS.
— 1990. — 74, N 3. — P. 329–340.
11. F i l g u e i r a s M . , T o m a s A . P . A fast method for finding the basis of non-negative solutions to
a linear diophantine equation // J. Symbolic Comput. — 1995. — 19, N 2. — P. 507–526.
12. C o m o n H . Constraint solving on terms: Automata techniques (Preliminary lecture notes). Intern. Sum-
mer School on Constraints in Comput. Logics: Gif-sur-Yvette, France, September 5–8. — 1999. — 22 p.
Ïîñòóïèëà 08.07.2009
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 41
|
| id | nasplib_isofts_kiev_ua-123456789-44480 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-25T20:42:24Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Крывый, С.Л. 2013-06-02T08:09:05Z 2013-06-02T08:09:05Z 2009 Алгоритм построения базиса множества решений систем линейных диофантовых уравнений в кольце целых чисел / С.Л. Крывый // Кибернетика и системный анализ. — 2009. — № 6. — С. 36-41. — Бібліогр.: 12 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44480 51.681.3 Запропоновано поліноміальний алгоритм побудови мінімальної породжуючої множини (пред-базиса) і базиса множини всіх розв’язків системи лінійних діофантових рівнянь в кільці цілих чисел. Цей алгоритм грунтується на модифікованому TSS-методі. A polynomial algorithm is proposed to construct the minimal generating set of solutions and the basis of the solution set for systems of linear Diophantine equations over the ring of integer numbers. The algorithm is based on the modified TSS-method. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Алгоритм построения базиса множества решений систем линейных диофантовых уравнений в кольце целых чисел Алгоритм побудови базису множини розв’язків систем лінійних діофантових рівнянь в кільці цілих чисел An algorithm for constructing the basis of the solution set for systems of linear Diophantine equations over the ring of integer numbers Article published earlier |
| spellingShingle | Алгоритм построения базиса множества решений систем линейных диофантовых уравнений в кольце целых чисел Крывый, С.Л. Кибернетика |
| title | Алгоритм построения базиса множества решений систем линейных диофантовых уравнений в кольце целых чисел |
| title_alt | Алгоритм побудови базису множини розв’язків систем лінійних діофантових рівнянь в кільці цілих чисел An algorithm for constructing the basis of the solution set for systems of linear Diophantine equations over the ring of integer numbers |
| title_full | Алгоритм построения базиса множества решений систем линейных диофантовых уравнений в кольце целых чисел |
| title_fullStr | Алгоритм построения базиса множества решений систем линейных диофантовых уравнений в кольце целых чисел |
| title_full_unstemmed | Алгоритм построения базиса множества решений систем линейных диофантовых уравнений в кольце целых чисел |
| title_short | Алгоритм построения базиса множества решений систем линейных диофантовых уравнений в кольце целых чисел |
| title_sort | алгоритм построения базиса множества решений систем линейных диофантовых уравнений в кольце целых чисел |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/44480 |
| work_keys_str_mv | AT kryvyisl algoritmpostroeniâbazisamnožestvarešeniisistemlineinyhdiofantovyhuravneniivkolʹcecelyhčisel AT kryvyisl algoritmpobudovibazisumnožinirozvâzkívsistemlíníinihdíofantovihrívnânʹvkílʹcícílihčisel AT kryvyisl analgorithmforconstructingthebasisofthesolutionsetforsystemsoflineardiophantineequationsovertheringofintegernumbers |