Материал: Теория скрытности. Часть 1, Основы теории скрытности. Каневский З.М., Литвиненко В.П

по дереву поиска.

Рассмотренное дерево поиска соответствует наиболее простому случаю отсутствия ошибок в каждом двоичном измерении. Если возникают ошибочные измерения, то в общем случае возможен возврат к ранее проверенным событиям. При этом дерево поиска усложняется, появляются новые варианты разбиения подмножеств и соответствующие им ветви, возможен возврат к ранее принятым решениям (появляются петли). Это приводит к удлинению ветвей дерева вплоть до бесконечности.

В целом дерево поиска является удобной геометрической интерпретацией алгоритма формирования финальных решений. С его помощью появляется возможность использования для анализа поисковых процедур современного аппарата теории графов.

2.3. Вероятности посещения узлов дерева поиска

Вероятности попадания поисковой процедуры в узел дерева поиска зависят от состава приписываемых узлам подмножеств и распределения вероятностей состояний объекта.

В состав корневого узла Х входят все элементы множества Х, определяемые числом исчерпывающих возможных несовместных состояний объекта xi . Так как по условию какое

либо из состояний всегда реализуется, вероятность посещения входного узла в соответствии с теоремой сложения вероятностей несовместимых событий равна

Вероятность попадания в узел, соответствующий подмножеству X ( N ,q ) равна

19

Например, вероятность посещения первого узла (N,q) при

N=1 q=1 (рис. 2.3) равна

а для альтернативного подмножества соответственно

20

Глава 3. ОПРЕДЕЛЕНИЕ СКРЫТНОСТИ И ЕЕ МЕРА

3.1. Подходы к определению скрытности

При оценке скрытности объекта используются два подхода. В первом (условно назовем его вероятностным) скрыт-

ность определяется как вероятность успешного выявления

реасобытия в заданное время. Однако это прежде всего мера успеха разведки, а не усилий, направленных на выявление состояния объекта. Кроме того, вероятностная мера скрытности неудобна численно, например, значения вероятностей успеха 0,94 и 0,99 близки, однако для их достижения могут потребоваться различные временные затраты.

Второй подход предполагает оценивать скрытность объ-

екта через затраты на выявление его состояния с заданной достоверностью (вероятностью правильного решения). Он точнее отражает существо термина «скрытность»; чем больше затраты, чем труднее выявить реасобытие, тем лучше оно «спрятано» от разведки. В дальнейшем оценку скрытности будем производить в рамках такого «затратного» подхода.

Таким образом при раскрытии неопределенности состояния объекта необходимо произвести соответствующие временные и аппаратные затраты.

Очевидно, что при использовании для каждого состояния своего отдельного устройства обнаружения (параллельное одновременное измерение) результат будет получен наиболее быстро, но при максимальных аппаратных затратах.

Если же использовать лишь один двоичный измеритель, то для выявления реасобытия необходимо организовать поисковую процедуру, последовательно перебирая подмножества состояний. В этом случае аппаратные затраты минимальны, но поиск требует соответствующего времени.

Теоретический анализ показывает, что параллельное и последовательное обнаружение реасобытия имеют общие

21

свойства и аппаратные затраты можно связать с временными и наоборот. Для обеспечения единообразия при оценке скрытности различных объектов целесообразно в качестве

базового выбрать поисковый алгоритм обнаружения реасобытия с одним двоичным измерителем.

3.2. Длина пути от корневого до финального узла дерева поиска

Переход от одного узла к другому по дереву поиска (рис. 3.1.) сопровождается одним двоичным измерением, которое будем сокращенно обозначать через ДИЗ. Его мы будем использовать также в качестве единицы оценки скрытности состояния объекта.

число двоичных измерений, необходимых для выявления реасобытия при заданном алгоритме поиска. Оно равно средней

22

длине ветвей l дерева поиска от корня к финальным узлам,

Алгоритмическая скрытность характеризует средние затраты в диз’ах на выявление реасобытия при заданном алгоритме поиска. В определении (3.1) полагается, что ошибки отсутствуют и все измерения имеют единичную стоимость независимо от порядка их выполнения в процедуре поиска.

3.4. Влияние алгоритма поиска

В минувшую мировую войну в США всех призывников проверяли на отсутствие венерических заболеваний посредством реакции Вассермана. Сначала исследовалась кровь каждого призывника в отдельности. Затем было предложено объединить их в группы, смешивать кровь и проверять ее целиком. Группы с общей отрицательной реакцией от дальнейших исследований в этом направлении освобождались. Экономичность второго пути очевидна.

Объединение проверяемых состояний в группы кроме медицины и технической диагностики, рассматривается также применительно к разведке сигналов в частотном диапазоне. На рис. 3.2а приведены результаты вычисления значений R( ) при двух алгоритмах поиска .

В первом алгоритме ( 1 ) производится последователь-

ный перебор состояний от первого до последнего, пока не встретится реасобытие. Дерево поиска показано на рис. 3.3а.

Второй алгоритм поиска ( 2 ) предполагает разделение

всего множества состояний пополам, проверку наличия реасобытия в каждой из этих частей, затем разделение выбранной половины множества X на две равные части с проверкой наличия в них реасобытия и так далее. Поиск заканчивается,

23

когда в выделенном подмножестве оказывается одно событие. Дерево поиска показано на рис. 3.3б.

Расчеты выполнены при равномерном распределении вероятностей состояний объекта.

Рис. 3.2

Рис. 3.3

На рис. 3.2б показана зависимость отношения

показывающего, в какой мере можно уменьшить среднее число двоичных измерений до раскрытия состояния объекта при алгоритме 2 по сравнению с 1 . Быстродействие поиска

возрастает в 200 раз при A 5000. Рассмотренный пример говорит о наличии значительных резервов в сокращении времени поиска за счет надлежащего выбора алгоритма.

24

3.5. Потенциальная скрытность

Назовем потенциальной скрытность S, численно равную минимально достижимому (минимум – миниморум по всем реализуемым алгоритмам поиска) среднему числу двоичных измерений, необходимому и достаточному для раскрытия всех возможных состояний объекта, определив ее равенством

Речь идет о согласованном с объектом алгоритме поиска, обеспечивающем искомый минимум зависимости R от K . В

ряде случаев может существовать несколько алгоритмов, эквивалентных в смысле (3.3).

Потенциальная скрытность является характеристикой собственно объекта исследования, его выраженным в числовой форме качеством, способностью противостоять выявлению текущего состояния. Потенциальная скрытность объекта не зависит от действий системы выявления его состояний, так как предполагает использование оптимального алгоритма поиска. Фактически она является наиболее «осторожной» оценкой скрытности.

Сравнение практически используемых алгоритмов поиска с потенциальным позволяет судить о степени их совершенства.

В ходе радиоэлектронной борьбы разведывательная система стремится выявить рабочие параметры системы радиосвязи, которая, в свою очередь, стремится затруднить разведку, управляя распределением вероятностей своих состояний.

Например, если система связи использует только часть частот из рабочего диапазона, то противник, установив это по результатам предшествующих наблюдений, будет именно там проводить поиск, снижая затраты времени. Тогда система связи должна изменять распределение вероятностей рабочих частот, затрудняя действия разведывательной системы, то

25

есть повышая свою скрытность. Можно установить распределение вероятностей рабочих параметров системы связи, при котором даже при оптимальных действиях противника его затраты на поиск будут максимально возможными.

Для решения этой задачи можно использовать понятие потенциальной скрытности. При выбранных параметрах системы связи определяется потенциальная скрытность и соответствующий оптимальный алгоритм поиска. Затем, изменяя параметры, определяются условия, при которых потенциальная скрытность максимальна.

В рассмотренном примере системы радиосвязи и разведки участвуют в игре, в которой каждая сторона стремится уменьшить потери и максимизировать свой выигрыш. Эти вопросы решаются в рамках математической теории игр.

26

Глава 4. ИРФОРМАЦИОННЫЕ АСПЕКТЫ ПОИСКОВОЙ ПРОЦЕДУРЫ

4.1.Неопределенность возможных состояний объекта, их энтропия

При анализе технических систем передачи сообщений широко используется теория информации, основоположником которой является К. Шеннон. Ее можно использовать и при исследовании свойств поисковых процедур.

Базовым понятием теории информации является энтропия. Она зависит от закона распределения вероятностей состояний Pi и определяется выражением

i1

иизмеряется в двоичных единицах – битах.

Энтропия является мерой неопределенности поступающих сообщений или состояний наблюдаемого объекта. Ее величина равна нулю, если одна из вероятностей Pi 1, а ос-

тальные равны нулю. Это означает, что объект всегда находится только в одном заранее известном состоянии xi и неоп-

ределенность его состояний отсутствует.

Энтропия максимальна при равновероятном распределе-

В этом случае нет оснований для предпочтительного ожидания какого-либо одного состояния объекта и обстановка наиболее неопределенная из всех других возможных.

27

4.2. О количестве информации в сообщении

Результат определения состояния объекта xi можно рассматривать как сообщение. Количество информации, заключенное в сообщении xi , зависит от его неожиданности или, иначе говоря, от его вероятности Pi . Чем меньше вероятность

состояния, тем больше информации приносит его выявление. Маловероятное сообщение из Сочи в июле, что там выпал снег, заключает в себе большее количество информации по сравнению с обычным, что там жарко. Теория информации оперирует не с самими вероятностями, а с их логарифмами.

Количество информации в одном передаваемом сообще-

и измеряется, как и энтропия, в битах. Знак минус обусловлен тем, что логарифм вероятности Pi 1 отрицателен, тогда ве-

личина I i оказывается положительной.

Среднее количество информации I(X ) в расчете на одно передаваемое сообщение из множества Х определяется матожиданием I i ,

Как видно, выражения (4.1) и (4.4) совпадают, то есть количество информации, содержащееся в состояниях объекта, равно их исходной неопределенности I (X ) H(X ) . Если со-

стояние xi заранее известно (его вероятность равна единице), то I (X ) 0 . Максимальное количество информации поступа-

28