5. Эквивалентные преобразования графовых моделей алгоритмов и программ.

Задача – получить сетевую модель. Данная задача решается в два этапа:

1. “СА -> ГМ” – преобразование схемы алгоритма в графовую модель определенного вида (псевдосетевую модель). Псевдосетевая модель отличается от сетевой только наличием контуров.

2. “ГМ -> СМ” – преобразование графовой модели в сетевую модель, то есть избавление от контуров.

Рассмотрим второй этап – построение сетевой модели (“СА -> ГМ”).

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

Существует 3 правила эквивалентных преобразований:

1. Последовательные соединения одинаково направленных дуг.

m_il = m_is + m_sl – мат.ожидание

D_il = D_is + D_sl – дисперсия

p_il = p_is*p_sl

2. Параллельное соединение одинаково направленных дуг.

3. Элементарный контур.

Элементарный контур – это контур, в котором совпадают исходящая и входящая вершины и не содержится промежуточных вершин.

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

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

1. Есть ли промежуточные вершины?

   1. ДА => Есть ли элементарный контур?

      1. ДА => Применяем правило 3, вернуться к пункту 1.

      2. НЕТ => Применяем правило 1, вернуться к пункту 1.

   2. НЕТ => Есть ли параллельные дуги?

      1. ДА => Применяем правило 2.

      2. НЕТ => Конец

Циклы

1. Циклы с фиксированным числом повторений – известно n – число повторений, или мат.ожидание m(n).

1. Цикл с постусловием.

Всего событий n, нас устраивает одно, поэтому вероятность выхода из цикла:

Или

2. Цикл с предусловием.

Всего событий n+1, нас устраивает одно, поэтому вероятность выхода из цикла:

Или

2. Цикл с заранее не фиксированным числом повторений.

Рассмотрим вероятность выхода из цикла q(n):

n	1	2	3	…	k	…	N
q(n)	p	(1-p)*p	(1-p)^2*p	…	(1-p)^k-1*p	…	(1-p)^N-1*p

1. Если известно m(n), то

2. Если известно q(n), то

3. Разветвление в результате проверки неравенства (x<C) или (x>C).

x – переменная, , c = const.

Если х – непрерывная случайная величина (НСВ):

Если x – равномерная СВ:

6. Марковские случайные процессы и их место при построении и исследовании вероятностных моделей объектов.

Состояние – это внутренняя характеристика объекта/процесса, позволяющая определить текущие или будущие реакции объекта/процесса на предполагаемые внешние воздействия.

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

Случайный процесс называется марковским, если для любого произвольного момента t₀ поведение этого объекта или процесса в будущем определяется только текущим состоянием объекта в момент t₀ и не зависит от того, как мы попали в это состояние (то есть не зависит от предыстории). Пример – счетчик Гейгера (количество заряженных частиц N).