Исследование алгоритма последовательного поиска

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО

ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

"ВОРОНЕЖСКИЙ  ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ"

(ГОУВПО "ВГТУ")

ФАКУЛЬТЕТ РАДИОТЕХНИКИ И ЭЛЕКТРОНИКИ

 

Специальность "210400 Радиотехника"

 

 

 

 

Отчет по лабораторной работе № 3

по дисциплине: “ОСНОВЫ ТЕОРИИ СКРЫТНОСТИ”

Тема лабораторной работы: «ИССЛЕДОВАНИЕ АЛГОРИТМА ПОСЛЕДОВАТЕЛЬНОГО ПОИСКА»

 

 

 

 

 

Выполнил  студент: группы РТ-111

Курганский  А. Е.

Проверил: Литвиненко В. П.

 

 

Защищен  ___________________                   Оценка______________________

                               (дата)

 

Воронеж 2013

Содержание

 

Введение……………………………………………………………………….

1    Исследование алгоритма поиска  «m=n» при равномерном распределении………………………………………………………………….

2 Исследование  алгоритма поиска «m=А-n+1» при  равномерном распределении…………………………………………………………………

3   Последовательный поиск при экспоненциальном  распределении……

4   Исследование последовательного поиска при случайном распределении……………………………………………………………….

Заключение……………………………………………………………………….

Приложение А Листинг программ………………………………………………

 

Введение

 

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

Вариант работы - № 12.

 

1 Исследование алгоритма поиска «m = n» при равномерном распределении

 

В программе  Poisk было установлено равномерное распределение вероятностей событий при их числе А = 8. Был задан полный алгоритм поиска «m = n», при котором номер события m равен номеру измерения n (при этом не проверяется последнее событие). Дерево поиска представлено на рис. 1а.

 

     а)                              б)                           в)                               г)

 

Рисунок 1 – Деревья последовательного поиска

 

 Результаты  моделирования изображены на рис. 2 в виде скриншота окна программы «Poisk». В табл. 1 занесено полученное значение скрытности – R₀.

 

 

Рисунок 2 - Моделирование последовательного поиска (алгоритм «m = n» без проверки последнего события при равномерном распределении вероятностей)

 

Таблица 1 – Алгоритмические скрытности при равномерном распределении 

	R0, диз	R1, диз	R2, диз	R3, диз
Моделирование	4.375	4.5	4.375	4.5
Расчет	4.375	4.5	4.375	4.5

 

При проверке последнего события было проведено  аналогичное моделирование процесса последовательного поиска. Результаты моделирования изображены на рис. 3, а полученное значение скрытности – R₁  внесено в табл. 1. Дерево поиска для такого алгоритма представлено на рис. 1б.

 

Рисунок 3 - Моделирование последовательного поиска (алгоритм «m = n» с проверкой последнего события при равномерном распределении вероятностей)

 

Скрытность определяется средним числом двоичных измерений. Таким образом, при проверке последнего события и полном алгоритме поиска скрытность скрытность должна быть выше. Моделирование позволило подтвердить данную мысль. Поледнее измерение является холостым с точки зрения извлечения количества информации, что подтверждают графики кривых снятия неопределенности для последовательного поиска (m=n) без проверки последнего события и для того же алгоритма с проверкой последнего события. Остаточная энтропия равна нулю уже при предпоследнем номере события арсенала. Если же добавить ко всему одно  холостое измерение, то данный факт лишь повлияет на общее число измерений и, как следствие, увеличит скрытность, поэтому .

Скрытности  полученные в результате моделирования () можно рассчитать, воспользовавшись формулами (1) и (2) соответственно

 

 

 

 

 

где 

 

            .

 

Таким образом, получаем:

 

 

 

 

 

Рассчет величин алгоритмических скрытностейподтверждает моделирование

 

 

 

 

 

 

2 Исследование алгоритма поиска «m = А – n + 1» при равномерном распределении

 

Алгоритм  поиска «m = А – n + 1» при арсенале из восьми событий абсолютно аналогичен алгоритму «m = n», но проверка событий начинается с последнего и заканчивается вторым. Результаты моделирования приведены на рис. 4. Полученное значение скрытности – R₂ внесено в табл. 1,  а дерево поиска представлено на рис. 1в.

 

 

Рисунок 4 –  Моделирование алгоритма последовательного  поиска «m = A – n + 1» без проверки первого  события при равномерном распределении  вероятностей

 

Аналогичное моделирование было так же проведено  и для случая с тем  же алгоритмом «m = А – n + 1», арсеналом из  восьми событий и проверкой событий  начинается с последнего, а заканчивается  первым. Результаты моделирования приведены  на рис. 5. Полученное значение скрытности – R₃ внесено в табл. 1,  а дерево поиска представлено на рис. 1г.

 

 

Рисунок 5 – Моделирование алгоритма последовательного  поиска «m = A – n + 1» с проверкой  первого события при равномерном  распределении вероятностей

 

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

 

    

Скрытности  полученные в результате моделирования () можно рассчитать, воспользовавшись формулами (5) и (6) соответственно

 

 

 

 

 

где 

 

            .

 

Таким образом, получаем:

 

 

 

 

 

Рассчет величин алгоритмических скрытностейподтверждает моделирование

 

 

 

 

 

 

3 Моделирование  последовательного поиска при экспоненциальном распределении

 

Для арсенала из восьми событий было установлено распределение вероятностей вида:

 

                    

где B – нормирующий множитель;

.

 

Результаты моделирования представлены на рис. 6, а значение скрытности – R₄ внесено в табл. 2. Дерево поиска изображено на рис. 1а.

 

 

Рисунок 6 – Моделирование алгоритма поиска «m = n» при экспоненциальном рапределении вероятностей

Таблица 2 – Алгоритмичекие скрытности при экспоненциальном распределении

	R5	R6
Моделирование	1,9647	6,5294
Расчет

 

Результаты  моделирования алгоритма поиска «m = А – n + 1» представлены на рис. 7, а значение скрытности – R₆ внесено в табл. 2. Дерево поиска изображено на рис. 1в.

 

 

Рисунок 7 - Моделирование алгоритма поиска «m = А – n + 1» при экспоненциальном рапределении вероятностей

 

Для экспоненциального  распределения вероятности, последовательный алгоритм (m = A – n +1) является наименее приемлемым сточки зрения обнаружения, потому что при заданном алгоритме поиска, первые проверяемые состояния ( ) оказываются наименее вероятными. Для алгоритма (m = n) картина складывается куда более благоприятная. В таком случае, напротив проверяются сначала наиболее вероятные места пребывания реасостояния (), что с точки зрения самой скрытности, повышает шансы найти реасостояния в первые циклы проверки и понижает саму меру скрытности. Таким, образом эффективность алгоритма (m = n) и неэффективность алгоритма (m = A – n +1) подтверждают результаты, занесенные в табл.2

 

,       

 

3,3234  раза

 

Среднее число двоичных измерений при экспоненциальном распределении вероятности и алгоритме (m = n) в 3,3234  раза меньше числа двоичных измерений при алгоритме (m = A – n + 1). Это говорит о том, что последовательный поиск при (m = n) эффективней поиска при (m = A – n +1) в 3,3234  раза.

Такие же результаты можно получить, если воспользоваться  формулами 6 и 7 для расчета алгоритмической скрытности при алгоритмах поиска «m=n» и «m=A-n+1» соответственно.

 

 

 

 

 

Значения  скрытностей, полученных с помощью  моделирования и в процессе расчета, совпадают.

 

 

1.4 Исследование алгоритма последовательного поиска при случайном распределении

 

В соответствии с вариантом было выбрано распределение  вероятностей в программе «Poisk» под номером семь, число событий арсенала – четыре (А=4). Результат моделирования алгоритма последовательного алгоритма поиска «m=n» изображен на рис. 1.7, значение скрытности внесено в табл. 1.3. Дерево поиска представлено на рис. 1.8а.

 

Рисунок 1.7 -  Моделирование алгоритма поиска «m=n» при рапределении вероятностей под номером семь

 

Таблица 1.3 – Алгоритмические скрытности при распределении под номером  семь

R6	R7	R8	R9
2.3	4.73	6.33	8.02

 

 

а)  б)  в)  г)

Рисунок 1.8 –  Деревья поиска для последовательного  алгоритма

 

Кривая  снятия неопределенности на рис. 1.7 говорит  о том, что алгоритм поиска отличается от оптимального. Это связано с  тем, что проверка событий такого распределения в порядке убывания номера не приводит к тому, что события  проверяются в порядке убывания вероятности их реализации. Правильнее было бы проверять события в соотвтствии  с деревом поиска, изображенным на рис. 1.9. Результат моделирования такого алгоритма представлен на рис. 1.10.

 

Рисунок 1.9 –  Оптимальный алгоритм последовательного  поиска для распределения под номером семь

 

Рисунок 1.10 – Моделирование оптимального алгоритма  поиска для распределения под  номером семь

 

Как видно  из рис. 1.10 кривая снятия неопределенности для последовательного алгоритма поиска с деревом, изображеным на рис. 1.9, совпадает с оптимальной кривой снятия неопределенности для заданного распределения.

 

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

Рисунок 1.11 - Моделирование алгоритма поиска для распределения под номером  семь и арсенала из восьми событий

 

Рисунок 1.12 - Моделирование алгоритма поиска для распределения под номером  семь и арсенала из двенадцати событий

Рисунок 1.13 - Моделирование алгоритма поиска для распределения под номером  семь и арсенала из шестнадцати событий

 

При увеличении арсенала событий значение скрытности увеличивается, так как число  измерений напрямую связано с  числом событий арсенала при последовательном поиске. При хаотичном распределении  вероятностей случайных событий  алгоритм поиска «m=n» не является оптмальным. Это иллюстрируют рис. 1.11 – 1.13, на которых кривые снятия неопределенности, полученные в результате моделирования отличаются от оптимальных.