Использование радиуса устойчивости оптимизационных задач для скрытия и проверки …
1
УДК 004.056:519.854
Использование радиуса устойчивости
оптимизационных задач для скрытия и проверки
корректности информации
© Э.Н. Гордеев
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
Рассматриваются возможности применения теории устойчивости оптимиза-
ционных задач для скрытия информации и проверки корректности получаемой
информации при передаче ее по открытым каналам. Для этого используется
связь между исследованием устойчивости решений дискретных экстремальных
задач и методами решения обратных задач. (В обратной задаче требуется по-
строить условие задачи на основе заданного решения или множества решений.)
Приводится общее описание двух методов, а также дается краткое описание
некоторых результатов теории устойчивости, на основе которых описанные
методы могут быть реализованы. Первый подход базируется непосредственно
на связи методов решения обратных задач и результатов теории устойчивости.
Второй подход посвящен возможностям восстановления искаженной информа-
ции на основе знания радиуса устойчивости некоторой дискретной экстремаль-
ной задачи.
Ключевые слова:
дискретная оптимизация, радиус устойчивости, обратная зада-
ча, восстановление информации.
Введение.
В работах [1–7] рассматривались различные подходы к
исследованию устойчивости в задачах дискретной оптимизации.
Суть их состоит в следующем.
Рассматривается класс задач дискретной оптимизации, который
описывается следующей моделью. Пусть
E
= (
e
1
, ...,
e
n
) – некоторое
множество,
D
n
=
m
m
, – система подмножеств множества
E
, называемых траекториями. Характеристический вектор траекто-
рии
будем обозначать через
H
h
h
n
), т. е.
1,
;
( )
0,
.
i
i
i
e
h
e
Элементам из E приписаны веса
w
(
e
1
) =
a
1
, ...,
w
(
e
n
) =
a
n
. И пусть
вектор
A
= (
a
1
, ...,
a
n
), берется из
R
n
. На каждой траектории определя-
ется функционал
– длина траектории при взвешивании
A
. Функ-
ционал может быть задан различными способами, наиболее извест-
ные из которых – линейный функционал:
( )
i
i
e
A a
(1)
