Подробное описание документа

Волков М. С. А., Гордеев Э. Н.
   О непрерывности линейных форм / Волков М. С. А., Гордеев Э. Н. // Безопасные информационные технологии (БИТ – 2023) : материалы 12-ой Международной научно-технической конференции, посвященнойя 25-летию кафедры ИУ8, Москва, 1-2 ноября 2023 года / МГТУ им. Н. Э. Баумана (национальный исследовательский университет). - М., 2024. - С. 16-20.

Рассмотрены линейные формы с переменными, принимающими целые неотрицательные значения. Внимание уделено свойствам области значений таких форм и различным критериям их непрерывности. Определены необходимые и достаточные условия непрерывности линейной формы с x ∈{0, 1, …, p}. Получены оценки числа непрерывных линейных форм заданной размерности с булевыми переменными. Найдены зависимости между числом разрывов области значений и коэффициентами линейной формы. Разработан алгоритм построения формы с заданным числом разрывов. Результаты могут представлять интерес для конструирования алгоритмов решения задач целочисленной оптимизации.
Ключевые слова: задача о рюкзаке, NP-полнота, непрерывность, линейная форма