85

Классификация и моделирование систем

Шпаргалка

Математика и математический анализ

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

Русский

2012-11-14

926.5 KB

22 чел.

  1.  Основные понятия теории систем

Моделирование – замещение одного объекта (оригинала системы) другим, т.е. моделью, фиксация и изучение свойств модели.

Объект моделирования – система.

Обозначение: S – система.

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

Обозначение: Х – внешняя среда.

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

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

Признаки системы:

1. Ограниченность – выделенность и наличие границ функционирования.

2. Автономность – независимость, самостоятельность

3. Целостность – не сводимость целого к частям.

Этапы развития: возникновение – становление – расцвет – стагнация – распад.

Формальное определение системы:

Выход: Y0 – характеристики системы (множество)

 S – система

 X0 – множество воздействий внешней среды

Вход: S0 – множество параметров системы

{y0k}k Y0, {s0i}i S0, {x0n}n X0

y0k = f(s0i, x0n, T), где  y0k – выходные данные (характеристика), s0i (параметр), x0n (внешнее воздействие) – входные, Т – время исследования системы.

  1.  Классификация систем

1. Материальные и абстрактные

Материальные – совокупности материальных объектов

Абстрактные – системы знаний (продукты человеческого мышления)

2. Статические и динамические (стат со временем постоянны)

3. Детерминированные и стохастические

Детерминированные: по текущему состоянию можно сказать как было до и как будет потом.

Стохастические: можем указать вероятность следующего состояния

4. Закрытые (замкнутые) и открытые (не замкнутые)

В закрытых происходит обмен энергией, в открытых – обмен энергией и веществом.

5. Линейные и не линейные

6. Дискретные и непрерывные

7. По степени организованности:

- плохоорганизованные (диффузионные)

- хорошоорганизованные

- самоорганизующиеся

  1.  Модель, моделирование, формальное определение модели

Модель – представление объекта или системы в некоторой форме, отличной от реального существования.

Формальное представление модели:

Smi = 1(S0i) , Smi – свойство модели, S0i - реальное

Xmn = 2(X0n)

Tm = m*T, T – время моделирования, m – изменение шкалы времени

Ymk = f(Smi, Xmn, Tm) – характеристика системы, функция.

Ymk = (y0k)

Цели моделирования:

1) оценка (оценить действительные характеристики проектируемой или существ системы, определить на сколько система будет соответствовать предъявляемым требованиям)

2) сравнение (произвести сравнение конкурирующих систем одного функционального назначения или сопоставить несколько вариантов построения 1 и той же системы)

3) прогноз (оценить поведение системы при некотором предлагаемом сочетании условий.

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

5) оптимизация (установить такое сочетание факторов и величин, которые обеспечат лучшие показатели эффективности.

1 – 4 анализ, 5 – синтез.

Стадии разработки моделей:

1) макропроектирование (на основе данных о внешней среде и параметрах реальной системы строится модель внешней среды, выявляются ограничения построения, выбирается модель системы и критерий, позволяющий определить адекватность модели).

2) микропроектировнние: с помощью способов и методов, предложенных на 1 этапе исследуется система, определяющая функции подсистем. итерационная процедура.

Принципы проектирования:

1) пропорционально-исследованное продвижение по этапам создания модели

2) согласование информационных, ресурсных, надежностных и других характеристик.

3) правильное соотношение отдельных уровней иерархии в системе моделирования

4) целостность отдельных обособленных стадий построения модели.

Классификация моделей:

1) натуральные модели – макеты или образцы, которые описаны реально существуют системы и имеют полную адекватность (уменьшенная копия)

2) электрическая (электронная) – воспроизведение динамики изменения состояния системы с помощью электрических ведичин.

3) математические модели: система, описывается в форме некоторой математической теории.

4) имитационные модели: с помощью машин воспроизводится система. целесообразно применять, когда: 1) не существует аналитич решения; 2) аналитические методы существуют, но очень сложные и трудоёмкие; 3) кроме оценки характеристик необходимо наблюдать за ходом процесса в течение определенного времени; 4) необходимо сжатие шкалы времени.

При построении модели используются следующие подходы:

1) непрерывно-детерминированный  (D- схемы) системы ДУ

2) дискретно-детерминированные F – конечные автоматы

3) дискретно-стохастические P вероятностные автоматы

4) непрерывно-стохастические Q

5) Сетевой подход N сети Петри.

  1.  Системный подход, принципы системного подхода

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

2 основных принципа:

1. структурный подход: выявляется состав элементов системы и связей между ними.

2. функциональный подход: оценивается функцией, которую выполняет система.

Функция – свойство, приводящее к достижении цели.

Функционирование системы – переход системы из одного состояния в другое.

  1.  Генераторы случайных чисел

Способы генерации случайных чисел:

1) Аппаратный (вырабатываются датчиком случайных чисел, в основе лежит физический эффект, например, шумы)

обрабатывается последовательность случайных чисел, которая имеет равномерное распределение на отрезке [0,1]

Ut – напряжение

UL – пороговое значение.

«+» запас чисел не ограничен, не используется память

«-»  периодически требуется проверка датчика,
2) Табличный 9случайные числа в виде таблицы (встраивается в программу)

«+» требуется однократная проверка

«-» ограничено количество значений, используется память.

3) Алгоритмический (основан на специальных алгоритмах)

ri = f(ri-1)

r0 задается и качество работы датчика зависит  от него и существует период, после которого числа начинают повторяться => число чисел ограничено периодом.

Например, метод средних квадратов: r0 берется из таблицы случайных чисел

r0 = 0.1234

r02 = 0.12345678

r1 = 0.3456

  1.  Проверка качества ГСЧ на равномерность

Генераторы случайных числе проверяются на:

1. равномерность ri U[0,1],

2.стат независимость cov(ri, ri+1) = 0 (c разным шагом) и на

3. стохастичность (не повторяются)

r1,…,rn – последовательность случайных чисел

R~U[0,1], если - плотность распределения

MR =  - мат ожидание

DR = - дисперсия

Способы проверки:

1. проверить стат оценки MR и DR на соответствие.

2. Частотный способ (используется доверительный интервал)

- доверительная вероятность

, - функция Лапласа, =1

пусть n=1 (0.5-0.2883; 0.5+0.2883) тогда r1,…,rn 68% в доверительном интервале

3. Проверка гипотезы (критерий )

H0: r1,…,rn ~ U[0,1] – основная гипотеза

разделим [0,1] на k интервалов одинаковой длины, h=1/k – шаг, интервалы:

ni – число значений - эмпирические частоты,

- вероятность попадания в интервал

- теоретическая частота

Для проверки гипотезы строится:

находится по таблице

- уровень значимости, k-r-1 степеней свободы,

k – число интервалов, r – число независимых параметров

если > , то H0 отвергается.

  1.  Проверка качества ГСЧ на независимость

, где - сдвиг последовательности

выборочный коэффициент корреляции (эмпирический):

где ,

данные независимы, если

H0: - теоретический коэффициент корреляции

H1: 

Критерий проверки:

1: , 2:

если , то H0 отвергается и говорят, что коэффициент корреляции значимо отличается от 0.

  1.  Проверка качества ГСЧ на стохастичность

r1,…,rn  0<p<1

 n1 – число a, n2 – число b, n – число серий.

Серия – последовательность одинаковых идущих подряд символов

 - функция Лапласа

 - функция Лапласа

  1.  Моделирование дискретных и непрерывных с.в.

1. Дискретные случайные величины

,

получить набор стат данных: r1,…,rn ~ U[0,1] – равномерное.

m – объем выборки

y1,…,ym – хотим получить (значения )

Принцип генерирования дискретной случайной величины:

2. Непрерывная случайная величина

- непрерывная, существует плотность распределения f(x)

- функция распределения

Метод обратной функции: пусть получен набор случайных чисел r1,…,rn ~ U[0,1], тогда, чтобы получить y1,…,ym с заданным законом распределения, должны вычислить: yj = F-1(rj)

1) Равномерное распределение на [a,b] U[a,b]

yj = rj(b-a) + a

2) Показательное распределение

y = F(X) =

y ~ U[0,1] т.к. эквивалентны в смысле распределения

1-y ~ U[0,1]

3) Нормальное распределение N(0;1)

=mDri , т.к. все независимы

  1.  Статистическое оценивание

Рассмотрим стат оценки для мат ожидания и дисперсии.

Оценка для мат ожидания будет состоятельной, не смещенной

- среднее арифметическое

Не смещенность: 

состоятельность следует из ЗБЧ (теорема Чебышева)

Оценка для дисперсии будет состоятельной и смещенной

- выборочная дисперсия

- исправленная дисперсия (несмещенная, исправленная).

Доверительный интервал.

Нормальное распределение с неизвестным мат ожиданием и известной дисперсией.

, находится по таблице функции Лапласа.

Если не известна дисперсия, то , t находится по таблице Стьюдента.

  1.  Системы обслуживания

СМО – совокупность приборов, обслуживающих поток заявок в соответствии с определенной дисциплиной обслуживания.

Сети СМО – объединение взаимосвязанных СМО

PK(t0, t0 + t) – вероятность поступления K заявок в интервале времени (t0; t0 + t)

СМО обладает свойствами:

1. стационарность

PK(t0, t0 + t) = PK(t) не зависят от t0 

2. ординароность

PK>=2(t) = o(t)

За время t поступит >=2 заявок, за единицу времени не >1 заявки tср -> 0

3. отсутствие последействия

в непересекающиеся интервалы времени моменты прихода заявок независимы.

(t0; t0 + t) и (t1;t2) где t2 < t0 число приходов в 1ом интервале не зависит от числа приходов во втором.

Для того, чтобы описать СМО, надо описать все её компоненты.

Компоненты СМО:

1) входной поток

tn – момент прихода в систему n-ной заявки.

- интервал между потходами n-ной и (n+1)-ой заявками  = tn+1 + tn

A(x) = P(x)  -входной поток, функция распределения сл величины

Если A(x) – функция показательного распределения, то

т.е.  имеет экспоненциальное распределение с параметром , то входной поток – простейший.

а(t) – число заявок [0;t]

a(t) ~ распределению Пуассона с параметром  для простейшего потока

a(t) ~ (k, P(a(t) = k) = ), k = 0,1,…

M(a(t)) = ; E=1/

- интенсивность входного потока – число заявок, приходящих в единицу времени.

Если  независимое и одинаково распределенное, то входной потока называется рекуррентным.

2) обслуживающие устройства

m – число каналов (приборов) обслуживания

m=1 – одноканальные

- многоканальные.

Sn – время обслуживания заявки с номером n

B(x) = P(Snx) – функция распределения случайной величины Sn

Если  (Sn ~ exp()), то поток обслуживания называется простейшим.

M(Sn) = 1/

- интенсивность обслуживания заявок – число обслуживаемых заявок в единицу времени.

Если все Sn независимы и одинаково распределенные, то поток называется рекуррентным.

n – число мест в очереди.

Если n = 0, то система называется СМО с отказами. Показатель качества: вероятность отказа, среднее число отказов.

- СМО с ограниченной очередью

- СМО с ожиданием.

3) дисциплина обслуживания

1. FIFS – обслуживание в порядке поступления

2. LIFS  

3. Случайная – выбор производится в соответствии с распределением. если равн N, pi = 1/N

4. Обслуживание с относительными приоритетами – обслуживается заявка с наибольшим относительным приоритетом.

5. Обслуживание с абсолютными приоритетами – при поступлении заявки с большим приоритетом, чем текущая, текущая снимается и обслуживается поступившая.

6. Обслуживание с разделением времени – заявки, поступившие в систему, встают в цикл, и каждой на обслуживание выделяется квант времени.

  1.  Оценки характеристик СМО

Методы определения оценок характеристик СМО:

1) коэффициент загрузки:

- среднее время обслуживания

Nобсл - среднее количество обслуженных заявок за Tm.

, оценка

2) длина очереди

, где - интервал времени, Ni – число заявок в очереди.

3) время ожидания

, где - время ожидания i-той заявки на i-том канале

=0

, R –оператор упорядочивания по возрастанию.

x+ = max(x, 0)

- среднее время ожидания

4)вероятность отказа

5) пропускная способность

- оценка относительной пропускной способности

- оценка абсолютной пропускной способности

6) количество занятых каналов

оценивается через вектор ожидания, если все 0, то канал свободен.

  1.  Принципы моделирования

1. построение модели

2. написание программы

3. обработка стат результатов моделирования.

Принципы моделирования:

1) принцип

состояние системы определяется в моменты времени t0, t0+  ,…,Tm

- выбрать очень трудно

2) принцип особых состояний:

Особые состояния – состояния системы, в которых характеристики меняются скачкообразно.

Момент поступления заявки, момент освобождения устройств.

3) принцип последовательной обработки заявок

каждая заявка отслеживается от момента поступления до момента выхода.

4) объектный тип моделирования

описание объектов идет разными блоками.

  1.  Основные объекты GPSS

1. Транзакты (транзактные сообщения)

Транзакты – динамические объекты, которые создаются в одних блоках, продвигаются по блокам и уничтожаются в других. Нумеруются от 1. Могут быть параметры (целые числа), например, приоритет.

2. Блоки.

Один блок выполняет несколько функций или правил.

Формат: <N строки> <метка> Имя_блока

  <A>,<B>,[<C>] – параметры

 ; - комментарий.

метка начинается с буквы и  5 символов

номера строк идут последовательно

* комментарий  (в начале строки)

Структура блоков:

GENERATR

….

TERMINATE

все блоки имеют вход и выход. GENERATE служит для генерации тарнзактов.

3. Устройства

Устройства – реальные объекты, на которых происходит обработка транзактов.

4. Списки.

1) список текущих событий (транзакт в активном состоянии)

2) список будущих событий (могут начать движение в будущий момент времени)

3) список прерываний (список транзактов, обслуживание которых прервано)

4) список пользователей (список транзактов, удаленных с использованием блока LINK как временно не активных)

5) список синхронизации (находятся в данный момент времени в состоянии сравнения)

5. Память, накопитель

используется, когда есть ограничение по числу мест в очереди.

6. Логические ключи

LOGIK <X> <A>

A – номер логического ключа

X = S – включен, X = R – выключен

7. Очереди

QT – среднее время пребывания транзакта в очереди

QT1

QT $LEN1  

8. Таблицы

имя_таблица TABLE <A>,<B>,<C>,<D>

A – табулируемый параметр

B – верхний предел 1 интервала

C – ширина интервала

D – число интервалов

в конце TABULATE <A> - табулирование текущего значения заданного аргумента в таблице А

(занесение данных в таблицу)

  1.  Блоки GENERATE и TERMINATE, блоки RELEASE и SEIZE, ADVANCE

GENERATE <A>,<B>,[<C>],[<D>]

AB единиц времени, если A и B – числа

AB единиц времени, если B – функция

С – задержка начала моделирования

D – число генерируемых мгновенно транзактов.

По сути D – генерация входного потока, для получения равномерного распределения на интервале [2;6] A=4, B=2

TERMINATE <A>

Имеет только вход, завершает процесс продвижения транзактов.

A – число транзактов, на которое заменяется счетчик числа завершения. Стандартно 1.

SEIZE <A> - захват устройства с именем A

RELIASE <A> - освобождение устройства с именем А

ADVANCE <A>,<B> - моделирование задержки с течением времени AB, если A и B – числа и AB, если B – функция.

  1.  Блоки GATE и TEST, блок TRANSFER

GATE <X> <A> <B>

X – логический оператор (16 существует)

А – объект, который проверяется

B – номер следующего блока, куда пойдёт транзакт, если Х – ложно.

TEST определяет направление движения транзакта в зависимости от выполнения условия, заданного алгебраическим соотношением. Оператор имеет расширенное поле операции, включающее общепринятые обозначения логических операций: L (меньше), LE (меньше или равно), E (равно), NE (не равно), G (больше), GE (больше или равно). Формат записи имеет вид

< TEST XX        A,B,C >

XX — дополнительный код логической операции (L, LE, E, NE, G, GE.).

А — не имеет значения по умолчанию, представляет собой выражение, левая часть которого сравнивается с требуемой операцией: если сравнение истинно, то Транзакт продвигается в следующий последовательный ОБ.

В — не имеет значения по умолчанию, представляет собой выражение, правая часть которого сравнивается с операндом А.

С — не имеет значения по умолчанию и представляет собой имя или номер ОБ, к которому направляется Транзакт, если результат сравнения ложный (альтернативный адрес). Если операнд С отсутствует, а результат сравнения ложный, Транзакт запрещен, вход в ОБ TEST и сравнение проводятся каждый раз, пока Транзакт находится в СТС. Такое обстоятельство приводит к избыточному использованию памяти, в этом случае (операнд С не определен) следует пользоваться ОБ GATE.

TRANSFER (Перенести, переместить) - позволяет осуществлять непоследовательное прохожде

ние разными путями. Формат записи в общем виде выглядит

следующим образом:

< TRANSFER A,B,C >

Существуют четыре основных варианта применения

1. Безусловный переход:

< TRANSFER ,B >

А — по умолчанию 0, заменяется обязательной запятой.

В — не имеет значения по умолчанию, характеризует имя (адрес) блока, к которому направляется транзакт.

2. Условный переход с одним альтернативным адресом (режим

“BOTH”):

< TRANSFER BOTH,B,C >

А — не имеет значения по умолчанию, операнд заменяется словом

BOTH, указывающим тип режима.

В — по умолчанию обозначает, что Транзакт следует в первый последовательный блок, при именовании операнда В характеризует имя (адрес) блока, к которому направляется транзакт (основной адрес).

С — не имеет значения по умолчанию, характеризует собой альтернативный адрес (при невозможности войти в блок с адресом В).

3. Условный переход с многими альтернативами (режим “ALL”):

<TRANSFERALL,B,C,D >

А — не имеет значения по умолчанию, операнд заменяется словом ALL, указывающим тип режима.

В — по умолчанию обозначает, что Транзакт следует в первый последовательный блок, при именовании представляет собой первый адрес.

С — не имеет значения по умолчанию, определяет последний адрес.

D — не имеет значения по умолчанию, представляет собой константу М, используемую для вычисления возможных адресов движения транзактов: адрес в поле В, затем — В+М, В+2М, ..., адрес в поле С.

4. Статистический переход (переход с заданной вероятностью):

<TRANSFER А,В,С >

А — не имеет значения по умолчанию, характеризует вероятность перехода транзакта по адресу С или часть времени, используемую ОБ С.

В — по умолчанию является следующим последовательным ОБ, при именовании представляет собой альтернативный адрес.

  1.  Блоки для описания очередей, блоки для описания накопителя

QUEUE <A>, [<B>] – вход в очередь с именем А, В – на сколько увеличивается очередь (по умолчанию 1).

DEPART <A>, [<B>] – выход из очереди с именем А, В – на сколько уменьшается длина очереди.

имя_накопителя STORAGE <A>

<A> - число единиц накопителя

ENTER <A> - вход

LEAVE <A>,[<B>] – Выход

<A> - имя_накопителя

<B> - число единиц, на которые уменьшается объем.

  1.  Сеть Петри. Структура сети Петри

Основные направления:

1) Общая теория сетей Петри

2) Чистая теория сетей Петри

3) Конкретные задачи анализа системы.

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

Четверка <P, T, I, O> называется сетью Петри, где

Р = {p1,…,pn} – конечное множество символов, называемых позициями (P)

T = {t1,…,tn} – конечное множество символов, называемых переходами (T)

I: PxT -> {0, 1} - входная функция

O: TxP -> {0, 1} - выходная функция

Для любого tj T задается

I(tj) = {pi  P: I(pi, tj) = 1}

O(tj) = {pi  P: O(tj, pi) = 1}

I(pi) = { tj  T: I(tj, pi) = 1}

O(pi) = { tj  T: O(pi, tj) = 1}

Графически: сеть Петри – двудольный ориентированный мультиграф.

Двойственная сеть – сеть Петри, которая получается в результате перестановки позиций переходов.

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

  1.  Маркировка сети Петри

Для отображения динамических свойств объекта вводится понятие разметки.

M: P -> {0, 1, 2,…}

каждой вершине в соответствие ставится число:

M = (M(p1), …, M(pn))

M(pi) – число меток в позиции pi P, i=1,…,n

Маркированная сеть Петри – пятерка вида: <P, T, I, O, M>, где

Р = {p1,…,pn} – конечное множество символов, называемых позициями (P)

T = {t1,…,tn} – конечное множество символов, называемых переходами (T)

I: PxT -> {0, 1} - входная функция

O: TxP -> {0, 1} - выходная функция

M – разметка сети Петри.

При отображении используем замену одной маркировки сети Петри другой по определенному правилу: переход осуществляется путём срабатывания перехода tj. Для того, чтобы переход сработал, он должен быть разрешен: tj  T разрешен, если число меток во всех входных позициях не меньше, чем число дуг из позиции в переход.

Если для любого pi I(tj) выполняется M(pi) #(pi, I(tj))

M0 – начальная разметка.

M0 M`

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

M`(pi) = M(pi) - #(pi, I(tj)) + # (pi, O(tj))

  1.  Безопасность, ограниченность, сохраняемость cети Петри

Безопасность.

Позиция p называется безопасной для сети Петри C = < P, T, I, O, M>, если число меток в этой позиции не превышает M(pi) в любой разметке, достижимой из разметки М0.

Сеть Петри называется безопасной, если все её позиции безопасны.

Правило: добавляем: pi  I(tj) => p`i O(tj) и pi  O(tj) => p`i I(tj)

Ограниченность

позиция pi  P называется k-ограниченной позицией для сети Петри С, если число меток в этой позиции не превышает k. M(pi)  k,M  R(C, M0)

Сеть Петри называется ограниченной, если все её позиции являются ограниченными.

Сохранение

Сеть Петри называется строго сохраняющей, если  для M, M` R(C, M0)

Правило: |I(tj)| = |O(tj)| tj T

рассмотрим метку w = (w1,…,wn), wi>0 – вес pi P

Сеть Петри С называется сохраняющей с вектором взвешивания w, если  для M, M` R(C, M0)

  1.  Активность, задача покрываемости, задача достижимости

Активность

Тупик в сети Петри – переход или множество переходов, которые не могут быть запущены.

Переход называется активным, если он не заблокирован.

Переход tj называется потенциально-запустимым в разметке М, если существует разметка М`, достижимая из М.

Переход tj активен в разметке М, если он потенциально запустим в разметке М`и M` R(C, M0)

Уровни активности:

0: tj – уровень активности 0, если он никогда не может быть запущен (пассивный)

1: tj – уровень активности 1, если он потенциально запустим

2: tj – уровень активности 2, если и последовательность запусков, в которой tj присутствует по крайней мере n раз.

3: tj – уровень активности 3, если существует бесконечная последовательность запусков, в которой tj присутствует неограниченное количество раз.

4: tj – уровень активности 4, если из всякой разметки M` R(C, M0) существует такая последовательность запусков переходов : tj разрешен.

- эта разметка получается из М` запуском последовательности переходов

Если каждый переход обладает активностью не ниже уровня i, то вся сеть обладает активностью i.

Достижимость и покрываемость

Задача достижимости: для заданной разметки М и сети Петри С определить является ли разметка М` достижимой их М: M` R(C, M)

Разметка М` называется достижимой из разметки М, т.е. M` R(C, M), если существует последовательность запуска переходов , которая приводит к разметке М` из разметки М, т.е. .

Задача покрываемости: Существует ли для данной сети Петри С и начальной разметки М0 маркировка

M`` R(C, M0): M``M`

Задача взаимного исключения: есть 2 процесса, которые используют один критический ресурс.

Одновременно внутри критической области может находится только один процесс.

S – двоичный семафор, TP – открытие процесса, TV – закрытие семафора, CS – критическая область.

M0 = (1 1 0 0 0 0 1)

t1: M2 = (0 1 0 0 1 0 0) t2: M4 = (1 0 0 0 0 1 0)

t3: M3 = (0 1 1 0 0 0 0) t4: M5 = (1 0 0 1 0 0 0)

Проверим все возможные достижимые разметки, посмотрели, что одновременное использование критического ресурса нет и в p3 и p4 или в p5 и p6.

Возможна ли такая разметка сети Петри, чтобы одновременно присутствовали метки p3, p4 и p5, p6.

  1.  Дерево достижимости

Представляет собой множество достижимости сети Петри в графическом методе

M0 = (1 0 0)

t1: (1 1(w) 0)        t2: (0 1 1)

дублирующая t1: (1 2(w) 0)  t2: (0 2(w) 1)   t3: (0 0 1) – терминальная

t1: (1 3 0) t2: (0 3(w) 1) – дубл t3: (0 1 1)

x – вершина дерева достижимости содержит разметку M(x)i: число или w

x – граничная (не обработана)

- терминальная

- дублирующая

- внутренняя.

Если для маркировки М не один из переходов не разрешен, то вершина х – терминальная.

tj T разрешен  M(x)

M(z) – дерево достижтимости.

Алгоритм:

1. Если в ДД  другая вершина ti, не являющаяся граничной и с ней связана та же маркировка y: M(y) = M(x), то х – дублирующая вершина.

2. Если для М(х) ни один переход не разрешен (M(x), tj) не определена  tj T, то вершина объявляется терминальной.

3. Если  у на пути от корневой к х и M(x) (M(x), tj) и M(y)i < (M(x), tj)i  строим новую вершину M(z)i = w (на i-том месте символ w, если он уже там стоял, то так и оставляем)

Если M(x)i = w, то M(z)i = w.

4. в противном случае M(z)i = (M(x), tj)i .

Свойства сетей Петри:

1. Безопасность (если в каждой вершине не > 1 метки, то сеть является безопасной, если стоит хоть 1 w, то сеть не является безопасной.

2. Ограниченность: k-огранич: в каждой вершине не более k меток. Когда есть w сеть не ограничена.

3.Сохраняемость: строгое: если сумма всех меток в каждой вершине одинакова. Если есть w сеть не является строго сохраняющей. сохр-ть с весом: если вес позиции, в которой стоит w должен быть = 0.

4. Покрываемость: имеем M`  M

5. Активность переходов: с помощью ДД определить не возможно.

6. Достижимость: задача достижимости не решается, т.к. мешает w определить.

  1.  Матричные уравнения

Представим 2 матрицы: D- - матрица входов, D+ - выходов.

D-ij = #(pi, I(tj)) – число входов из этой позиции.

D+ij = #(pi, O(tj)) – число выходов из этой позиции.

- число входных дуг

- число выходных из t в р.

Обозначим ej – вектор, содержащий нули кроме j-той компоненты.

ej = (0, …, 1, … 0)

tj разрешен, если число меток не меньше числа входных дуг

M` = (M, tj) = MejD- + ejD+ = M + ej(D- + D+) = M + ejD.

D – матрица изменений.

Обозначим - последовательность запуска переходов.

M` = (M, ) = M + ej1D + … +ejkD = M + (ej1 + … + ejk)D

(ej1 + … + ejk) = f() – отображение Париха последовательность .

Свойства:

1. Сохраняемость: с весом w Mw = M`w

M` = M + f()D

Mw = (M + f()D)w

Dw = 0 верно для любого f()

Если решение существует, то находим сразу веса и сеть является сохраняемой с весом w.

2. Задача достижимости: является ли М` достижимой из М с помощью запуска последовательности переходов.

M` = (M, )

M`= M + f()D

M` - M = xD (x – вектор) если решение в виде не отрицательных целых чисел, то разметка достижима.

  1.  Сети Петри для моделирования, одновременность и конфликт, операции над сетями Петри

Событие – действии и переход |

Состояние – некоторое условие

Соответствие между действиями и условиями: действие означает переход, условие – позиции.

Предусловия – состояния, которые описывают условия при который произойдёт переход.

Выполнение событий может привести к выполнению постусловия.

Автомат продавец

Событие

Предусловие

Постусловие

1

-

б

2

а, б

в,г

3

в

а,г

4

г

-

Это было описание одноканальной системы обслуживания.

Не примитивное событие – это событие, длительность которого 0

Примитивное событие – событие, запуск которого рассматривается мгновенно.

С помощью сетей можем генерировать параллельно распределенное управление.

Особенности:

- Параллелизм (одновременность)

- Асинхронность (отсутствие изменения времени, только информация о последнем событии.)

- Недетерминированность (одновременно можем запускать несколько переходов и мы можем с некоторой вероятностью выбрать переход)

2 ситуации:

Конфликт:

оба могут быть запущены, если они разрешены

Одновременность: конфликтов нет

Операции над сетями Петри

1. Слияние переходов (для ситуации параллельных процессов)

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

2. Слияние позиций

Если в одной сети достигнуто описанное состояние, то в другой сети оно тоже достигнуто.

  1.  Языки сетей Петри

Сети Петри у которых языки эквивалентны называются эквивалентными.

Можно рассматривать задачу оптимизации.

Языки также могут быть использованы для изучения свойств.

Сеть Петри можно использовать в качестве котроллера.

- алфавит – конченое множество символов.

* - множество строк над алфавитом

* = + , где -строка – пустая строка, длина которой = 0.

Языки определяются:

1. Начальное состояние: есть несколько способов описания начального состояния:

- M0

-  M = (1 0 0 0)

 - {M0}

Мы будем: М – фиксированная разметка.

2.Помечение сети Петри – функция, которая отображает множество переходов в алфавит

-свободно помечаем сть Петри в которой все переходы помечена по-разному

- помечаем с - переходами

- помечаем без - переходов

помеченные- переходы не появляются в предложенных языках чети Петри.

3. Заключительное состояние сети Петри.

F – множество заключительных состояний

если F – множество заключительных маркировок, то язык L-типа. , M и F, что  и ,  - функция ограничения, - последовательность запуска.

Язык L называется языком сети Петри G-типа если, M и F, что  и (достижимая разметка из М с помощью последовательности переходов , покрывает разметку Mf.

Язык L называется языком сети Петри T-типа если, M: и  определена   не определена. (терминальная)

Язык L называется языком сети Петри P-типа если, M: и  определена.

12 классов языков:

Свободное

с- переходами

без- переходов

L-типа

Lf

L^

L

G-типа

Gf

G^

G

T-типа

Tf

T^

T

P-типа

Pf

P^

P

- помеченная сеть Петри для сети С.

  1.  Свойство замкнутости языков (конкатенация, объединение)

Для простоты рассмотрим язык L сети Петри замкнуты определенными операциями. Будем рассматривать на примере стд языков.

Сети Петри с языком имеент стандартный вид, если:

1) начальная разметка состоит точно из 1 фишки в позиции ps и в других позициях меток нет. при чем она не является выходной позицией ни для 1 вершины.

2) множество заключительных состояний состоит из 1 позиции pn:

а) F={pf},  если нет пустых - строк, F{ps,pf} иначе.

б)  - не является входной позицией не для какого перехода.

в) не определена  и имеющих в pf фишку (M`(pf) > 0)

Всякая сеть Петри эквивалентна сети стандартного вида.

Свойства:

1) конкатенация:

L1L2|={x1x2:x1L1, x2  L2}

L(C1) = (a + b)

L(C2) = {anbn}

L(C`) = (a+b) anbn

Если L1 и L2 языки L-типа, то L1L2 – язык L-типа.

2) объединение:

L(C1) = a(a + b)b

L(C2) = {ambn},m>n>1

L(C`) = a(a+b)b+ ambn

  1.  Свойства замкнутости языков (параллельная композиция, пересечение)

Для простоты рассмотрим язык L сети Петри замкнуты определенными операциями. Будем рассматривать на примере стд языков.

Сети Петри с языком имеент стандартный вид, если:

1) начальная разметка состоит точно из 1 фишки в позиции ps и в других позициях меток нет. при чем она не является выходной позицией ни для 1 вершины.

2) множество заключительных состояний состоит из 1 позиции pn:

а) F={pf},  если нет пустых - строк, F{ps,pf} иначе.

б)  - не является входной позицией не для какого перехода.

в) не определена  и имеющих в pf фишку (M`(pf) > 0)

Всякая сеть Петри эквивалентна сети стандартного вида.

Свойства:

1) параллельная композиция (перемешивание, одновременное выполнение)

,

L1 = {a, b} L2 = {c} => L1 || L2 = {abc, acb, cab}

L(C1) = a(a+b)

L(C2) = ca3ncb2nc

2) пересечение

L(C1) = ca3ncb2nc

L(C2)= ca2ncb3nc

зеркальное отображение


 

А также другие работы, которые могут Вас заинтересовать

67825. ПРАВОВЕ РЕГУЛЮВАННЯ ВИКОРИСТАННЯ ТА ОХОРОНИ АТМОСФЕРНОГО ПОВІТРЯ 92.5 KB
  Одним із основних життєво-важливих елементів навколишнього природного середовища є атмосферне повітря. Значення атмосферного повітря полягає в тому, що воно є основою для забезпечення життєдіяльності біологічних організмів, в тому числі людей, служить захистом...
67826. УНІФІКОВАНІ ВУЗЛИ ПРОМИСЛОВИХ РОБОТІВ (ПРОДОВЖЕННЯ) 1.04 MB
  Мальтійські механізми використовують для повороту ПР, коли необхідно здійснити преривистий рух робочого органу, тобто рух в одному напрямку з періодичними зупинками. Вони отримали розповсюдження в зв’язку з їх конструктивною простотою, простотою виготовлення і експлуатації.
67827. ПРАВОВЕ РЕГУЛЮВАННЯ ВИКОРИСТАННЯ ТА ОХОРОНИ РОСЛИННОГО СВІТУ 117.5 KB
  Рослинний світ становить сукупність усіх видів рослин, а також грибів та утворених ними угруповань на певних території. Це правове визначення рослинного світу як об’єкта навколишнього природного середовища міститься в ст. З Закону України «Про рослинний світ».
67828. ЗАХОПЛЮЮЧІ ПРИСТРОЇ (ЗП) ПРОМИСЛОВИХ РОБОТІВ 1 MB
  Технологічне призначення: захопюючі і утримуючі ЗП призначені для зхахоплення і утримування об‘єктів за допомогою гачків петель вилок лопаток губок пальців голок кліщів еластичних камер струменів повітря магнімного поля вакууму електростатичного притягання адгезії липучих накладок та інших засобів...
67829. ПРАВОВЕ РЕГУЛЮВАННЯ ВИКОРИСТАННЯ ТА ОХОРОНИ ЛІСІВ 101.5 KB
  Ліс є невід’ємною та незамінною частиною світової екосистеми. Значення лісів для навколишнього природного середовища проявляється в корисних властивостях лісів. Корисними властивостями лісів є їх здатність зменшувати вплив негативних природних явищ, захищати ґрунти від ерозії, регулювати стік води...
67830. СИСТЕМА ТРАНСПОРТНИХ І НАКОПИЧУВАЛЬНИХ ЗАСОБІВ РТС. НАВАНТАЖУВАЛЬНО-РОЗВАНТАЖУВАЛЬНІ ЗАСОБИ РТС 1.82 MB
  В загальному випадку транспортна система складається з складів 12 заготівок, оброблених деталей і зібраних виробів, складів 24 напівфабрикатів, інструментів і технологічного оснащення, а також транспортних засобів їхньої доставки і завантажувально-розвантажувальних пристроїв, що забезпечують...
67831. ПРАВОВЕ РЕГУЛЮВАННЯ ВИКОРИСТАННЯ ТВАРИННОГО СВІТУ 86.5 KB
  Відносини у галузі охорони, використання і відтворення тваринного світу, об’єкти якого перебувають у стані природної волі, у напіввільних умовах чи в неволі, на суші, у воді, ґрунті та повітрі, постійно чи тимчасово населяють територію України або належать до природних багатств її континентального...
67832. МІЖНАРОДНО-ПРАВОВЕ РЕГУЛЮВАННЯ ВИКОРИСТАННЯ ПРИРОДНИХ РЕСУРСІВ 125 KB
  Планета Земля, яка є нашим спільним домом, для сучасної людини перестала бути безмежною, в зв’язку з чим, всі природні та інші процеси, які відбуваються в сучасному світі, стали взаємозалежними та взаємопов’язаними. Так, наприклад, пестициди (ДДТ), що використовувалися...
67833. ТРАНСПОРТНІ ТА СКЛАДСЬКІ ЗАСОБИ РТС 418.5 KB
  Конвейєром називають машину для безперервного транспортування виробів. Відмітною особливістю багатьох конструкцій конвейєрів, разом з виконанням функцій по переміщенню заготівок, є можливість утворення невеликих міжопераційних заділів, що забезпечують незалежну роботу складних верстатів в складі РТС.