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

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

4.3. Количество информации в результате одного двоичного измерения, декремент неопределенности

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

Если исходная (априорная) энтропия равна H (X ) , то после измерения и принятия решения y о наличии реасобытия в

выбранном подмножестве апостериорная (послеопытная) условная энтропия равна

Например, если при A 8 исходное распределение вероятностей равномерно (рис. 4.1а) и первое безошибочное измерение выявляет наличие реасобытия в подмножестве

29

ностей принимает вид рис. 4.1б и определяется по формуле

В рассматриваемом случае исходная неопределенность H(X ) 3 бита, а после измерения условная энтропия

равна H ( X / X 1(1) ) 2 бита. Как видно, после первого измерения неопределен-

Рис.4.1 ность состояния объекта уменьшилась на 1 бит.

После n-го двоичного измерения реасобытие обнаруживается в одном из подмножеств X 1(n,q) или X 2(n,q) , вероятности этого соответственно равны

На рис. 4.2 показан фрагмент дерева поиска для рассмотренного двоичного измерения. При этом поступающая информация снижает условную неопределенность состояния объекта на величину H , определяемую выражением

Рис. 4.2

30

H [ p log2 p (1 p) log2 (1 p)]. (4.11)

Назовем эту величину локальным декрементом неопреде-

ленности данного двоичного измерения.

На рис. 4.3 приведена вычисленная по формуле (4.11) за-

наиболее информативно двоичное измерение, для которого условные вероятности нахождения реасобытия в

Рис. 4.3 каждом из подмножеств одинаковы и равны 0,5.

Это обстоятельство необходимо иметь в виду при планировании и оптимизации поисковых процедур по критерию максимума декремента неопределенности при каждом следующем двоичном измерении.

4.4. Связь между неопределенностью состояний (энтропией) и потенциальной скрытностью

Задачей поисковой процедуры является снятие неопределенности H (X ) относительно текущего состояния. После ка-

ждого двоичного измерения неопределенность уменьшается на величину H (4.11).

Допустим, что поиск организован таким образом, что величина H при каждом шаге максимальна и равна H =1. При этом исходная неопределенность снизится до нуля при минимальном числе диз S, равном

31

ся при безошибочных измерениях и симметричном (гл.2) множестве возможных состояний объекта. Можно доказать, что в общем случае минимально необходимое число диз может превышать значение (4.12), но не более, чем на единицу

В дальнейшем будем пользоваться в качестве нижней оценки потенциальной скрытности при H(X ) 1 нижней границей (4.13),

Вычисляемую по формуле (4.13) скрытность будем назы-

вать энтропийной.

4.5. Баланс неопределенностей

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

Рассмотрим пример с показанным на рис.4.4 деревом поиска. Первое измерение проверяет эле-

и может быть существенно больше единицы. Вероятность та-

и эта величина не более единицы, что полностью соответствует полученным ранее результатам.

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

сумма частных декрементов неопределенности H n (xr ) по

всем n -м измерениям, n 1,lr , lr - длина соответствующей ветви дерева поиска для заданного реасобытия, равна исходной энтропии H (X ) ,

n 1

Умножая обе части равенства (4.18) на P(xr ) и суммируя

по всем реасобытиям, получим

33

A lr

r 1 n 1

Назовем статистическим декрементом неопределенности произведение

Величина (4.19) равна удельному вкладу результата n -го двоичного измерения при реасобытии xr в снижении неопре-

деленности до нулевого уровня в конце поиска. Тогда получим

A lr

r 1 n 1

Соотношения (4.17), (4.18) и (4.20) назовем балансом неопределенностей. Из них видно, что в процессе поиска неопределенность о состоянии объекта постепенно снижается, а поисковая система получает порции информации в ходе каждого двоичного измерения.

Академик А.А.Харкевич в одной из своих работ высказал предположение о существовании некоего объективного закона сохранения информации в природе, подобного другим законам сохранения. Баланс неопределенностей можно рассматривать, как один из вариантов его проявления.

34

5. МИНИМИЗАЦИИ ПРОДОЛЖИТЕЛЬНОСТИ ДВОИЧНОЙ ПОИСКОВОЙ ПРОЦЕДУРЫ

5.1. Двоичная индексация узлов дерева поиска

Будем пользоваться следующими правилами обозначения (адресации) узлов на дереве поиска (рис. 5.1).

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

Рис. 5.1 ла 0, смещенный вправо – добавлением символа 1, и так

далее.

В такой постановке получим дерево, в котором число разрядов в индексе финального узла указывает на его расстояние в диз’ах относительно корня дерева или, иначе гово-

ря, длину ветви li , i 1, A, от корня до данного узла.

5.2. Минимальное среднее число двоичных измерений

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

где Pi - вероятность состояния xi , а li - число измерений для

его выявления.

Представим закон распределения вероятностей состояний

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

Длины всех ветвей дерева поиска ограничены и существует такая величина l0 , для которой

Дополним двоичные коды ветвей всеми возможными комбинациями символов 0 и 1 до длины l0 , то есть добавим к

коду каждой ветви ki l0 li элементов. Тогда к дереву поиска всего будет добавлено

дополнительных ветвей, а их общее число не может быть больше 2l0 . С учетом (5.4) получим важное неравенство

A

i 1

которое устанавливает связь между длинами ветвей дерева и является условием реализуемости алгоритма поиска. Подобное соотношение известно в теории информации [3] как нера-

36

венство Крафта.

Тогда задачу минимизации алгоритмической скрытности

(5.1), то есть определения потенциальной скрытности объек-

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

Это классическая задача минимизации функции (5.6) при ограничениях типа неравенств (5.7) и (5.8), являющихся регулярными (задача имеет решение), если обеспечивается выполнение условия

Для минимизации алгоритмической скрытности целесообразно использовать известный в теории выпуклого программирования метод неопределенных множителей Лагранжа [4]. Решение задачи приведено в [1], где показано, что значение S равно

где m - наибольшее целое число, удовлетворяющее неравенству

37

m

Pi

PA - наименьшая из вероятностей состояний объекта.

В результате длины ветвей дерева поиска определяются выражениями

Как видно, в рассматриваемом случае минимальное значение алгоритмической скрытности (потенциальная скрытность) равно энтропии состояний объекта и его энтропийной

38