Вероятностные автоматы и марковские цепи

Вероятностный автомат (P- схема) - это конечный автомат, в котором закономерности смены состояний и формирования выходного сигнала имеют статистический характер [22, 29].

Пусть заданы множество входных сигналов автомата X размерностью J, множество состояний Z размерностью I и множество выходных сигналов Y размерностью L. Введем новое множество G, элементами которого являются пары x_jz_i, и новое множество Ф, элементами которого являются пары z_iy_l. Очевидно, множество G будет иметь размерность K=IJ, а множество Ф - размерность S=IL.

Для вероятностного автомата любой элемент множества G индуцирует на множестве Ф дискретный закон распределения (p_{k 1}, p_{k 2},…, p_kS). Автомат может быть задан совокупностью

P= á G, Ф, В ñ = á X, Z, Y, В ñ, (2.10)

где B= ║ p_ks ║- матрица переходных вероятностей размерностью K×S. Элементы матрицы B должны отвечать следующим условиям:

0 ≤ p_ks≤ 1, k = 1,2,..., K; s = 1,2,..., S;

, k = 1,2,..., K.

Вместо матрицы B может быть задана таблица переходных вероятностей. Строки матрицы B и таблицы переходных вероятностей соответствуют элементам множества G,столбцы - элементам множества Ф.

Таким образом, если в детерминированном автомате заданной последовательности входных сигналов x (1), x (2),…, x (n) будет соответствовать определенная жесткая последовательность выходных сигналов y (1), y (2),…, y (n), то в вероятностном автомате такая последовательность формируется случайным образом. Вероятности реализации ее возможных вариантов могут быть рассчитаны на основе матрицы B.

Рассмотренные формы описания соответствуют наиболее общему случаю вероятностного автомата. Частные случаи вероятностных автоматов соответствуют рассмотренным выше видам конечных автоматов.

1. Вероятностный автомат Мили может быть задан таблицей переходов (табл. 4) и таблицей выходов (табл. 5), элементы которых должны удовлетворять следующим требованиям:

, , k= 1,2,..., K; K=IJ;

q_kir_kl=p_ks, s= (i, l), i= 1,2,..., I; l= 1,2,..., L; k= 1,2,..., K.

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

Таблица 4

Таблица 5

Таблица переходов

Таблица выходов

G

z 1

...

zi

...

zI

G

y 1

...

yl

...

yL

g 1= x 1 z 1

q 11

...

q 1 i

...

q 1 I

g 1 =x 1 z 1

r 11

...

r 1 l

...

r1L

...

...

...

...

...

...

...

...

...

...

...

...

gk = xjzi'

qk 1

...

qki

...

qkI

gk=xjzi

rk 1

...

rkl

...

rkL

...

...

...

...

...

...

...

...

...

...

...

...

gK = xJzI

qK 1

...

qKi

...

qKI

gK=xJzI

rK 1

...

rKl

...

rKL

Частными случаями всех видов вероятностных автоматов являются Z -детерминированные и Y -детерминированные автоматы. Рассмотрим их на примере автомата Мили.

В Z -детерминированном автомате функция переходов j является детерминированной, а функция выходов - статистической. Функция переходов для него может быть задана табл. 1 переходов, матрицей соединений С или графом (рис.12, б). Законы распределения выходных сигналов задаются матрицей переходных вероятностей B размерностью KL или соответствующей таблицей.

В Y -детерминированном автомате функция выходов y является детерминированной, а функция переходов - статистической. Функция выходов здесь может быть задана вектором выходов Y, а законы распределения новых состояний - матрицей переходных вероятностей B размерностью KI.

2. Вероятностный автомат Мура задается таблицей переходов (табл. 4) и таблицей выходов (табл. 6), построенной в предположении, что распределение вероятностей выходных сигналов зависит только от состояния автомата. Элементы таблиц должны отвечать следующим требованиям:

, k= 1,2,..., K; K=IJ;

, i= 1,2,..., I;

q_kiv_il=p_ks, s= (i,l); i= 1,2,..., I; l= 1,2,..., L; k= 1,2,..., K.

3. Автономный вероятностный автомат удобнее всего рассматривать и задавать как частный случай вероятностного автомата Мура при условии эквивалентности множеств G и Z. Наибольшее практическое использование получил Y -детерминированный автономный автомат, задаваемый матрицей переходных вероятностей:

-

вектором Y или графом (например, рис. 13). Вершины графа соответствуют состояниям автомата, дуги - возможным переходам. Около дуг указываются соответствующие переходные вероятности, около вершин - формируемые выходные сигналы. Модель в форме такого автомата называется также дискретной марковской цепью.

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

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

Предположим, что алгоритм УУ допускает формализацию в виде автомата без памяти F= á X, Y,yñ, и функция выходов y представлена в виде вектора размерностью J:

, (2.11)

где y_lj - элементы выходного алфавита Y= (y ₁, y ₂,…, y_L), то есть меры обеспечения безопасности, предусмотренные алгоритмом УУ для различных x_j.

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

Предположим, что в текущей ситуации применения системы присутствуют два угрожающих фактора внешней среды Ц₁ и Ц₂, причем Ц₁ является наиболее опасным и его нейтрализация должна обеспечиваться в первую очередь. Обозначим во входном алфавите как x ₁ элемент, соответствующий наличию фактора Ц₁. Выделим в выходном алфавите три элемента:

y ₁ - решение УУ о нейтрализации фактора Ц₁ - таким будет выходной сигнал детерминированного автомата при поступлении входного сигнала x ₁;

y ₂ - решение УУ о нейтрализации фактора Ц₂;

y ₃ - отсутствие мер обеспечения безопасности объекта.

Пусть и - вероятности обнаружения и правильного определения характеристик соответственно Ц₁ и Ц₂ устройствами информационной подсистемы. Тогда распределение вероятностей выходных сигналов вероятностного автомата будет следующим:

,

,

,

, 3 < l ≤ L.

Нетрудно убедиться, что . Аналогично могут быть получены распределения вероятностей возможных решений УУ для всех предусмотренных его алгоритмом ситуаций, которые и составят матрицу, задающую вместе с множествами X и Y модель информационной подсистемы в форме вероятностного автомата без памяти:

, (2.12)

где p_jl - вероятность формирования выходного сигнала y_l при поступлении входного сигнала x_j.

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

Дата добавления: 2015-11-04