Крывый С. Л.
Алгоритмы решения систем линейных уравнений в кольцах вычетов

Запропоновано поліноміальні алгоритми побудови базису множини розв'язків системи лінійних однорідних і неоднорідних діофантових рівнянь в кільці лишків за модулем деякого числа за умови відомого розкладу модуля на прості множники.

Запропоновано поліноміальні алгоритми побудови базису множини розв'язків системи лінійних однорідних і неоднорідних діофантових рівнянь в полі лишків за модулем простого числа.

Предложены полиномиальные алгоритмы построения базиса множества решений системы линейных однородных и неоднородных диофантовых уравнений в кольце вычетов по модулю некоторого числа при условии известного разложения модуля на простые множители.

Рассмотрены базовые понятия систем линейных однородных и неоднородных уравнений и неравенств в области {0, 1}, к решению которых применяется TSS-алгоритм, и свойства этого алгоритма. Описаны процедуры чистки множеств решений и определения линейно зависимых уравнений системы при работе TSS-алгоритма. На основе базисных понятий и свойств предложена достаточно экономная относительно памяти модификация TSS-алгоритма для численного решения систем линейных однородных уравнений и неравенств с целыми коэффициентами в области {0, 1}. Приведено описание предложенного алгоритма с помощью псевдокода и оценка временной сложности предложенного алгоритма. Рассмотрены алгоритмы решения отдельного класса систем линейных однородных уравнений и неравенств, коэффициенты которых принадлежат множеству {- 1, 0, 1}. Приведен ряд теорем, доказывающих правильность предлагаемых алгоритмов. Описаны их применения к решению следующих задач: поиска множеств независимых вершин неориентированного графа; поиска дедлоков и ловушек в сети Петри; анализа множества дизъюнктов на противоречивость. Для задачи поиска множеств независимых вершин неориентированного графа приведено подробное описание сведения задачи к системе линейных неравенств, предложены 2 алгоритма решения, а также модификация второго алгоритма. Приведены примеры с подробным объяснением выполнения каждого из алгоритмов, а также описаны их временные характеристики работы. Для задач поиска дедлоков и ловушек в сети Петри предложен способ сведения к системам линейных неравенств с коэффициентами во множестве {- 1, 0, 1} и решениями в множестве {0, 1}. Приведены пример с объяснением решения и временные характеристики работы предложенного алгоритма. Алгоритм для анализа множества дизъюнктов на противоречие представлен в виде псевдокода. Кроме проверки на противоречие заданного множества дизъюнктов, он позволяет находить минимальные противоречащие подмножества дизъюнктов, если они существуют. Работа алгоритма проиллюстрирована на примерах с временными характеристиками.

Розглянуто методи розв'язання систем лінійних однорідних діофантових рівнянь в множині натуральних чисел та в множині {0, 1}. Наведено відповідні алгоритми, їх властивості і оцінки часової складності.

PDF

Бібліографічний опис:
Крывый С. Л.  Алгоритмы решения систем линейных уравнений в кольцах вычетов. Кибернетика и системный анализ. 2016. Т. 52, № 5. С. 149-160. doi: https://doi.org/10.1007/s10559-016-9880-8 URL: http://jnas.nbuv.gov.ua/article/UJRN-0000553525