Модифікація алгоритму побудови мінімальної генеруючої множини розв’язків СЛР в множині натуральних чисел
The work presents optimization transformations of the algorithm for constructing the minimum supported set of solutions of the system of linear equations in the set of natural numbers, which improve the time characteristics of this algorithm.
Gespeichert in:
| Datum: | 2023 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Schlagworte: | |
| Online Zugang: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/291 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479660721340416 |
|---|---|
| author | Kryvyi, Sergii Chugaenko, Oleksii |
| author_facet | Kryvyi, Sergii Chugaenko, Oleksii |
| author_institution_txt_mv | [
{
"author": "Sergii Kryvyi",
"institution": "д. ф.-м. н., професор, Київський Національний університет імені Тараса Шевченка, 03680, Київ, проспект академіка Глушкова 4Д"
},
{
"author": "Oleksii Chugaenko",
"institution": "старший програміст ТОВ «SAMSUNG RND Ukraina», 01032, Київ, в. Толстого, б. 57."
}
] |
| author_sort | Kryvyi, Sergii |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:32:19Z |
| description | The work presents optimization transformations of the algorithm for constructing the minimum supported set of solutions of the system of linear equations in the set of natural numbers, which improve the time characteristics of this algorithm. |
| first_indexed | 2026-06-09T01:09:48Z |
| format | Article |
| fulltext |
131
doi.org/10.15407/fmmit2023.36.131
Модифікація алгоритму побудови мінімальної генеруючої
множини розв’язків СЛР в множині натуральних чисел
Сергій Кривий1, Олексій Чугаєнко2
1 д. ф.-м. н., професор, Київський Національний університет імені Тараса Шевченка, 03680, Київ, проспект
академіка Глушкова 4Д, e-mail: sl.krivoi@gmail.com
2
старший програміст ТОВ «SAMSUNG RND Ukraina», 01032, Київ, в. Толстого, б. 57.
email: firestream_13@yahoo.com
У роботі наведена оптимізаційні перетворення алгоритму побудови мінімальної
генеруючої множини розв’язків системи лінійних однорідних рівнянь в множині
натуральних чисел, які покращують часові характеристики цього алгоритму з
обгрунтуванням та ілюстрацією роботи на прикладах.
Ключові слова: Діофантові рівняння, алгоритм, розв’язання, складність
Вступ. Існує багато задач зводиться до розв’язання систем лінійних рівнянь
(СЛР) і тому було розроблено багато методів розв’язання СЛР. Особливе місце в
цьому ряду займають СЛР, розв’язки яких шукаються в множині натуральних
чисел N. Більше століття тому було встановлено, що СЛР такого типу мають
скінченний базис множини всіх розв’язків [1,2], але алгоритму побудови цього
базису не було (тоді і поняття алгоритму не існувало) Роботи по пошуку
алгоритмів розв'язання СЛР велися весь час, але особлива активність в цьому
напрямку почалася на початку 80-х років 20-го століття у зв'язку з роботами по
побудові пруверів для теорій першого порядку. Побудова пруверів вимагала
розв'язання проблеми уніфікації термів у асоціативно-комутативних теоріях
першого порядку, яке зводилося до розв'язання СЛР в множині N. З'явилися
алгоритми розв'язання одного лінійного однорідного рівняння (ЛОР) [3], систем
ЛОР (СЛОР) [4,5,6] та інші. В кінці 20-го століття був розроблений TSS-метод і
алгоритм розв’язання СЛР у множині N для аналізу мереж Петрі [7]. Алгоритм,
побудований на TSS-методі, описаний в монографії [8] і застосовний для
розв’язання систем лінійних обмежень типу рівностей і нерівностей.
Особливістю цього алгоритму є те, що в процесі пошуку розв’язків систем він не
використовує операцію ділення, за винятком скорочення на найбільший спільний
дільник. Алгоритм знаходить мінімальну генеруючу множину розв’язків СЛОР у
множині N. Слід зазначити, що всі алгоритми розв’язання СЛОР і TSS-алгоритм в
тому числі у множині N досить складні [8, 9].
1. Алгоритм побудови мінімальної генеруючої множини розв’язків СЛОР
Нехай дана СЛОР з цілими коефіцієнтами
УДК 004.822
mailto:sl.krivoi@gmail.com
Сергій Кривий, Олексій Чугаєнко
Модифікація алгоритму побудови мінімальної генеруючої множини розв’язків …
132
1 11 1 12 2 1
1 1 2 2
( ) ... 0,
.........................................................
( ) ... 0,
q q
p p p pq q
L x a x a x a x
S
L x a x a x a x
(1)
де aij ∈ Z (множина цілих чисел), а xij приймають значення y множині N.
Розглянемо множину векторів канонічного базису M0' = {e1,e2,…,eq} і перше
рівняння L1(x) = а11x1+a12x2+…+a1qxq=0 системи S. За допомогою функції L1(x)
розіб'ємо елементи множини M0' на такі три групи: M1
0
= {e | L1(e) = 0}, M1
+
={e
| L1(e) > 0} і M1
-
= {e | L1(e) < 0}. Зрозуміло, що коли одна з множин M1
0
∪ M1
+
чи M1
0
∪ M1
-
пуста, то рівняння L1(x) = 0 не має нетривіальних розв'язків у
множині натуральних чисел. Якщо множини M1
0
, M1
+
, M1
-
непусті, то розглянемо
множину M1' = M1
0
∪ {yij | yij = -L1(ei)ej + L1(ej)ei}, де ej ∈ M1
+
, ei ∈ M1
-
.
Використовуючи функцію L2(x), розіб'ємо елементи множини M1' аналогічно до
попереднього також на три групи: M2
0
={e | L2(e) = 0}, M2
+
= {e | L2(e) > 0} і M2
-
=
={e | L2(e) < 0}. Припустимо, що принаймні дві з цих множин непусті, тоді
побудуємо множину
M2' = M2
0
∪ {yij | yij = -L2(ei)ej + L2(ej)ei, де ej ∈ M2
+
, ei ∈ M2
-
}.
Нехай таким способом побудовано множину Mj' із множин Mj
0
={er
0
| Lj(er
0
) = 0},
Mj
+
={ei
+
| Lj(ei
+
) > 0} й Mj
-
= {es
-
| Lj(es
-
) < 0} за допомогою функції Lj(x) і ця
множина непуста. Справедлива очевидна
Теорема 1. Елементи множини Mj' – розв'язки системи рівнянь
L1(x) = 0 L2(x) = 0 … Lj(x) = 0.
Означення 1. Побудована множина Mj' називається зрізаною множиною
розв'язків або TSS (від англійського truncated set оf solutions). Ця назва себе
виправдовує, оскільки отримана множина розв'язків не завжди буде базисом
множини всіх розв'язків системи.
Генеруюча властивість TSS випливає з такої теореми.
Теорема 2. Нехай М – TSS системи лінійних однорідних рівнянь (1) у
множині N, побудована вищеописаним способом, і М’ множина всіх розв’язків
цієї системи. Тоді довільний розв’язок x ∈ M’ представляється у вигляді лінійної
комбінації
1 1 2 2 ,m mkx a e a e a e де k ≥ 1, ai ∈ N, ei ∈ M, i = 1,…m [8].
Нехай (x,y) означає скалярний добуток векторів x i y, а Li(x) – ліву частину i-го
рівняння S. З вищесказаного випливає такий алгоритм побудови TSS для СЛОДР
у множині натуральних чисел N.
TSSEQN(Mp,q)
Вхід: Матриця СЛОДР розмірності p×q.
Вихід: TSS-множина M розв'язків СЛОДР або ``несумісна''.
Метод:
M:={e1,…,eq | ei канонічний вектор Nq});
for i := 1 to p do
M:=TSSEQN1(M,Li(x));
if M= then (print(несумісна);STOP) else CLEAN(M);
print(M);
TSSEQN1(M,L(x))
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 131-136
133
begin
M0:= ; \ M+:= ; M:= ;
forall e ∈ M do
if L(e)=0 then M0:=M0 ∪ {e} else
if L(e) > 0 then M+:=M+ ∪ {e} else M-:=M- ∪ {e};
M':= M0;
if M+ ≠ M- ≠ then
forall u ∈ M+ do
forall v ∈ M- do e := -L(v)u + L(u)v; M':=M' ∪ {e} od;
return(M');
end
Процедура CLEAN(M) виконує чистку отриманної множини розв'язків M. В
загальному випадку така чистка зводиться до пошуку невід'ємних розв'язків
СЛНР таких, що коли розв'язок a є невід'ємною лінійною комбінацією решти
розв'язків із множини М, то він із М вилучається.
З наведених теорем 1, 2 випливає, що кожний вектор TSS можна поділити на
НСД його координат, якщо цей НСД відмінний від одиниці. Це дає змогу
зменшити величину координат цих векторів і ефективніше проводити
обчислення.
Розглянемо приклади, які ілюструють роботу алгоритму TSSEQN та
властивості множини розв'язків, отриманих цим алгоритмом. Покажемо
спочатку, що результати обчислень TSS залежать від порядку рівнянь у системі.
Приклад 1. Знайти TSS розв’язки у множині натуральних чисел N:
1 2 3 4
1 2 3 4
2 3 0,
3 2 0.
x x x x
s
x x x x
Розв’язання. TSS першого рівняння набуває вигляду:
е1=(1,1,0,0), е2 = (2,0,1,0) е3=(0,3,0,1), е4=(0,0,3,2).
Підставляємо в друге рівняння знайдені розв’язки і знаходимо значення: 2, -4, 8, -8.
Комбінуючи їх за знайденими значенями, дістаємо таку TSS системи:
s1=2е1+е2=(4,2,1,0), s2=2е2+е3=(4,3,2,1), s3=4е1+е4=(4,4,3,2), s4 = е3+е4=(0,3,3,3),
Де останній розв’язок після скорочення на НСД координат набуває вигляду s4 =
=(0,1,1,1). Розв’язки s2 і s3 лінійно виражаються через s1 і s4 , дійсно
s2 = s1 + s4 і s3 = s1 +2s4.
Отже, розв’язки s1 і s4 складають мінімальну породжуючи множину всіх розв’язків
початкової системи.
А тепер почнемо будувати TSS з другого рівняння даної системи. Дістаємо таку TSS
е1 = (3,1,0,0), е2 = (0,2,3,0), е3 = (0,1,0,3).
Підстановка в перше рівняння знайдених розв’язків другого рівняння дає значення -1,4,
-4. Тоді TSS всієї системи маї вигляд:
s1=4е1+е2=(12,6,3,0) (після скорочення на НСД) = (4,2,1,0),
s2=е2+е3=(0,3,3,3) ( після скорочення на НСД) = (0,1,1,1).
TSS розв’язки для даної системи є базисом всієї множини розв’язків, але в загальному
випадку мінімальна породжуючи множина розв’язків базисом не буде, як показує
наступний приклад. Отже, другий спосіб побудови TSS не обчислює «лишніх» розв’язків
СЛОР.
Приклад 2. Перевірити сумісність СЛОДР:
Сергій Кривий, Олексій Чугаєнко
Модифікація алгоритму побудови мінімальної генеруючої множини розв’язків …
134
1 1 2 3 4 5
2 1 2 3 4 5
3 1 2 3 5
( ) 4 2 3 2 0,
( ) 2 4 5 0,
( ) 0 2 4 0 9 0.
L x x x x x x
S L x x x x x x
L x x x x x x
TSS M1' складають вектори:e1 = (3,0,4,0,0), e2 = (0,3,2,0,0), e3 = (1,0,0,2,0), e4 = (0,1,0,1,0), e5 =
(1,0,0,0,4), e6 = (0,1,0,0,2). Базис множини розв'язків рівняння L1(x) = 0 (який можна знайти,
наприклад, методом із роботи [3]) складають вектори: e1 = (3,0,4,0,0), e2 = (0,3,2,0,0), e3 =
(1,0,0,2,0), e4 = (0,1,0,1,0), e5 = (1,0,0,0,4), e6 = (0,1,0,0,2), e7 = (2,0,2,1,0), e8 = (1,1,2,0,0), e9 =
(1,0,0,1,2), e10 = (0,2,1,0,1), e11 = (1,0,1,0,1). Вектори e7 - e11 цього базису мають такі розклади
через вектори e1 – e6: 2e7 = e1 + e3, 3e8 = e1 + e2, 2e9 = e3 + e5, 2e10 = e2 + e6, 4e11 = e1 + e5.
Знаходячи значення функції L2(x) на векторах із M1', маємо
L2(e1) = -10, L2(e2) = -11, L2(e3) = 4, L2(e4) = 0, L2(e5) = 22, L2(e6) = 9. Будуємо M2':
e1'= (0,1,0,1,0), e2'=2e1+5e3=(11,0,8,10,0), e3'=4e2+11e3=(11,12,8,22,0), e4'=2e2 +e5 =(1,6,4,0,4),
e5'=9e2 +11e6 = (0,19,9,0,11), e6'=11e1+5e5 = (19,0,22,0,10), e7'= 9e1 + 10e6 = (27,10,36,0,20).
Якщо одержану множину розв'язків проаналізувати на лінійну залежність, то дістаємо
таку множину векторів M2' = {e1' = (0,1,0,1,0), e2' = (11,0,8,10,0), e4' = (0,19,9,0,11), e5' =
=(19,0,22,0,10)}, оскільки e3' = e2'+ 12e1', 19e4'=6e5'+ e6', 19e7' = 10e5' + 27e6' і їх можна
вилучити із TSS.
Базис множини розв'язків системи L1(x)=0 L2(x)=0 складають такі вектори:
s1 = (0,1,0,1,0), s2 = (11,0,8,10,0), s3 = (16,1,19,0,9), s4 = (0,19,9,0,11),
s5 = (19,0,22,0,10), s6 = (1,6,4,0,4), s7 = (13,2,16,0,8), s8 = (10,3,13,0,7),
s9 = (7,4,10,0,6), s10 = (4,5,7,0,5), s11 = (3,0,3,1,1).
Вектори s6 – s11 i s3 є лінійними комбінаціями векторів s1=(0,1,0,1,0), s2=(11,0,8,10,0),
s4=(0,19,9, 0,11), s5 = (19,0,22,0,10), мають такий вигляд:
19s6 = 6s4 + s5, 19s7 = 2s4 + 13s5, 19s8 = 3s3+ 10s5,
19s9 = 4s4 + 7s5, 19s10 = 5s4 + 4s, 10s11 = s2 + s5,19s3=s4+16s5.
Значення L3(s1) = 2, L3(s2) = 32, L3(s4) = -25, L3(s5) =-2, тобто система сумісна i має
принаймні чотири розв'язки:
s1'=(19,1,22,1,10), s2'= (275,608,488,250,352), s3'=(0,63,18,25,22), s4' = (63,0,72,2,32).
Але розв’язки s1',s2' лінійно виражаються через s3'=(0,63,18,25,22), s4' = (63,0,72,2,32).
Справді, 63∙(19,1,22,1,10) = 19∙(63,0,72,2,32) + (0,63,18,25,22) і 63∙(275,608,488,250,352) =
=275∙(63,0,72,2,32) + 608∙(0,63,18,25,22). Отже, розв’язки s3'=(0,63,18,25,22), s4' = (63,0,72,2,32)
складають TSS системи S.
2. Оптимізаційні перетворення TSS-алгоритма
Тепер можна описати оптимізаційні перетворення та оцінити їх ефективність на
конкретних задачах.
Перше оптимізаційне перетворення випливає з аналізу ситуації в прикладі 1.
Це перетворення зводиться до вибору першого рівняння системи, з якого
починається побудова TSS: слід вибирати серед рівнянь системи те рівняння,
у якого величина kn+m мінімальна, де k – кількість додатних коефіцієнтів, n –
кількість від'ємних коефіцієнтів і m – кількість нульових коефіцієнтів у системі.
Це перетворення ефективне, як показують експерименти, але воно не завжди
можливе в ситуації, коли для всіх рівнянь системи величина kn+m однакова.
Друге оптимізаційне перетворення випливає з першого і зводиться до
діагоналізації матриці системи. Діагоналізація має поліноміальну складність і
дозволяє зменшити величину kn+m, про яку йшлося в першому перетворенні.
Простий приклад ілюструє ефективність цього перетворення: нехай матриця А
СЛОДР має вигляд:
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 131-136
135
2 1 3 1 4 2
1 0 2 3 2 1
3 1 1 0 1 2
4 1 1 2 0 1
A
,
0 0 0 31 5 38
0 0 2 2 3 5
'
0 2 0 25 5 35
1 0 0 5 1 6
A
.
Перетворивши матрицю А до неповного трикутно-діагонального вигляду А’ і
застосувавши TSS-алгоритм, дістаємо таку кількість комбінацій -L(v)u + +L(u)v,
які обчислюються під час побудови TSS (TSS складається з двох розв'язків
(16,15,89,0,76,10) і (2,0,3,5,7,5)) цієї СЛОДР з матрицями A і A': для першої
матриці обчислюється 31комбінація, а для другої – 8 комбінацій!!!
Третє оптимізаційне перетворення випливає з аналізу ситуації в прикладі 2.
Аналіз векторів, які входять до TSS, показує, що обчислення, пов’язані з
наступним рівнянням системи, збільшують кількість ненульових координат в
розв’язках TSS на одиницю. Якщо кількість ненульових координат в лінійній
комбінації e := -L(v)u + L(u)v при обчисленнях для і-го рівняння системи
перевищує величину q-(i+1), де q кількість невідомих системи, то будувати цю
комбінацію непотрібно. В прикладі 2 при знаходженні TSS підсистеми з перших
двох рівнянь не будуть обчислюватися розв’язки e3’, e4’, e3’, а при обчисленні
TSS всієї системи не будуть обчислюватися розв’язки s1’, s2’.Це прискорює
обчислення TSS СЛОР. Останнє обгрунтовує така теорема.
Теорема 3. Нехай S – СЛОДР вигляду (1) і Mp' – її TSS, яка має k елементів.
Тоді довільний вектор x із Mp' такий, що tx ≥ ei ϵ Mp' \{x}, t ϵ N і t ≠ 0, представ-
ляється у вигляді невід'ємної лінійної комбінації mx = b1e1 + b2e2 +…+ bk-1ek-1, де
m ϵ N, m ≠ 0, bi ϵ N, i = 1, 2,…, k-1[8].
Обчислень комбінацій такого типу можна уникнути, якщо завчасно
підрахувати кількість ненульових координат в комбінації e := -L(v)u + L(u)v. Це
потребує такої модифікації підпрограми TSSEQN1(M,L(x)):
TSSEQN1(M,L(x))
begin
M0:= ; \ M+:= ; M:= ;
forall e ∈ M do
if L(e)=0 then M0:=M0 ∪ {e} else
if L(e) > 0 then M+:=M+ ∪ {e} else M-:=M- ∪ {e};
M':= M0;
if M+ ≠ M- ≠ then
forall u ∈ M+ do (* де u=(u(1),…, u(q)) *)
forall v ∈ M- do (* де v=(v(1),…,v(q)) *)
z := 0; (* підрахунок кількості ненульових координат *)
for j:=1 to q do if (u(j) ≠ 0 v(j) ≠ 0) then z:=z+1 od
if z ≤ (q-(i+1)) then ( e := -L(v)u + L(u)v; M':=M' ∪ {e});
return(M');
end
3. Експериментальні результати оптимізаційних перетворень
Підводячи підсумки вищесказаному, наведемо експериментальні результати,
отримані на конкретних прикладах систем.
Сергій Кривий, Олексій Чугаєнко
Модифікація алгоритму побудови мінімальної генеруючої множини розв’язків …
136
Таблиця 1
Розмірності систем, норми коефіцієнтів та часові характеристики їх розв’язання
до і після застосування оптимізаційних перетворень
Розмірність
системи
Час без
оптимізації
(секунди)
Час з
оптимізацією
(секунди)
Загальна кількість
кандидатів
Кількість відкинутих
кандидатів
32x38 5.45 0.45 56240 45695 (81%)
12x25 229.29 184.44 40699436 6002799 (14%)
12x25.1 237.76 216.54 44543433 5965471 (13%)
Загалом перше перетворення, якщо воно застосовне, дає в середньому 15-20%
прискорення обчислень, друге перетворення дає в середньому 35-40% і третє
перетворення – 20-25%.
Висновки. В роботі представлено ефективність оптимізаційних перетворень
алгоритму побудови мінімальної генеруючої множини розв’язків систем
лінійних однорідних рівнянь у множині натуральних чисел.
Література
[1] Gordan P. Ueber die Auflösung linearen Gleidungen mit reallen Coefficienten. Mathematische
Annalen, 1873, № 6, P. 23–28.
[2] Hilbert D. Ueber die Theorie der algebraischen Formen. Mathematische Annalen, 1890, № 36,
– P. 473–534.
[3] Clausen M., Fortenbacher A. Efficient solution of linear diophantine equations. Journ.
Symbolic Computation, 1989, v.8. № 1,2. – P. 201–216.
[4] Contenjean E., Devie H. An efficient algorithm for solving systems of Diophantine
equations, Inform. Comput, 1994, № 113, v. 1. – P. 143–172.
[5] Domenjoud E. Outils pour la deduction automatique dans les theories associatives-
commutatives. Thesis de Doctorat d'Universite: Universite de Nancy I, 1991.
[6] Pottier L. Minimal solution of linear diophantine systems: bounds and algorithms. In Proceed. of
the 4-th Intern. Conf. on Rewriting Techniques and Applications, Como, Italy, 1991, – P.162–173.
[7] Крывый С.Л. 0 вычислении минимального множества инвариантов сетей Петри. Ж. Искус-
ственный интеллект, 2001, № 3. с. 199-206
[8] Кривий С.Л. Лінійні Діофантові обмеження та їх застосування. К: Інтерсервіс, 2021, – 260 с.
[9] Hermann M., Juban L., Kolaitis P. G. On the Complexity of Counting the Hilbert Basis of a
Linear Diophantine System. Springer Verlag, LNCS, 1999, № 1705. – P. 13–32.
Modification of algorithm for constructing minimal supported set of solutions of SLE over the set of
natural numbers
Sergii Kryvyi, Oleksii Chugaenko
The work presents optimization transformations of the algorithm for constructing the minimum
supported set of solutions of the system of linear equations in the set of natural numbers, which
improve the time characteristics of this algorithm.
Отримано 13.03.23
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-291 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:09:48Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/6a/308e1be420f7a6a2d04d6238b3f8456a.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-2912025-02-21T17:32:19Z Modification of algorithm for constructing minimal supported set of solutions of SLE over the set of natural numbers Модифікація алгоритму побудови мінімальної генеруючої множини розв’язків СЛР в множині натуральних чисел Kryvyi, Sergii Chugaenko, Oleksii Діофантові рівняння, алгоритм, розв’язання, складність The work presents optimization transformations of the algorithm for constructing the minimum&nbsp;supported set of solutions of the system of linear equations in the set of natural numbers, which improve the time characteristics of this algorithm. У роботі наведена оптимізаційні перетворення алгоритму побудови мінімальної генеруючої множини розв’язків системи лінійних однорідних рівнянь в множині натуральних чисел, які покращують часові характеристики цього алгоритму з обгрунтуванням та ілюстрацією роботи&nbsp; на прикладах.&nbsp; &nbsp; Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-13 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/291 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 131-136 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 131-136 2617-5258 1816-1545 10.15407/fmmit2023.36 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/291/239 Авторське право (c) 2023 Сергій Кривий, Олексій Чугаєнко (Автор) |
| spellingShingle | Діофантові рівняння алгоритм розв’язання складність Kryvyi, Sergii Chugaenko, Oleksii Модифікація алгоритму побудови мінімальної генеруючої множини розв’язків СЛР в множині натуральних чисел |
| title | Модифікація алгоритму побудови мінімальної генеруючої множини розв’язків СЛР в множині натуральних чисел |
| title_alt | Modification of algorithm for constructing minimal supported set of solutions of SLE over the set of natural numbers |
| title_full | Модифікація алгоритму побудови мінімальної генеруючої множини розв’язків СЛР в множині натуральних чисел |
| title_fullStr | Модифікація алгоритму побудови мінімальної генеруючої множини розв’язків СЛР в множині натуральних чисел |
| title_full_unstemmed | Модифікація алгоритму побудови мінімальної генеруючої множини розв’язків СЛР в множині натуральних чисел |
| title_short | Модифікація алгоритму побудови мінімальної генеруючої множини розв’язків СЛР в множині натуральних чисел |
| title_sort | модифікація алгоритму побудови мінімальної генеруючої множини розв’язків слр в множині натуральних чисел |
| topic | Діофантові рівняння алгоритм розв’язання складність |
| topic_facet | Діофантові рівняння алгоритм розв’язання складність |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/291 |
| work_keys_str_mv | AT kryvyisergii modificationofalgorithmforconstructingminimalsupportedsetofsolutionsofsleoverthesetofnaturalnumbers AT chugaenkooleksii modificationofalgorithmforconstructingminimalsupportedsetofsolutionsofsleoverthesetofnaturalnumbers AT kryvyisergii modifíkacíâalgoritmupobudovimínímalʹnoígeneruûčoímnožinirozvâzkívslrvmnožinínaturalʹnihčisel AT chugaenkooleksii modifíkacíâalgoritmupobudovimínímalʹnoígeneruûčoímnožinirozvâzkívslrvmnožinínaturalʹnihčisel |