Энтропийная скрытность

Размещено на http://www.allbest.ru

1. ЭНТРОПИЙНАЯ СКРЫТНОСТЬ

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

,

Все необходимые вычисления проведем в программе Mathcad, где и представим полученные результаты листинг программы рис.1.

В соответствии с заданием будем выполнять вариант № 13.

Заданное распределение вероятностей имеет вид:

,

Рисунок 1.

Определим среднее значение и дисперсию случайной величины i.

Среднее значение будет равно:

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

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

Определим среднее значение и дисперсию случайной величины i. Рассчитаем энтропийную скрытность множества состояний. Определим энтропийную скрытность с тем же арсеналом А, с равномерным распределением вероятностей состояний вида:

,

Равномерное распределение вероятностей:

Энтропия: множества состояний равномерного распределения будет равна:

Рисунок 2

Сравнивая полученные значения, можно сделать вывод, что энтропия заданного по варианту распределения меньше энтропии равномерного распределения.

2. ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК

Для заданного распределения вероятностей определите алгоритмическую скрытность состояний объекта для показанного на рис. 3а. дерева поиска. Проведите аналогичный расчет для дерева поиска на рис. 3б. Повторите эти расчеты для равномерного распределения вероятностей

Рисунок 3.

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

Длины l_i ветвей дерева поиска и вероятности p_i их появления приведены в таблице 1.

Таблица 1

Тогда алгоритмическая скрытность равна:

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

Таблица 2

Алгоритмическая скрытность равна:

Определим алгоритмическую скрытность состояний объекта равномерного распределения вероятностей для показанного ряда рис. 3а и 3б деревьев поиска. Исходные данные приведены в таблице 3.

Таблица 3

Алгоритмическую скрытность состояний объекта равномерного распределения вероятностей будет равна:

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

Для заданного распределения вероятности определим и построим графически дерево писка для оптимального последовательного алгоритма (состояния объекта проверяются последовательно по мере уменьшения их вероятностей). Вычислим соответствующую ему алгоритмическую скрытность (рис. 4 , таблица 4)

Таблица 4

Алгоритмическая скрытность для оптимального последовательного алгоритма

3. ДИХОТОМИЧЕСКИЙ ПОИСК

Для заданного в соответствии с вариантом распределения вероятностей определим скрытность при дихотомическом поиске, дерево которого показано на рис. 5. Дерево поиска на рис.5а соответствует случаю, когда , - целое число (в примере ), а если это условие не выполняется, то дерево поиска имеет вид, показанный на рис. 5б (в примере ).

Рисунок 5

При этом же значении определим скрытность для равномерного распределения вероятностей (1) и проанализируем результаты

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

Длины всех ветвей дерева поиска при дихотомическом поиске одинаковы и равны /. Определим скрытность при дихотомическом поиске. Длины ветвей дерева поиска, изображенного на рис. 4а и вероятности их появление приведены таблице 5

Таблица 5

тогда алгоритмическая скрытность равна:

При этом же значении определим скрытность для равномерного распределения вероятностей (1) и проанализируем результаты. Исходные данные приведены в таблице 6

Таблица 6

Скрытность для равномерного распределения вероятностей равна:

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

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

4. ОПТИМИЗАЦИЯ ПОИСКА

Методом Циммермана - Хаффмена для заданного значения арсенала построим оптимальное дерево поиска и рассчитаем потенциальную скрытность для равномерного распределения вероятностей состояний объекта (1). Выполним это же задание методом Шеннона - Фано, сравним полученные деревья поиска.

Проведем аналогичные расчеты для равномерного (1) распределения вероятностей . Сравним результаты, сделаем выводы.

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

4.1 Метод Циммермана - Хаффмена

Дерево поиска строится следующим образом.

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

Минимальные вероятности имеют состояния с номерами 1 и 2. Объединяя их в одно эквивалентное событие, получим новое множество состояний с вероятностями, приведенными в таблице 7.

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

Таблица 7

Полученные результаты позволяют построить дерево поиска, показанное на рисунке 6

Для оптимального дерева поиска значение потенциальной скрытности равно

4.2 Метод Шеннона-Фано

Исходное множество состояний объекта с заданным распределением их вероятностей разбивается на два подмножества и так, чтобы вероятности попадания в них были максимально близки (равны по 0,5). Затем каждое из полученных подмножеств и отдельно разбивается на два подмножества , и , соответственно, так, чтобы апостериорные вероятности нахождения в них реасобытия были бы максимально близки (равны по 0,5). Разбиение заканчивается, когда все подмножества будут иметь только по одному элементу.

Множество можно разбить на два подмножества и с вероятностями нахождение в них реасобытия, равными 0,5. Апостериорные (после первого двоичного измерения) вероятности состояний в множестве в соответствии с формулой Байеса приведены в таблице 8.

Таблица 8

Апостериорные вероятности состояний во втором множестве приведены в таблице 9.

Таблица 9

Множество можно разбить на два подмножества и . В результате получим дерево поиска, показанное на рис.7, соответствующее значение потенциальной скрытности равно:

.

Рисунок 7

ЗАКЛЮЧЕНИЕ

Как видно методы Циммермана-Хаффмена и Шеннона-Фано приводят к различным алгоритмам поиска, однако соответствующие им потенциальной скрытности приближенно равны и погрешность будет уменьшаться с ростом арсенала событий объекта.

Полученные деревья поиска похожи, но для метода Циммермана-Хаффмена оно имеет более оптимальный вид. Это позволяет получить минимальное значение скрытности и более эффективный алгоритм. Применение указанных методов к равномерному распределению дает дерево и результат дихотомического поиска, как предельного случая.

Сравнивая результаты, получим метод Циммермана-Хаффмена, как самый эффективный в данном случае, аналогичные по результату, хоть и чуть мене оптимальные - метод оптимизированного последовательного поиска и метод Шеннона-Фано.

ЛИТЕРАТУРА:

1. Литвиненко В.П. Основы теории скрытности: практикум: учеб. пособие / В.П. Литвиненко. Воронеж: ГОУВПО «Воронежский государственный технический университет», 2010. 106 с.

2. Основы теории скрытности: учеб. пособие / З.М. Каневский, В.П. Литвиненко, Г.В. Макаров, Д.А. Максимов. Воронеж: ВГТУ, 2006. 202с.

3. Программа, контрольные задания и методические указания по дисциплине «Основы теории скрытности» для студентов специальности 20302 «Радиотехника» ускоренной очно-заочной формы обучения / ГОУВПО «Воронежский государственный технический университет»; сост. В.П. Литвиненко. Воронеж, 2007, 27 с.

Размещено на Allbest.ru