10. Расчеты при выполнении

ЛАБОРАТОРНЫХ РАБОТ

10.1. Лабораторная работа №1: «Алгоритмическая

скрытность»

Пусть задано распределение вероятностей состояний объектов , при ,

(10.1)

Расчет и графическое представление распределения вероятностей показаны в программе на рис. 10.1.

Рис. 10.1

71

Определим алгоритмическую скрытность для алгоритма последовательного поиска, дерево которого показано на рис. 10.2а,

, (10.2)

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

(10.3)

Рис. 10.2

Расчет проведен в программе на рис. 10.1 и .

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

. (10.4)

72

В результате получим (рис. 10.1). Сравните полученные результаты.

Для равномерного распределения вероятностей

(10.5)

алгоритмическая скрытность для дерева поиска на рис. 10.2а определяется из (10.2) при замене на , тогда получим . Для дерева поиска на рис. 10.2б расчет ведется аналогично по (10.4) и . Объясните эти результаты.

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

Рис. 10.3

10.2. Лабораторная работа №2: «Информационные

характеристики поиска»

Распределение вероятностей состояний объекта определяется (10.1), график показан на рис. 10.1.

73

Проведем расчет кривой снятия неопределенности (КСН) для алгоритма последовательного поиска, дерево которого показано на рис. 10.2а.

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

, (10.6)

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

(10.7)

Вероятность такого решения равна . Тогда для апостериорных вероятностей из (10.6) получим

(10.8)

Если принято решение об отсутствии реасобытия , то

(10.9)

и . Тогда для апостериорных вероятностей получим

74

(10.10)

Для апостериорных вероятностей после второго измерения можно записать формулу Байеса в виде

, (10.11)

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

Если принято решение о наличии реасобытия , то

(10.12)

Вероятность решения равна , тогда для апостериорных вероятностей получим

(10.13)

Для решения об отсутствии реасобытия

(10.14)

и . Тогда для апостериорных вероятностей получим

75

(10.15)

В общем случае после -го измерения, ,

, (10.16)

и для решения об обнаружении -го реасобытия

(10.17)

Вероятность появления решения равна , а апостериорные вероятности равны

(10.18)

Если в ходе -го измерения принято решение об отсутствии реасобытия, то

(10.19)

а вероятность принятия этого решения равна

. (10.20)

76

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

(10.21)

Рассмотрим алгоритм дихотомического поиска, его дерево поиска показано на рис. 10.3.

В ходе первого измерения множество состояний объекта разбивается на два подмножества и . Апостериорные вероятности определяются выражением (10.6).

Если принято решение о принадлежности реасобытия к подмножеству , то

(10.22)

а вероятность такого решения равна

. (10.23)

Для апостериорных вероятностей из (10.6) получим

(10.24)

77

Если принято решение о принадлежности реасобытия к подмножеству , то

(10.25)

. (10.26)

Для апостериорных вероятностей из (10.6) получим

(10.27)

Объединяя полученные результаты и введя обозначение

(10.28)

Получим

(10.29)

(проверьте это соотношение самостоятельно).

Коэффициент

(10.30)

78

равен 1, если значение совпадает со значением решения и равен 0 в противном случае. Тогда из (1029) запишем

(10.31)

В ходе второго измерения выявленное подмножество или разбивается на два подмножества , (при первом измерении принято решение ) или , (для ) соответственно.

Если приняты решения и о принадлежности реасобытия к подмножеству , то

(10.32)

и вероятность такого решения равна

. (10.33)

Апостериорные вероятности равны

(10.34)

Аналогично нетрудно получить выражения для апостериорных вероятностей состояний объекта при других наборах принятых решений

79

(10.35)

(10.36)

(10.37)

Введем обозначения

(10.38)

( - символ логического объединения – суммирования множеств) и

(10.39)

Для апостериорных вероятностей можно записать

(10.40)

80

После третьего и так далее -го двоичного измерения всего получится вариантов апостериорных вероятностей, которые определяются аналогично (10.34)-(10.37).

В общем случае для -го двоичного измерения получим

(10.41)

Программа расчета энтропийных характеристик последовательного и дихотомического поиска на основе выражений (10.24), (10.27) и (10.34)-(10.37) приведена в приложении 3. В приложении 4 представлена программа вычисления тех же характеристик дихотомического поиска на основе (10.41). Проведите их сравнительный анализ, напишите аналогичные программы на других языках высокого уровня.

Результаты расчета КСН для алгоритма последовательного поиска при распределении вероятностей (10.1) показаны на рис. 10.4.

Рис. 10.4

81

На рис. 10.5 показана КСН для дихотомического поиска при тех же условиях.

Рис. 10.5

10.3. Лабораторная работа №6: «Методы оптимизации

поиска»

Для распределения вероятностей состояний объектов , при ,

(10.42)

методом Шеннона-Фано постройте оптимальный алгоритм поиска.

По методу Шеннона-Фано при первом двоичном измерении множество состояний объекта разбивается на два подмножества и с предельно близкими между собой (равными 0,5) вероятностями нахождения в них реасобытия.

При втором измерении в каждом из подмножеств и вычисляются апостериорные вероятности нахождения реасобытия. Затем каждое подмножество разбивается на две части

82

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

В приложении 4 приведена программа, с помощью которой можно сформировать близкий к оптимальному алгоритм поиска.

В ходе первого измерения формируется массив (вектор) со значениями каждого из элементов 0 или 1 (0 - принадлежность состояния к одному подмножеству, а 1 – к другому). Изменяя значения этих символов, можно подобрать их так, чтобы суммарные вероятности стали одинаковыми. В табл. 10.1 приведены номера состояний в выбранных подмножествах. После двоичного измерения принимается решение о наличии реасобытия в подмножестве ( ) или ( ).

Таблица 10.1

1	3	5	7	9	13	15	2	4	6	8	10	11	12	14	16

На рис. 10.6 приведены апостериорные вероятности наличия реасобытия в подмножествах и соответственно.

Рис. 10.6

83

Далее процедура повторяется до тех пор, пока в каждом из подмножеств не окажется по одному элементу. Результаты расчета приведены в программе из приложения 4, там же представлены полученные разбиения подмножеств. Дерево поиска показано на рис. 10.7.

Рис. 10.7

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

. (10.43)

Рис. 10.8

84

Проверим условие практической реализуемости алгоритма поиска (программа в приложении 5)

. (10.44)

Равенство единице суммы (10.43) является косвенным свидетельством близости алгоритма поиска к оптимальному.

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

Энтропийная оценка потенциальной скрытности равна

, (10.45)

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

Определим оптимальный алгоритм поиска методом Циммермана-Хаффмена. Исходное распределение вероятностей состояний представлено в табл. 10.2 (первые два столбца).

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

85

Таблица 10.2

1	0,127	1	0,127	1	0,127
2	0,123	2	0,123	2	0,123
3	0,117	3	0,117	3	0,117
4	0,11	4	0,11	4	0,11
5	0,1	5	0,1	5	0,1
6	0,089	6	0,089	6	0,089
7	0,078	7	0,078	7	0,078
8	0,066	8	0,066	8	0,066
9	0,054	9	0,054	9	0,054
10	0,042	10	0,042	10	0,042
11	0,032	11	0,032	11	0,032
12	0,023	12	0,023	14,15,16	0,024
13	0,015	13	0,015	12	0,023
14	0,01	15,16	0,014	13	0,015
15	0,00735	14	0,01
16	0,00684

Таблица 10.3

1	0,127	1	0,127	1	0,127
2	0,123	2	0,123	2	0,123
3	0,117	3	0,117	3	0,117
4	0,11	4	0,11	4	0,11
5	0,1	5	0,1	5	0,1
6	0,089	6	0,089	6	0,089
7	0,078	7	0,078	10, 12,13	0,08
8	0,066	8	0,066	7	0,078
9	0,054	11, 14,15,16	0,056	8	0,066
10	0,042	9	0,054	11, 14,15,16	0,056
12,13	0,038	10	0,042	9	0,054
11	0,032	12,13	0,038
14,15,16	0,024

86

Таблица 10.4

1	0,127	7,8	0,143	6,10, 12,13	0,17
2	0,123	1	0,127	7,8	0,143
3	0,117	2	0,123	1	0,127
9,11, 14,15,16	0,11	3	0,117	2	0,123
4	0,11	9,11, 14,15,16	0,11	3	0,117
5	0,1	4	0,11	9,11, 14,15,16	0,11
6	0,089	5	0,1	4	0,11
10, 12,13	0,08	6	0,089	5	0,1
7	0,078	10, 12,13	0,08
8	0,066

Таблица 10.5

4,5	0,21	3,9,11, 14,15,16	0,227	1,2	0,25
6,10, 12,13	0,17	4,5	0,21	3,9,11, 14,15,16	0,227
7,8	0,143	6,10, 12,13	0,17	4,5	0,21
1	0,127	7,8	0,143	6,10, 12,13	0,17
2	0,123	1	0,127	7,8	0,143
3	0,117	2	0,123
9,11, 14,15,16	0,11

Таблица 10.6

6,7,8, 10, 12,13	0,313	3,4,5, 9,11, 14,15,16	0,437	1,2,6,7,8, 10, 12,13	0,563
1,2	0,25	6,7,8,10, 12,13	0,313	3,4,5, 9,11, 14,15,16	0,437
3,9,11, 14,15,16	0,227	1,2	0,25
4,5	0,21

87

Рис. 10.9

На рис. 10.10 показаны значения длин ветвей дерева поиска для алгоритма рис. 10.9. Как видно, имеются отличия от графика на рис. 10.8. Величина скрытности равна

, (10.46)

что меньше (10.43) и согласуется с (10.45)

Рис. 10.10

88

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

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