Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по моделированию систем - файл P-схемы.doc


Загрузка...
Лекции по моделированию систем
скачать (1799.4 kb.)

Доступные файлы (18):

10_Псевдослучайные числа, процедуры их получения.doc127kb.31.03.2005 20:30скачать
11_Моделирование случайных воздействий.doc302kb.21.04.2005 22:59скачать
12_Приближенные способы преобразования.doc279kb.22.04.2005 01:52скачать
13_Имитационное моделирование.doc505kb.28.04.2005 15:43скачать
14_Характеристики мод-х систем и типовые схемы.doc1157kb.04.05.2005 23:18скачать
15_Планирование экспериментов.doc236kb.12.05.2005 16:07скачать
1_введение.doc207kb.07.01.2005 19:19скачать
1_общ_вопр_мод.DOC105kb.26.01.2005 11:17скачать
2_матем_мет_мод.doc89kb.22.02.2005 11:16скачать
3_Сетевые модели.doc21kb.08.02.2005 18:48скачать
6_Системы массового обслуживания.doc234kb.02.03.2005 23:51скачать
7_Сетевые модели Сети Петри.doc264kb.11.03.2005 10:17скачать
8_Обощенные модели А-схемы.doc206kb.18.03.2005 01:16скачать
9_Концептуальные, алгоритмические, статические модели.doc90kb.25.03.2005 13:09скачать
P-схемы.doc137kb.24.02.2005 22:48скачать
Модели данных.doc26kb.08.02.2005 14:10скачать
Непрерывно детерминированные модели.doc58kb.22.02.2005 17:07скачать
Сетевые модели.doc379kb.08.02.2005 18:42скачать

P-схемы.doc

Реклама MarketGid:
Загрузка...
ДИСКРЕТНО-СТОХАСТИЧЕСКИЕ МОДЕЛИ (P-схемы)
Определение: Вероятностный автомат [англ, probabilistic automat) (ВА) - это дискретный потактный преобразователь информации с памятью, функционирова­ние которого в каждом такте зависит только от состояния памяти нем и может быть описано статистически.

Схемы вероятностных автоматов (Р-схем) применяются:

  • в проектировании дискретных систем, проявляющих статистически закономерное случайное пове­дение;

  • в определении алгоритмических возможностей систем;

  • в обосновании границ целесообразности их использования;

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

Математическое понятие Р-автомата формируется на понятиях, введенных для F-автомата.

Пусть множество G, элемен­тами которого являются всевозможные пары где xi и zs — элементы входного подмножества X и подмножества состояний Z соответственно . Если существуют две такие функции и , то с их помощью осуществляются отображения и , то говорят, что (1) определяет конечный автомат детерминиро­ванного типа.

Введем более общую математическую схему. Пусть Ф — множество всевозможных пар вида (zk, yj), где yj — элемент выходного подмножества Y, т.е. . Пусть в любой элемент множества G индуцирует на множестве Ф некоторый закон распределения следующего вида:

Таблица 1

Элементы из Ф

•••

(z1, y1)

•••

(z1, y2)

•••

(zK, yJ-1)

(zK, yJ)

(zk, yj)

•••

b11




b12




bk(j-1)

bkj


При этом , (2) где bkj — вероятности перехода автомат в состояние zk и выдаче на выходе сигнала yj, если автомат был в состоянии z.S, и на его вход в момент времени поступил сигнал хi. Число таких распределений, представленных в виде таблиц, равно числу элементов множества G.

Обозначим множество этих таблиц через ^ В. Тогда четверка элементов (3) называ­ется вероятностным автоматом (Р-автоматом).

Вероятностный автомат Мили

Пусть элементы множества G индуцируют некоторые законы распределения на подмножествах Y и Z, которые можно представить соответственно в виде:

Таблица 2

Элементы из Y

•••

y1

y2

•••

YJ-1

y J



•••

q1

q2

•••

q J-1

q J

Элементы из Z

•••

z1

z2

•••

zK-1

zK



•••

1

2

•••

K-1

K


При этом и (4)— вероятности перехода Р-автомата в состояние zk и выдачи выходного сигнала yk при условии, что Р-автомат находился в состоянии zS и на его вход поступил входной сигнал xt.

Если для всех k и j имеет место соотношение (5), то такой автомат называется вероятностным автоматом Мили. Представленное тре­бование означает выполнение условия независимости распределе­ний для нового состояния Р-автомата и его выходного сигнала.
^ Вероятностный автомат Мура
Пусть выходной сигнал Р-автомата зави­сит лишь от того состояния, в котором находится автомат в данном такте работы, каждый элемент выходного подмножества Y индуцирует распределение вероятностей выходов, имеющее следующий вид:

Таблица 3

Элементы из Ф

•••

yl

у2

•••

yk-1

yk

(zk, yj)

•••

s1

S2

•••

SI-1

SI


Здесь ,(6) где Si, — вероятность появления сигнала на выходе yi при условии, что Р-автомат находился в состоянии zk.
Частным случаем Р-автомата являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминированно. Такой автомат называется Y-детерминированным вероятност­ным автоматом.

Если состояние Р-автомата определяется детерменированно, то такой автомат называется ^ Z-детерминированным вероятност­ным автоматом.

Аналогично, Z-детерминированным вероятност­ным автоматом называется Р-автомат, у которого выбор нового состояния является детерминированным.

^ Рассмотрим пример У-детерминированного Р-автомата

Пусть У-детерминированный Р-автомат, задан таб­лицей переходов

Таблица 4

zk

zk

z1

z2




zK-1

zk

z1

p11

p12




p1(K-1)

p1K

z2

p21

P22




p2(K-1)

p2K













p3(K-1)

p3K

zk

pK1

pK1




pK(K-1)

pK


где pij – вероятность перехода автомата из состояния zi в состояние zj

Можем записать (7)
Таблица выходов представлена следующим образом:

Таблица 5


Z . . . . z1

z2 . . . . zk-

zk

Y .... уi1

уi2 . . . yik-1

yik


Первую из этих таблиц можно представить в виде квадратной матрицы размерности К x К, которая называется матрицей переходных вероятностей или просто матрицей переходов Р-автомата. В общем случае матрица переходов имеет вид
(8)

Для полного описания У-детерминированного Р-автомата необходимо задать началь­ное распределение вероятностей вида

Таблица 6


Z . . . . z1

z2 . . . . zk-

zk

D . . . . d1

d2 . . . . dK-1

dK


где dK — вероятность того, что в начале работы автомат находится в состоянии zk

При этом . (9)

Будем предполагать, что до начала работы (до нулевого такта времени) Р-автомат всегда находится в состоянии z0, в нулевом такте времени меняет свое состояние в соот­ветствии с распределением D. Дальнейшая смена состояний Р-автомата определяет­ся матрицей переходов РР. Информацию о начальном состоянии Р-автомата удобно внести в матрицу РР/ , увеличив ее размерность до (10). При этом первая строка такой матрицы, сопоставляемая состоянию z0, будет иметь вид (0, dt, d2, ... ..., dK), а первый столбец будет нулевым.

- сопоставляется со состоянием z0 (11)
Описанный У-детерминированный Р-автомат можно задать в виде ориентиро­ванного графа, вершины которого сопоставляются состояниям автомата, а дуги — возможным переходам из одного состояния в другое. Дуги имеют веса, соответст­вующие вероятностям перехода рij, а около вершин графа пишутся значения выход­ных сигналов, индуцируемых этими состояниями.

^ Рассмотрим следующий пример. У-детерминированный Р-автомат задан матрицей

. (12)
Таблица 7

Z

z0

z1

z2

z3

z4

Y

0

0

1

1

0


Граф переходов имеет вид (Рис.1).

0,50


Рис. 1

Требуется оценить суммар­ные финальные вероятности пребывания этого Р-автомата в состояниях z2 и z3.

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

- матрица финальных состояний (13)

(14), где ck - финальная вероятность пребывания Р-автомата в состоянии zk.

Получаем систему уравнений

(15)

Добавим к этим уравнениям условие нормировки с12 + с3 + с4 = 1 (16). Тогда, решая систему уравнений, получим с1 = 5/23, с2=8/23, c3 = 5/23, с4 = 5/23 (17). Таким образом, с23= 13/23 =0,5652 (18). Другими словами, при бесконечной работе заданного в этом примере У-детерминированного Р-автомата на его выходе формируется двоичная последовательность с вероятностью появления единицы, равной 0,5652.

Подобные Р-автоматы могут испо­льзоваться как генераторы марковских последовательностей, которые необхо­димы при построении и реализации про­цессов функционирования систем S или воздействий внешней среды Е.

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



Скачать файл (1799.4 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации