Наукова періодика України Кібернетика та системний аналіз


Крывый С. Л. 
Алгоритмы решения систем линейных уравнений в кольцах вычетов / С. Л. Крывый // Кибернетика и системный анализ. - 2016. - Т. 52, № 5. - С. 149-160. - Режим доступу: http://nbuv.gov.ua/UJRN/KSA_2016_52_5_13
Запропоновано поліноміальні алгоритми побудови базису множини розв'язків системи лінійних однорідних і неоднорідних діофантових рівнянь в кільці лишків за модулем деякого числа за умови відомого розкладу модуля на прості множники.Запропоновано поліноміальні алгоритми побудови базису множини розв'язків системи лінійних однорідних і неоднорідних діофантових рівнянь в полі лишків за модулем простого числа.Розглянуто методи розв'язання систем лінійних однорідних діофантових рівнянь в множині натуральних чисел та в множині {0, 1}. Наведено відповідні алгоритми, їх властивості і оцінки часової складності.Предложены полиномиальные алгоритмы построения базиса множества решений системы линейных однородных и неоднородных диофантовых уравнений в кольце вычетов по модулю некоторого числа при условии известного разложения модуля на простые множители.Рассмотрены базовые понятия систем линейных однородных и неоднородных уравнений и неравенств в области {0, 1}, к решению которых применяется TSS-алгоритм, и свойства этого алгоритма. Описаны процедуры чистки множеств решений и определения линейно зависимых уравнений системы при работе TSS-алгоритма. На основе базисных понятий и свойств предложена достаточно экономная относительно памяти модификация TSS-алгоритма для численного решения систем линейных однородных уравнений и неравенств с целыми коэффициентами в области {0, 1}. Приведено описание предложенного алгоритма с помощью псевдокода и оценка временной сложности предложенного алгоритма. Рассмотрены алгоритмы решения отдельного класса систем линейных однородных уравнений и неравенств, коэффициенты которых принадлежат множеству {- 1, 0, 1}. Приведен ряд теорем, доказывающих правильность предлагаемых алгоритмов. Описаны их применения к решению следующих задач: поиска множеств независимых вершин неориентированного графа; поиска дедлоков и ловушек в сети Петри; анализа множества дизъюнктов на противоречивость. Для задачи поиска множеств независимых вершин неориентированного графа приведено подробное описание сведения задачи к системе линейных неравенств, предложены 2 алгоритма решения, а также модификация второго алгоритма. Приведены примеры с подробным объяснением выполнения каждого из алгоритмов, а также описаны их временные характеристики работы. Для задач поиска дедлоков и ловушек в сети Петри предложен способ сведения к системам линейных неравенств с коэффициентами во множестве {- 1, 0, 1} и решениями в множестве {0, 1}. Приведены пример с объяснением решения и временные характеристики работы предложенного алгоритма. Алгоритм для анализа множества дизъюнктов на противоречие представлен в виде псевдокода. Кроме проверки на противоречие заданного множества дизъюнктов, он позволяет находить минимальные противоречащие подмножества дизъюнктов, если они существуют. Работа алгоритма проиллюстрирована на примерах с временными характеристиками.
  Повний текст PDF - 135.837 Kb    Зміст випуску     Цитування публікації

Цитованість авторів публікації:
  • Крывый С.

  • Бібліографічний опис для цитування:

    Крывый С. Л. Алгоритмы решения систем линейных уравнений в кольцах вычетов / С. Л. Крывый // Кибернетика и системный анализ. - 2016. - Т. 52, № 5. - С. 149-160. - Режим доступу: http://nbuv.gov.ua/UJRN/KSA_2016_52_5_13.

      Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"
     
    Відділ інформаційно-комунікаційних технологій
    Пам`ятка користувача

    Всі права захищені © Національна бібліотека України імені В. І. Вернадського