Крывый С. Л. Алгоритмы решения систем линейных ограничений с целыми коэффициентами во множестве {0, 1} / С. Л. Крывый, В. Т. Антонюк // Проблемы упр. и информатики. - 2019. - № 4. - С. 5-25. - Библиогр.: 7 назв. - рус.Рассмотрены базовые понятия систем линейных однородных и неоднородных уравнений и неравенств в области {0, 1}, к решению которых применяется TSS-алгоритм, и свойства этого алгоритма. Описаны процедуры чистки множеств решений и определения линейно зависимых уравнений системы при работе TSS-алгоритма. На основе базисных понятий и свойств предложена достаточно экономная относительно памяти модификация TSS-алгоритма для численного решения систем линейных однородных уравнений и неравенств с целыми коэффициентами в области {0, 1}. Приведено описание предложенного алгоритма с помощью псевдокода и оценка временной сложности предложенного алгоритма. Рассмотрены алгоритмы решения отдельного класса систем линейных однородных уравнений и неравенств, коэффициенты которых принадлежат множеству {- 1, 0, 1}. Приведен ряд теорем, доказывающих правильность предлагаемых алгоритмов. Описаны их применения к решению следующих задач: поиска множеств независимых вершин неориентированного графа; поиска дедлоков и ловушек в сети Петри; анализа множества дизъюнктов на противоречивость. Для задачи поиска множеств независимых вершин неориентированного графа приведено подробное описание сведения задачи к системе линейных неравенств, предложены 2 алгоритма решения, а также модификация второго алгоритма. Приведены примеры с подробным объяснением выполнения каждого из алгоритмов, а также описаны их временные характеристики работы. Для задач поиска дедлоков и ловушек в сети Петри предложен способ сведения к системам линейных неравенств с коэффициентами во множестве {- 1, 0, 1} и решениями в множестве {0, 1}. Приведены пример с объяснением решения и временные характеристики работы предложенного алгоритма. Алгоритм для анализа множества дизъюнктов на противоречие представлен в виде псевдокода. Кроме проверки на противоречие заданного множества дизъюнктов, он позволяет находить минимальные противоречащие подмножества дизъюнктов, если они существуют. Работа алгоритма проиллюстрирована на примерах с временными характеристиками. Індекс рубрикатора НБУВ: В142.2
Рубрики:
Шифр НБУВ: Ж26990 Пошук видання у каталогах НБУВ Повний текст Наукова періодика України
Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"
|