Алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве (0, 1)
Предложены полиномиальные алгоритмы построения базиса множества решений системы линейных однородных и неоднородных диофантовых уравнений в кольце вычетов по модулю некоторого числа при условии известного разложения модуля на простые множители. Запропоновано поліноміальні алгоритми побудови базису мн...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2019 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/180816 |
| 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: | Алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве (0, 1) / С.Л. Крывый , В.Т. Антонюк // Проблемы управления и информатики. — 2019. — № 4. — С. 5-25. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862741548178866176 |
|---|---|
| author | Крывый, С.Л. Антонюк, В.Т. |
| author_facet | Крывый, С.Л. Антонюк, В.Т. |
| citation_txt | Алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве (0, 1) / С.Л. Крывый , В.Т. Антонюк // Проблемы управления и информатики. — 2019. — № 4. — С. 5-25. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Предложены полиномиальные алгоритмы построения базиса множества решений системы линейных однородных и неоднородных диофантовых уравнений в кольце вычетов по модулю некоторого числа при условии известного разложения модуля на простые множители.
Запропоновано поліноміальні алгоритми побудови базису множини розв'язків системи лінійних однорідних і неоднорідних діофантових рівнянь в кільці лишків за модулем деякого числа за умови відомого розкладу модуля на прості множники.Запропоновано поліноміальні алгоритми побудови базису множини розв'язків системи лінійних однорідних і неоднорідних діофантових рівнянь в полі лишків за модулем простого числа.Розглянуто методи розв'язання систем лінійних однорідних діофантових рівнянь в множині натуральних чисел та в множині {0, 1}. Наведено відповідні алгоритми, їх властивості і оцінки часової складності.
The basic concepts of linear homogeneous and inhomogeneous equations and inequalities in the domain {0, 1}, are considered the properties of the TSS-algorithm, which may be applied in solving those systems are described. The procedures for clearing the sets of solutions and determining the linearly dependent equations of the system during the process of the TSS algorithm are shown. Based on the basic concepts and properties, a memory effective modification of the TSS-algorithm for solving systems of linear homogeneous equations and inequalities with integer coefficients in {0, 1} is offered. A description of the proposed algorithm using pseudo-code and an estimate of the time complexity are given. Algorithms for solving a separate class of systems of linear homogeneous equations and inequalities whose coefficients belong to the set {– 1, 0, 1} are considered. A series of theorems that prove the correctness of the proposed algorithms are given. It is described their application to the following problems: finding sets of independent vertices of an undirected graph; finding deadlocks and traps in the Petri net; analysis of a set of clauses for inconsistency. For the task of finding sets of independent vertices of an undirected graph, a detailed description of reducing the problem to a system of linear inequalities is given, two solution algorithms are proposed, as well as a modification of the second algorithm. Examples are presented with a detailed explanation of the solution via each of the algorithms and their time characteristics of work are described. For problems of finding deadlocks and traps in the Petri net, a method for reducing it to systems of linear inequalities with coefficients in the set {– 1, 0, 1} and solutions in the set {0, 1} is proposed. An example with the solution explanation and time characteristics of the work of the offered algorithm is described. The algorithm for analyzing the set of clauses for inconsistency is presented in a pseudo-code form. In addition to checking for the inconsistency of a given set of clauses, it allows you to find the minimal inconsistent subsets of clauses if they exist. The operation of the algorithm is illustrated with examples and time characteristics of the algorithm are described.
|
| first_indexed | 2025-12-07T20:19:56Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-180816 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T20:19:56Z |
| publishDate | 2019 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Крывый, С.Л. Антонюк, В.Т. 2021-10-20T11:32:32Z 2021-10-20T11:32:32Z 2019 Алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве (0, 1) / С.Л. Крывый , В.Т. Антонюк // Проблемы управления и информатики. — 2019. — № 4. — С. 5-25. — Бібліогр.: 7 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/180816 51.681.3 Предложены полиномиальные алгоритмы построения базиса множества решений системы линейных однородных и неоднородных диофантовых уравнений в кольце вычетов по модулю некоторого числа при условии известного разложения модуля на простые множители. Запропоновано поліноміальні алгоритми побудови базису множини розв'язків системи лінійних однорідних і неоднорідних діофантових рівнянь в кільці лишків за модулем деякого числа за умови відомого розкладу модуля на прості множники.Запропоновано поліноміальні алгоритми побудови базису множини розв'язків системи лінійних однорідних і неоднорідних діофантових рівнянь в полі лишків за модулем простого числа.Розглянуто методи розв'язання систем лінійних однорідних діофантових рівнянь в множині натуральних чисел та в множині {0, 1}. Наведено відповідні алгоритми, їх властивості і оцінки часової складності. The basic concepts of linear homogeneous and inhomogeneous equations and inequalities in the domain {0, 1}, are considered the properties of the TSS-algorithm, which may be applied in solving those systems are described. The procedures for clearing the sets of solutions and determining the linearly dependent equations of the system during the process of the TSS algorithm are shown. Based on the basic concepts and properties, a memory effective modification of the TSS-algorithm for solving systems of linear homogeneous equations and inequalities with integer coefficients in {0, 1} is offered. A description of the proposed algorithm using pseudo-code and an estimate of the time complexity are given. Algorithms for solving a separate class of systems of linear homogeneous equations and inequalities whose coefficients belong to the set {– 1, 0, 1} are considered. A series of theorems that prove the correctness of the proposed algorithms are given. It is described their application to the following problems: finding sets of independent vertices of an undirected graph; finding deadlocks and traps in the Petri net; analysis of a set of clauses for inconsistency. For the task of finding sets of independent vertices of an undirected graph, a detailed description of reducing the problem to a system of linear inequalities is given, two solution algorithms are proposed, as well as a modification of the second algorithm. Examples are presented with a detailed explanation of the solution via each of the algorithms and their time characteristics of work are described. For problems of finding deadlocks and traps in the Petri net, a method for reducing it to systems of linear inequalities with coefficients in the set {– 1, 0, 1} and solutions in the set {0, 1} is proposed. An example with the solution explanation and time characteristics of the work of the offered algorithm is described. The algorithm for analyzing the set of clauses for inconsistency is presented in a pseudo-code form. In addition to checking for the inconsistency of a given set of clauses, it allows you to find the minimal inconsistent subsets of clauses if they exist. The operation of the algorithm is illustrated with examples and time characteristics of the algorithm are described. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Проблемы динамики управляемых систем Алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве (0, 1) Алгоритми розв’язання систем лінійних обмежень з цілими коефіцієнтами у множині {0, 1} Algorithms for solving the systems of linear constraints with integer coefficients in the set {0, 1} Article published earlier |
| spellingShingle | Алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве (0, 1) Крывый, С.Л. Антонюк, В.Т. Проблемы динамики управляемых систем |
| title | Алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве (0, 1) |
| title_alt | Алгоритми розв’язання систем лінійних обмежень з цілими коефіцієнтами у множині {0, 1} Algorithms for solving the systems of linear constraints with integer coefficients in the set {0, 1} |
| title_full | Алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве (0, 1) |
| title_fullStr | Алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве (0, 1) |
| title_full_unstemmed | Алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве (0, 1) |
| title_short | Алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве (0, 1) |
| title_sort | алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве (0, 1) |
| topic | Проблемы динамики управляемых систем |
| topic_facet | Проблемы динамики управляемых систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/180816 |
| work_keys_str_mv | AT kryvyisl algoritmyrešeniâsistemlineinyhograničeniiscelymikoéfficientamivomnožestve01 AT antonûkvt algoritmyrešeniâsistemlineinyhograničeniiscelymikoéfficientamivomnožestve01 AT kryvyisl algoritmirozvâzannâsistemlíníinihobmeženʹzcílimikoefícíêntamiumnožiní01 AT antonûkvt algoritmirozvâzannâsistemlíníinihobmeženʹzcílimikoefícíêntamiumnožiní01 AT kryvyisl algorithmsforsolvingthesystemsoflinearconstraintswithintegercoefficientsintheset01 AT antonûkvt algorithmsforsolvingthesystemsoflinearconstraintswithintegercoefficientsintheset01 |