УДК 004.5:519.854.33
А. И. О в ч и н н и к о в, Н. В. М е д в е д е в,
А. Ю. Б ы к о в
ПРИМЕНЕНИЕ МЕТОДА ВЕКТОРА СПАДА
ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПОИСКА ВАРИАНТОВ
ЗАЩИТЫ ОТ УГРОЗ БЕЗОПАСНОСТИ
ВЫЧИСЛИТЕЛЬНОЙ СЕТИ ПРЕДПРИЯТИЯ
Рассмотрена возможность применения метода вектора спада к
решению задачи выбора вариантов защиты от угроз безопасности
вычислительной сети предприятия. Решаемая задача представля-
ет собой задачу булева программирования с нелинейными ограни-
чениями, которая не допускает построения эффективныхприбли-
женныхалгоритмов в том смысле, что получение приближенного
решения с заданной оценкой точности столь же сложно, как и
получение точного решения. Реализация алгоритма метода выпол-
нена на языке Java. Проведены анализ быстродействия алгоритма
и оценка точности полученныхрешений.
Исключительно важную роль в решении задач дискретного про-
граммирования играют приближенные методы. Можно указать обсто-
ятельства, которые вызывают необходимость разработки приближен-
ных методов дискретного программирования.
Во-первых, из-за комбинаторного характера большинства задач
дискретного программирования и большой трудоемкости их решения
точные методы не дают возможности получить оптимальное решение
для практических задач довольно большой размерности за приемле-
мое время.
Во-вторых, часто на практике для задач исследования операций
применяются приближенные модели, где исходные данные определя-
ются неточно и приближенно. Это обесценивает поиск оптимальных
решений, и потому часто ограничиваются приближенными решения-
ми, удовлетворительными с точки зрения практики. На их поиск рас-
ходуется значительно меньше машинного времени и других ресурсов
ЭВМ, что особенно важно, если соответствующие задачи должны ре-
шаться в реальном времени (например, в условиях функционирова-
ния АСУ).
Особенность задачи оптимального выбора вариантов защиты от
угрозбезопасности вычислительной сети, как и многих других за-
дач дискретной оптимизации, то, что она является NP-полной задачей
[1, 2], т.е. невозможно получить точное решение за время, значение
которого является полиномом от размерности задачи. Поэтому име-
ет смысл рассмотреть приближенные методы, которые используются
в тех случаях, когда необходимо обеспечить оперативность решения
задачи или когда размерность задачи велика.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 2 73
