Оптимизация алгоритмов поиска.

ВВЕДЕНИЕ



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

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

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

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

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

1. Основы теории скрытности: учебное пособие для студентов специальности 200700 «Радиотехника» дневной формы обучения / Воронежский государственный технический университет; Сост.З.М. Каневский, В.П. Литвиненко, Г.В. Макаров, Д.А. Максимов; под редакцией З.М. Каневского. Воронеж, 2006. 202с.

2. Методические указания к лабораторным работам «Исследование алгоритмов поиска» по дисциплине «Основы теории скрытности» для студентов специальности 200700 «Радиотехника» дневной форм7 обучения / Воронежский государственный технический университет; сост.З.М. Каневский, В.П. Литвиненко. Воронеж, 2007.54с.

3. СТП ВГТУ 005-2007. Курсовое проектирование. Организация, порядок, оформление расчетно-пояснительной записки и графической части.