Презентация на тему: Сети Петри Глава 11. Стохастические сети Петри

Реклама. Продолжение ниже
Сети Петри Глава 11. Стохастические сети Петри
Оглавление :
Стохастические процессы. Основные понятия
Стохастические процессы. Основные понятия
Стохастические процессы. Основные понятия
Стационарные, независимые, Марковские процессы
Марковские процессы
Цепи Маркова
Вводные понятия и основные определения
Вводные понятия и основные определения
Вводные понятия и основные определения
Марковские сети Петри
Марковские сети Петри
Марковские сети Петри
Марковские сети Петри
Динамическая матрица МЦНВ
Динамическая матрица МЦНВ
Численные характеристики производительности систем
Численные характеристики производительности систем
Численные характеристики производительности систем
Численные характеристики производительности систем
Численные характеристики производительности систем
Пример 1
Пример 1
Пример 1
Пример 1
Пример 1
Пример 1
Численные характеристики производительности систем. Пример 2.
Численные характеристики производительности систем. Пример 2.
Численные характеристики производительности систем. Пример 2.
Численные характеристики производительности систем. Пример 2.
Численные характеристики производительности систем. Пример 2.
Численные характеристики производительности систем. Пример 2.
Литература
1/35
Средняя оценка: 4.4/5 (всего оценок: 46)
Код скопирован в буфер обмена
Скачать (651 Кб)
Реклама. Продолжение ниже
1

Первый слайд презентации: Сети Петри Глава 11. Стохастические сети Петри

Aurelia Prepelita Conf., dr., USM Chisinau, 2010

Изображение слайда
1/1
2

Слайд 2: Оглавление :

Глава 11. Стохастические сети Петри Стохастические процессы. Основные понятия Вводные понятия и основные определения Стационарные процессы Независимые процессы Марковские процессы Цепи Маркова Стохастические временные СП Марковские сети Петри

Изображение слайда
1/1
3

Слайд 3: Стохастические процессы. Основные понятия

По определению, стохастический процесс представляет собой семейство случайных величин X(  ) принадлежащих пространству Wx(  ), называемое пространством состояний и которые индексируются по параметру  значения которых принадлежат ансамблю . Это означает, что процесс представляется как : { X(  )  Wx(  ),    }. А нсамбли Wx и  могут быть дискретным или непрерывным. В зависимости от того принимает ли данный параметр  непрерывные или дискретные значения, то будем говорить либо о стохастической цепи, либо о стохастическом процессе. Часто параметр  представляет время.

Изображение слайда
1/1
4

Слайд 4: Стохастические процессы. Основные понятия

Для оценки состояния системы необходимо использовать вектор состояния X, представленный семейством X( i ) случайных величин, независимых между собой: X={X( 1 ), X( 2 ), …, X( i ), …}. Необходимо ввести понятие вероятности состояния  x ():  x ()=Prob{ X(  )=x }, является функцией параметра  и представляющая вероятность того, что переменная X примет значение х в момент ; Это значение фактически представляет собой абсолютную вероятность состояния X(  ).

Изображение слайда
1/1
5

Слайд 5: Стохастические процессы. Основные понятия

Условная вероятность перехода от состояния x1 к x2, через один или несколько временнных прыжков: r x1x2 ( 1, 2 )= Prob{X( 2 )=x2|X( 1 )=x1} и представляет вероятности перехода между двумя этими двумея состояниями, события, которые разворачиваются в промежутке времени = 2- 1. Стохастические процессы в соответствии с фунцией распределения вероятностей - F x ( X, ): F x ( X, )=Prob{ X( 1) ≤x1, X( 2) ≤x2, …, X( i) ≤xi, … } делятся на: стационарные процессы, независимые процессы, Марковские процессы.

Изображение слайда
1/1
6

Слайд 6: Стационарные, независимые, Марковские процессы

Стационарные процессы Процесс X(  ) является стационарным, если функция распределения вероятностей остается равной себе на любом промежутке  на оси времени, а именно: Fx( X,  + )= Fx( X, ); Независимые процессы Концепция независимости между переменными X( i ) представлена в ввиде : Fx( X, )=Fx1,x2,…,xi,…(x1,x2,…,xi,…, 1, 2, …, I,…)=Fx1(x1, 1)*Fx2(x2, 2)*…*Fxi(xi, i)*…; Марковские процессы Эта категория охватывает случайные процессы для которых изменения происходят, таким образом что каждое из состояний X( 0 ), X( 1 ),…, X( i ),… соответствующие последовательным моментам 0, 1, …, i,… зависят только от конечного числа k предыдущих состояний. Если пространство состояний дискретно, то мы имеем дело с цепью Маркова порядка k. Наиболее часто используется класс Марковских процессов, для которых k= 1. Это означает, что если дана последовательность состояний X( j ) для такого процесса, состояние X( j+1 ) будет зависеть исключительно от предыдущего X( j ) состояния т.е. с точки зрения вероятности: Prob{ Xj+1( j+1=xj+1| X( 0=x0, …, X( j=xj}= Prob{ X( j+1=xj+1| X( j=xj}.

Изображение слайда
1/1
7

Слайд 7: Марковские процессы

Это свойство представляет собой основную характеристику Марковского процесса: будущее состояние зависит только от настоящего состояния. Иными словами, Марковские процессы - процессы без памяти.

Изображение слайда
1/1
Реклама. Продолжение ниже
8

Слайд 8: Цепи Маркова

Если  n (j) является абсолютной вероятностью состояния nj, то пространство вероятности на момент j представляет собой матрицу-строку П ( j ), компонентами которой являются значения  0 (j),  1 (j), …, каждое из которых имея амплитуду меньшую или равную единице, т.е.: П ( j ) =[  0 (j),  1 (j), …,  k (j),… ]. зная, что для любого n j ≥ 0 существует : 0≤  ni ≤1 cu  ni  ni (j)=1.

Изображение слайда
1/1
9

Слайд 9: Вводные понятия и основные определения

Изображение слайда
Изображение для работы со слайдом
1/2
10

Слайд 10: Вводные понятия и основные определения

Стохастические процессы позволяют моделировать множество технических, экономических, социальных и др. систем.

Изображение слайда
1/1
11

Слайд 11: Вводные понятия и основные определения

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

Изображение слайда
1/1
12

Слайд 12: Марковские сети Петри

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

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/4
13

Слайд 13: Марковские сети Петри

Определение. Обобщенная сеть Петри-Маркова, RPM сокращенно, есть 2-ка NM=<N,  >, где: - N обобщенная СП; -  является функцией, определяющая скорость срабатывания возбужденных переходов маркировкой M, т. е. параметр отрицательно экспоненциального закона:.

Изображение слайда
Изображение для работы со слайдом
1/2
14

Слайд 14: Марковские сети Петри

В общем, если система описывается Марковским процессом с непрерывным временем, определяющий цепь Маркова с непрерывным временем (МЦНВ), тогда он определяет существование стационарного режима и позволяет проводить численные оценки средних значений характеристик исследуемой системы. Стационарное состояние функционирования системы представляет собой такой режим, при котором эволюция системы не зависит ни от начальных условий, ни от данного момента времени. Если все состояния МЦНВ могут быть достигнуты в течение ограниченного промежутка времени, то существует стационарное распределение вероятностей нахождения в соответствующих состояниях.

Изображение слайда
1/1
Реклама. Продолжение ниже
15

Слайд 15: Марковские сети Петри

Система, моделируемая RPM, будет обладать стабильными режимами функционирования, если соответствующая ей обобщенная СП ограничена, жизнеспособна и, реинициализуема. Эти три свойства обобщенной СП гарантируют что граф достижимых маркировок будет изоморфен МЦНВ для ОСП.

Изображение слайда
1/1
16

Слайд 16: Динамическая матрица МЦНВ

Динамическая матрица МЦНВ. Цепь МЦНВ, описывающая функционирование RPM может быть получена непосредственно из графа достижимых маркировок ОСП, представленный в виде списка. Пространство состояний МЦНВ является Acc(RP,M 0 ), и скорости перехода от заданной маркировки Mi к новой маркировке Mj, (M i [t k >M j ) определяются по формуле d ij =  k >0, i j, где  k скорость срабатывания перехода t k (возможно от маркировки зависимая, т. е., например,  k (Mi)=  k * M i (p i )). Если существуют два или более возбужденных переходов t k1, t k2,... которые в свою очередь приводят от маркировки Mi к маркировке Mj, (i j ), то d ij =  k1 +  k1 +..., и.

Изображение слайда
Изображение для работы со слайдом
1/2
17

Слайд 17: Динамическая матрица МЦНВ

Квадратная матрица порядка Ns = Acc (RP, М 0 ) называется динамической матрицей, описывающей ЦМНВ и соответствующая ОСП. Функционирование ЦМНВ описывается системой уравнений Колмогорова-Чепмена: где i() есть вероятность, что маркировка ОСП в данный момент времени  будет Mi, и  0 (0)=1. Приведем другой вид уравнения Чепмена-Колмогорова: П * D = 0 ; где i – стационарная вероятность что ОСП будет находиться в маркировке Mi, а П =( 0, 1,...,  Ns ) есть вектор-строка.

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/4
18

Слайд 18: Численные характеристики производительности систем

Определив вероятности стационарного состояния П, можно оценить различные характеристики производительности компьютерных систем описанных моделями ОСП Маркова. Далее мы рассмотрим некоторые численные характеристики производительности систем: 1. Предположим B Acc(RP, M0) является подмножеством состояний цепи ЦМНВ определяющее частное условие вероятности появления некоторых событий, таких что Марковский процесс принадлежал бы подмножеству состояний B, то мы получим следующее соотношение:

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
19

Слайд 19: Численные характеристики производительности систем

2. Вероятность что в позиции pi, L – ограниченной, находятся ровно l=(0,...,L) маркеров : 3. Среднее число маркеров в позиции pi:

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/5
20

Слайд 20: Численные характеристики производительности систем

4. Средняя скорость срабатывания перехода tj: 5. Средняя скорость входного потока в позицию pi:

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/5
21

Слайд 21: Численные характеристики производительности систем

6. Средняя скорость выходного потока из позиции pi: 7. Вероятность что число маркеров в позиции ограниченно

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/5
22

Слайд 22: Численные характеристики производительности систем

8. Средняя частота срабатывания перехода tj: 9. Среднее время нахождения маркера в позиции pi:

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/5
23

Слайд 23: Пример 1

Пример 1 Рассмотрим марковскую сеть RPM1. a) M1 = [1,1,0,0] [t1>M2, t2>M3; M2 = [0,1,1,0] [t2>M4; M3 = [1,0,0,1] [t1>M4; M4 = [0,0,1,1] [t3>M1. 0 Рисунок 1. Марковская с еть RPM1 (a); Граф достижимости в виде списка (b); Граф достижимости марковской с ети RPM1 (c) Цепь Маркова LM1 (d). t 1 M1(1,1,0,0) M3(1,0,0,1) M2(0,1,1,0) M4(0,0,1,1) t 1 t 2 t 2 t 3 M1(1,1,0,0) M3(1,0,0,1) M2(0,1,1,0)  1  2  2  3  1 M4(0,0,1,1) c) d) b)

Изображение слайда
Изображение для работы со слайдом
1/2
24

Слайд 24: Пример 1

Динамическая матрица D1: M1(1,1,0,0) M3(1,0,0,1) M2(0,1,1,0) M4(0,0,1,1)  1  1  1  1 M4(0,0,1,1)  2 M1(1,1,0,0) M3(1,0,0,1) M2(0,1,1,0)  1  2  3  1 Рис. 3. Цепь Маркова LM1.

Изображение слайда
Изображение для работы со слайдом
1/2
25

Слайд 25: Пример 1

Вектор-строка стационарных вероятностей ∏ =[  1,  2,  3,  4 ] нахождения в состояниях Mi(i=1,4) является решением системы уравнений Колмогорова : { Пример 1

Изображение слайда
Изображение для работы со слайдом
1/2
26

Слайд 26: Пример 1

Находим : Средние скорости срабатывания переходов RPS1:

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
27

Слайд 27: Пример 1

Т.о., вектор-строка  =[  1,  2,  3] является решением уравнения C*  =0, где C матрица инциденций сети RPM1. Средние значения маркировок M (pi) в соответствующих позициях определяются как :

Изображение слайда
Изображение для работы со слайдом
1/2
28

Слайд 28: Пример 1

Которые определяют уловия консервирования маркировок в позициях : С помощью формулы Little можно определить среднее время  (pi) нахождения маркеров в соответствующих позициях :

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
29

Слайд 29: Численные характеристики производительности систем. Пример 2

Проиллюстрируем применение ССП Маркова для моделирования вычислительных систем. Рассмотрим упрощенную модель многопроцессорной системы с n активными процессорами, которые могут выйти из строя, и с К процессорами в хорошем рабочем состоянии, что находится в резерве. При отказе какого-либо процессора в активном состоянии, то он будет заменен на один процессор из числа резервных. Процессор вышедший из строя будет отремонтирован, а затем будет направлен в резерв. Состояния: Р1 число активных процессоров в хорошем, рабочем состоянии; Р2 число процессоров в хорошем рабочем состоянии, что находится в резерве и которые могут быть использованы для замены вышедших из строя процессоров, находящихся в активном состоянии; P3 это число процессоров в аварии и P4 определяет количество процессоров в настоящее время нуждаются в ремонте. Основными событиями являются: 1 сбой процессора находящегося в активном состоянии; 2 замена процессора на резервный процессор; 3 ремонт процесса, который затем направляется в резерв.

Изображение слайда
1/1
30

Слайд 30: Численные характеристики производительности систем. Пример 2

Рисунок 1. ССПМ(а ) и производительность работы системы в зависимости от средней скорости сбоя процессора  1 (b).

Изображение слайда
Изображение для работы со слайдом
1/2
31

Слайд 31: Численные характеристики производительности систем. Пример 2

Скорости срабатывания переходов : где число маркеров в позиции pi и маркировке Mi. Можно заметить что ОСП с начальной маркировкой M0=(n,k,0,0) имеет 2 P - инварианта :

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/4
32

Слайд 32: Численные характеристики производительности систем. Пример 2

Рассмотренная сеть является ограниченной, живой и реинициализуемой и цепь Маркова обладает Ns=(n+1)(k+1) числом состояний. Для начальной маркировке M0=(4,3,0,0) цепь Маркова представлена ниже :

Изображение слайда
1/1
33

Слайд 33: Численные характеристики производительности систем. Пример 2

Для начальной маркировке M 0 =(5,2,0,0) и значений получим численные значения для характеристик представленных на рис. 2b.

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
34

Слайд 34: Численные характеристики производительности систем. Пример 2

Рисунок. 2. Цепь Маркова с непрерывным временем с начальной маркировкой M0=(4,3,0,0).

Изображение слайда
Изображение для работы со слайдом
1/2
35

Последний слайд презентации: Сети Петри Глава 11. Стохастические сети Петри: Литература

GUTULEAC E., MOCANU M. L., TURCANU I. Membrane Differential Petri Nets for Performance Modelling of Hybrid P-Systems. Control Engineering and Applied Informatics, vol. 9, no. 3-4, December 2007, Ed.: SRAIT, Bucuresti, Romania, p. 12-21. Gu ţuleac E. Modelarea şi evaluarea performanţelor sistemelor de calcul prin Reţele Petri: Ciclu de prelegeri. Partea I. Departamentul Editorial-Poligrafic al U.T.M. Chişinău, 1998.

Изображение слайда
1/1
Реклама. Продолжение ниже