Построение и анализ дискретно-стохастической модели

1.

Раздел 1.
Анализ систем методами теории
массового обслуживания
Тема 3.
Построение и анализ
дискретно-стохастической модели

2.

План лекции:
1. Классификация математических моделей
по признакам непрерывности и стохастичности.
2. Классификация случайных процессов
по времени и по состояниям.
3.
Особенности
дискретно-стохастических
моделей.

3.

Вопрос 1.
Классификация математических
моделей
по признакам непрерывности и
стохастичности

4.

Классификация
математических моделей
по признаку
непрерывности
по признаку
стохастичности
непрерывные
детерминированные
дискретные
вероятностные
Рис. 1. Признаки классификации математических моделей.

5.

Математическая
модель
Непрерывнодетерминированные
(D - схемы)
Непрерывновероятностные
Дискретновероятностные
Дискретнодетерминированные
(Q - схемы)
(P - схемы)
(F - схемы)
Рис. 2. Классификация математических моделей

6.

Непрерывные детерминированные модели (dinamic)
В этих моделях текущее время полагается непрерывным, а
случайными факторами в системе пренебрегают.
Основной математический аппарат, используемый при
построении и исследовании данного класса моделей – это
теория дифференциальных и интегральных уравнений.
Пример - описание параметров колебательного контура:
2
d 2 x (t )
1
x (t ) u (t )
2
dt
1
u (t ) 0; x (0) A cos
1
x (t ) A cos(
t )
1/ 2
( 1 2 )

7.

Дискретно-детерминированные модели
(finish automat)
Время в них является дискретной переменной с шагом Δt.
Основной математический аппарат, который используется
при описании ДДММ – это теория разностных уравнений и
аппарат дискретной математики (теория конечных автоматов).
Конечный автомат – это ММ дискретной системы S,
которая под воздействием входных сигналов u вырабатывает
выходные сигналы y и может иметь некоторое изменяемое
внутреннее состояние x .
Пример разностного уравнения:
( x , x 1 ,...x n , u , u 1 ,...u m , , t ) 0
x i x(( i ) )

8.

Дискретные вероятностные математические модели
(probabilistic automat)
Главное отличие - учет случайных элементов.
Основными математическими аппаратами, используемыми
при построении и исследовании данного типа моделей,
являются:
• теория разностных стохастических уравнений;
• теория вероятностных автоматов.
Разностное стохастическое уравнение (РСУ) содержит
случайные параметры Q и случайные входные воздействия {Ui}.
Если необходимо учесть случайный вектор параметров системы
Q=(Q1,…, Qm) и случайную последовательность входных воздействий
{U0,U1,…,Um} тогда нелинейное РСУ порядка (n,m) имеет следующий вид:
Ф( x , x 1 ,..., x n , U , U 1 ,..., U m , , ) 0
где: x0, x1, …, xn+1 – это заданные начальные состояния системы.

9.

F(…) – это заданная функция.
Если F(…) линейна по {xt, Ut}, то она будет иметь специальный вид:
n
m
x
i 0
i
i
j 0
j n 1
U j U 0,
n 2; n 3,...
Данное уравнение в математической статистике известно,
как уравнение авторегрессии и скользящего среднего порядка
(n,m).
Второй член ур-я – модель скользящего среднего, а все
остальные члены – модель авторегрессии.

10.

Вопрос 2.
Классификация случайных
процессов
по времени и по состояниям

11.

Случайный процесс, протекающий в любой
физической системе S, представляет собой случайные
переходы системы из состояния в состояние.
Состояние системы может быть охарактеризовано с
помощью каких-либо численных параметров:
в простейшем случае – одного, а в более сложных –
нескольких.
Случайные процессы классифицируются:
«по времени» и
«по состояниям».
Случайный процесс называется процессом с
дискретным временем, если система, в которой он
протекает, может изменять свои состояния только в
конкретные моменты времени, число которых
конечно и счетно (t0, t1, t2, …, tn ).

12.

Случайный процесс называется процессом с
непрерывным временем, если переходы системы из
состояния в состояние могут происходить в любой
момент времени t наблюдаемого периода Т.
Случайный процесс называется процессом с
дискретными состояниями, если в любой момент
времени t множество его состояний S конечно и
счетно.
Разумеется,
все
случайные
процессы
с
«качественными» состояниями относятся к категории
процессов с дискретными состояниями. Течение такого
процесса представляет собой случайное событие –
аналог дискретной случайной величины.

13.

Т.О., в зависимости от характера множества значений
по времени и множества состояний системы все
случайные процесс делятся на четыре класса:
1) процесс с дискретными состояниями и дискретным
временем;
2) процесс с дискретными состояниями и непрерывным
временем;
3) процесс с непрерывными состояниями и дискретным
временем;
4) процесс с непрерывными состояниями и непрерывным
временем.

14.

Вопрос 3.
Особенности дискретностохастических моделей

15.

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

16.

При
изучении
процессов
с
дискретными
состояниями удобно пользоваться геометрической
схемой - графом состояний.
Граф состояний отображает возможные пути
перехода из одного состояния системы в другое.
Пример 1.
Компьютер (система S), состоящий на учете
отдела, может находиться в одном из пяти возможных
состояний:
S1 – исправен;
S2 – неисправен, требует осмотра для выявления
неисправности;
S3 – осматривается;
S4 – ремонтируется;
S5 – списан.
S1 , S5
- возможные состояния системы, а стрелки
указывают на возможные переходы из одного
состояния в другое.

17.

S1
S2
S3
S4
S5
Рис. 1.
Граф состояний системы S

18.

Пусть имеется система S , которая может
находиться в из n состояний S 1 , S n .
Случайным
процессом
с
дискретными
состояниями S 1 , S n и дискретным временем t 1 , t m
называется такой процесс, при котором переход из
состояния в состояние возможен только в
строго определенные моменты времени t 1 , t m .
В промежутках между этими моментами система
S находится в одном из состояний.
В общем случае система в моменты t i может не
переходить в другие возможные состояния, а
оставаться в исходном.
Для удобства будем называть моменты перехода
системы из состояния в состояние шагами.

19.

(k )
Обозначим S i (где i - номер состояния системы, а
k - число шагов) событие, состоящее в том , что через k
шагов система S будет находиться в i-м состоянии.
При любом k события образуют полную группу
несовместных событий.
Система S от шага к шагу случайным образом
переходит от состояния к состоянию.
(0)
(1)
( 2)
( 3)
,
,
,
...
Например, S 1 S 2 S 4 S 3
Такая случайная цепь событий называется
марковской цепью, если вероятность перехода из
(k )
( k 1)
состояния S i
в состояние S i
зависит только от
(k )
S i , но не зависит от того, как система
состояния
оказалась в этом состоянии.
Обозначим
вероятность нахождения системы в
(k )
состоянии S i :
(k )
P( S i ) Pi (k )

20.

n
Тогда для любого k справедливо Pi ( k ) = 1,
i 1
исходя из положения о несовместности событий и
образования ими полной группы.
Предположим , что поведение системы S задано
графом, изображенным на рис. 2.
p13
S1
S3
p32
p12
p23
p34
p24
S2
p42
Рис. 2. Пример размеченного графа
S4

21.

Граф называется размеченным, если над
стрелками поставлены вероятности перехода из
одного состояния в другое.
Из
размеченного
графа
и
положения
о
несовместности событий и образования ими полной
группы можно определить вероятность того, что
система может задержаться в некотором
i-м
состоянии.
Например , для рис. 2 можно найти :
p 1 p p
p 1 p p
p 1 p p
p 1 p
11
33
12
32
13
34
22
44
23
42
24

22.

В общем виде переходные вероятности
представить в виде матрицы:
p
p
p
p
...
...
p
p
11
21
P
ij
=
m1
12
22
m2
...
...
p
p
n1
n2
...
...
...
...
...
...
p
p
1n
2n
...
p
mn
...
p
nn
p удобно
ij

23.

Если система не может перейти из некоторого k-го
состояния в некоторое i-е ,то вероятность pki
в
матрице надо положить равной нулю.
Например, для графа, изображенного на рис.2,
переходная матрица будет иметь вид:
p p p 0
0
p p p
0
p p p
0
p 0 p
11
P
ij
=
12
13
22
23
24
32
33
34
42
44

24.

Определим вероятности нахождения системы в i-м
состоянии после k шагов pi (k ) при условии, что нам
известны:
(0)
1) начальное состояние системы S m ;
2) матрица переходных вероятностей.
В начальный момент времени (k=0)
Pm(0)=1;
Pi(0)=0;
i=1,n.
Очевидно, что на первом шаге вероятности Pi(1)
определяются m-й строки матрицы.

25.

На
втором
шаге
для
определения
воспользуемся формулой полной вероятности:
pi(2)
p1(2)=p1(1)p11+p2(1)p21+…+pn(1)pn1,
p2(2)=p1(1)p12+p1(1)p22+…+pn(1)pn2,
…………………
pn(2) = p1(1)p1n + p2(1)p2n +… + pn(1)pnn.
Система уравнений может записана и в более
кратком виде
n
p (2) p (1) p , i 1, n
i
j 1
j
ji

26.

Для k-го шага получим:
n
p (k ) p (k 1) p , i 1, n
i
j 1
j
ji
Порядок
расчета
вероятностей
состояний
проиллюстрируем на примере однородной марковской
цепи.
Пример 2. Проведен анализ хакерских атак
компьютерных сетей одной организации. Атаки
проводились
последовательно
тремя
разными
вредоносными программами.
Вероятности нанесения сети незначительных
повреждений, значительных повреждений, а также
полного вывода из строя сети после атак известны:
0,4; 0,2;
0,1.

27.

Известно также, что если сеть в результате
предыдущей
атаки
получала
незначительные
повреждения, ей были нанесены повторно уже
серьезные повреждения с вероятностью 0,4, или она
была полностью повреждена с вероятностью 0,2.
Если же сеть в результате предыдущего удара
получала серьезные повреждения, то при очередной
атаке она полностью выводилась из строя с
вероятностью 0,7.
Цель математического моделирования - определить
вероятности
состояний
сети
после
трех
последовательных атак.
Решение задачи:
1) составление размеченного
системы – компьютерной сети.
графа
состояний

28.

Выделяются четыре состояния системы:
S1 - сеть исправна;
S2 - сеть получила незначительные повреждения;
S3 - сеть получила значительные повреждения;
S4 - сеть выведена из строя.
S1
0,2
0,4
0,4
S2
S3
0,2
0,1
0,7
S4
Рис. 3. Размеченный граф исследуемой системы

29.

2) составление матрицы переходных вероятностей:
Так как в начальный момент
сеть находится в
состоянии S1,
то p1(1) = 1 – (0,4 + 0,2 + 0,1) = 0,3 (вероятность того, что
сеть после первой атаки останется в данном состоянии);
p2(1) = 0,4 (вероятность того, что сеть после первой атаки
перейдет в состояние S2).
Далее по аналогии:
p3(1) = 0,2;
p4(1) = 0,1.
(заполняется первая строка матрицы).
Вероятности того, что система в следующем шаге
останется в текущем состоянии, рассчитывается по
аналогии с расчетом p1(1) на основании формулы полной
группы событий:
p2(2) = 1 – (0,4 + 0,2) = 0,4;
p3(3) = 1 – 0,7 = 0,3;
p4(4) = 1.
Дополним граф данными вероятностями.

30.

0,3
S1
0,4
0,4
0,2
S3
0,7
0,3
S2
0,4
0,1
0,2
S4
1

31.

Т.О. все вероятности рассчитаны для матрицы
переходов.
Для проверки правильности матрицы можно
проверить, что сумма элементов в строке должна
быть равна единице.
P
=
ij
0,3 0,4 0,2 0,1
0 0,4 0,4 0,2
0
0 0,3 0,7
0
0
0
1

32.

3) вероятности состояний системы после второго
шага найдем по формуле
p (2) p (1) p
n
i
j 1
j
ji
p1(2) = p1(1) p11 = 0,3 * 0,3 = 0,09;
p2(2) = p1(1)p12 + p2(1)p22 =0,3*0,4 + 0,4*0,4 = 0,12+0,16 =
=0,28
p3(2) = p1(1)p13 + p2(1)p23 + p3(1)p33 = 0,3*0,2 + 0,4*0,4 +
+ 0,2*0,3 = 0,28
далее по аналогии
p4(2) = 0,3*0,1 + 0,4*0,2 + 0,2*0,7 + 0,1*1 = 0,35.

33.

4) таким же образом рассчитаем вероятности
состояний системы после третьего шага:
p1(3) = p1(2)p11 = 0,09*0,3 = 0,027;
p2(3) = p1(2)p12+p2(2)p22 = 0,09*0,4 + 0,28*0,4 = 0,148;
p3(3) = p1(2)p13 +p2(2)p23 +p3(2)p33 = 0,09*0,2 +0,28*0,4 +
+ 0,28*0,3 = 0,214;
p4(3) = p1(2)p14 + p2(2)p24 + p3(2)p34 +p4(2)p44 = 0,09*0,1 +
+ 0,28*0,2 + 0,28*0,7 + 0,35*1 = 0,611.

34.

Таким образом, получены вероятности всех
исходов трех подобных последовательных хакерских
атак компьютерных сетей:
p1(3) = 0,027 (сеть останется не поврежденной);
p2(3) = 0,148
повреждения);
(сеть
получит
незначительные
p3(3) = 0,214
повреждения);
(сеть
получила
существенные
p4(3) = 0,611 (сеть полностью будет выведена из
строя).
Как видно, сумма данных вероятностей равна 1.

35.

Задание на самоподготовку:
1) отработать учебный
контроля (самоконтроля);
материал
по
вопросам
2) быть готовым к прогнозированию состояния
исследуемой системы на основе её модели МСП с
дискретными состояниями и дискретным временем как
вручную, так и с использованием вычислительной
техники (эл. таблиц MS Excel)
на лабораторном занятии № 1.