Алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве {0,1}

Simple item page
dc.contributor.authorКрывый, Сергей
dc.contributor.authorАнтонюк, В.
dc.date.accessioned2019-10-06T20:37:08Z
dc.date.available2019-10-06T20:37:08Z
dc.date.issued2019
dc.description.abstractВ настоящей работе рассмотрены общий алгоритм решения СЛОУ и СЛОН в области {0, 1} и отдельный класс СЛОУ и СЛОН, коэффициенты которых принадлежат множеству {-1,0,1}. Специфика такого типа ограничений дает возможность построить алгоритмы вычисления всех множеств независимых вершин графа, алгоритмы поиска дедлоков и ловушек в СП и анализа множества дизъюнктов на противоречивость/непротиворечивость.ru_RU
dc.description.abstractРозглянуто базові поняття систем лінійних однорідних і неоднорідних рівнянь і нерівностей в області {0, 1}, до розв’язання яких застосовується Т88-алгоритм. та властивості цього алгоритму. Описано процедури чистки множин розв’язків та визначено лінійно залежні рівняння системи при роботі ТвЗ-алгоритму. На основі базових понять і властивостей пропонується достатньо економна відносно пам’яті модифікація ТБв-алгоритму для чисельного розв’язання систем лінійних однорідних рівнянь і нерівностей з цілими коефіцієнтами в області {0, 1}. Наводиться опис запропонованого алгоритму за допомогою псевдокоду і оцінка часової складності запропонованого алгоритму. Розглянуто алгоритми розв’язання окремого класу систем лінійних однорідних рівнянь і нерівностей, коефіцієнти яких належать множині (-1 ,0 , 1). Наведено ряд теорем, що доводять правильність пропонованих алгоритмів. Описано їх застосування до розв’язання наступних задач: пошуку множин незалежних вершин зорієнтованого графа; пошуку дедлоків і пасток в мережі Петрі; аналізу множини диз'юнктів на суперечність/несуперечність.uk_UA
dc.description.abstractThe 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 pseudocode 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.en_US
dc.identifier.citationКрывый С. Л. Алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве {0,1} / С. Л. Крывый, В. Т. Антонюк // Проблемы управления и информатики. - 2019. - № 4. - С. 5-25.ru_RU
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/16323
dc.language.isoruuk_UA
dc.relation.sourceПроблемы управления и информатикиru_RU
dc.statusfirst publisheduk_UA
dc.subjectсистемы диофантовых уравненийru_RU
dc.subjectнеравенстваru_RU
dc.subjectбазис множества решенийru_RU
dc.subjectнезависимые множества вершинru_RU
dc.subjectловушки и дедлоки сетей Петриru_RU
dc.subjectстатьяru_RU
dc.subjectсистеми діофантових рівняньuk_UA
dc.subjectнерівностіuk_UA
dc.subjectбазис множини розв’язківuk_UA
dc.subjectнезалежні множини вершинuk_UA
dc.subjectпастки та дедлоки мереж Петріuk_UA
dc.subjectsystems of Diophantine equationsen_US
dc.subjectinequalitiesen_US
dc.subjectbasis of the set of solutionsen_US
dc.subjectindependent sets of verticesen_US
dc.subjecttraps and deadlocks of Petri netsen_US
dc.titleАлгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве {0,1}ru_RU
dc.title.alternativeАлгоритми розв’язання систем лінійних обмежень з цілими коефіцієнтами у множині {0, 1}uk_UA
dc.title.alternativeAlgorithms for Solving the Systems of Linear Constraints with Integer Coefficients in the Set {0, 1}en_US
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Kryvyi_Alhoritmy_resheniia_sistem.pdf
Size:
857.27 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Кафедра математики