WWW.LIB.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Электронные материалы
 

«Сети Петри Карл Адам Петри Применение Моделирования тех систем, которые содержат взаимодействующие параллельные компоненты. Основные элементы сетей Петри ...»

Сети Петри

Карл Адам Петри

Применение

Моделирования тех систем, которые содержат

взаимодействующие параллельные компоненты.

Основные элементы сетей Петри

C=(P,T,I,O), где

множество позиций P,

множество переходов T,

входная функция I и

выходная функция O.

Входы/выходы

Входная и выходная функции связаны с

переходами и позициями.

Входная функция I отображает переход tj в

множество позиций I(tj), называемых входными

позициями перехода.

Выходная функция O отображает переход tj в множество позиций O(tj), называемых выходными позициями перехода.

Структура сети Петри определяется её позициями, переходами, входной и выходной функциями.

Определение Сеть Петри С является четверкой, C=(P,T,I,O).

P={p1, p2,..., pn} - конечное множество позиций, n=0.

T={ t1, t2,..., tm } - конечное множество переходов, m=0.

Множество позиций и множество переходов не пересекаются, то есть пересечение P и T равно пустому множеству. I: T-P является входной функцией - отображением из переходов в комплекты позиций. O: T-P есть выходная функция отображение из переходов в комплекты позиций.

Пример C=(P,T,I,O) P= {p1, p2, p3, p4, p5} T= { t1, t2, t3, t4} I( t1 )={ p1} O(t1)={ p2, p3, p5 } I( t2 )= { p2, p3, p5 } O(t2)={ p5 } I( t3 )={ p3} O(t3)={ p4 } I( t4 )={ p4} O(t4 )={ p2, p3 } Расширенные функции входа/выхода Расширенные функции зависят не от перехода, а от позиции.



I ( p1 )={ } O( p1 )={t1} I ( p2 )= { t1, t4 } O( p2 )={t2} I ( p3 )={ t1, t4 } O( p3 )={t2, t3} I ( p4 )={ t3} O( p4 )={t4} I ( p5 )= { t1, t2 } O( p5 )={t2} Представление сети Петри с помощью графов Теоретико-графовым представлением сети Петри является двудольный ориентированный мультиграф.

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

Кружок ”O” является позицией, а планка ”|” переходом.

Представление сети Петри с помощью графов Ориентированные дуги (стрелки) - соединяют позиции и переходы, при этом некоторые дуги направлены от позиций к переходам, а другие - от переходов к позициям.

Дуга, направленная от позиции pi к переходу tj, определяет позицию, которая является входом перехода. Кратные входы в переход указываются кратными дугами из входных позиций в переход.

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

Пример C=(P,T,I,O) P= {p1, p2, p3, p4, p5} T= { t1, t2, t3, t4} I( t1 )={ p1} O(t1)={ p2, p3, p5 } I( t2 )= { p2, p3, p5 } O(t2)={ p5 } I( t3 )={ p3} O(t3)={ p4 } I( t4 )={ p4} O(t4 )={ p2, p

–  –  –

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

Пример Маркированная сеть Петри. Маркировка - (1, 2, 0, 0, 1) Множество маркировок Так как количество фишек, которое может быть определено для каждой позиции, неограниченно, то в целом для сети Петри существует бесконечно много маркировок.

Множество всех маркировок сети Петри, обладающей n позициями, есть множество всех n-векторов, Nn.

Это множество, хотя и бесконечно, является счетным.

Правила выполнения сетей Петри Выполнением сети Петри управляют количество и 1.

–  –  –

выполнением переходов сети.

Сеть Петри выполняется посредством запусков 3.

переходов.

Переход запускается удалением фишек из его 4.

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

когда он разрешен.

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

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

Кратные фишки необходимы для кратных входных 7.

дуг.

Правила выполнения сетей Петри Фишки во входной позиции, которые разрешают 8.

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

Например, если позиции p1 и p2 служат входами для перехода t4, тогда t4 разрешен, если p1 и p2 имеют хотя бы по одной фишке. Для перехода t7 c входным комплектом {p6, p6, p6} позиция p6 должна обладать, по крайней мере, тремя фишками, для того, чтобы t7 был разрешен.

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

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

Правила выполнения сетей Петри Кратные фишки создаются для кратных выходных 10.

дуг.

Переход t3 с I(t3) = {p2} и O(t3) = {p7, p13} разрешен всякий раз, когда в p2 будет хотя бы одна фишка.

Переход t3 запускается удалением одной фишки из позиции p2 и помещением одной фишки в позицию p7 и в p13 (его выходы). Дополнительные фишки в позиции p2 не влияют на запуск t3 (хотя они могут разрешать дополнительные запуски t3).

Переход t2, в котором I(t2) = { p21, p23} и O(t2) = {p23, p25, p25} запускается удалением одной фишки из p21 и одной фишки из p23, при этом одна фишка помещается в p23 и две

- в p25 (так как p25 имеет кратность, равную двум).

Правила выполнения сетей Петри Запуск перехода в целом заменяет 11.

–  –  –

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

Запуск перехода никогда не удалит фишку, 13.

отсутствующую во входной позиции.

Если какая-либо входная позиция перехода не 14.

обладает достаточным количеством фишек, то переход не разрешен и не может быть запущен.

Пример

–  –  –

Маркировка, полученная в результате запуска перехода t3 Запуск сетей Петри Запуски могут осуществляться до тех пор, пока существует хотя бы один разрешенный переход.

Когда не останется ни одного разрешенного перехода, выполнение прекращается.

Пространство состояний сети Петри Состояние сети Петри определяется ее маркировкой. Запуск перехода изменяет состояние сети Петри посредством изменения маркировки сети Петри.

Пространство состояний сети Петри, обладающей n позициями, есть множество всех маркировок, т.е. Nn. Изменение в состоянии, вызванное запуском перехода, определяется функцией изменения которую мы b, назовем функцией следующего состояния.

Функция следующего состояния Когда эта функция применяется к маркировке m (состоянию) и переходу tj, она образует новую маркировку (состояние), которая получается при запуске перехода tj в маркировке m.

Так как tj может быть запущен только в том случае, когда он разрешен.

Функция b(m, tj) не определена, если tj не разрешен в маркировке m.

Если же tj разрешен, то b(m, tj) = m', где m' есть маркировка, полученная в результате удаления фишек из входов tj и добавления фишек в выходы tj.

Функция следующего состояния Пусть дана сеть Петри C = (P, T, I, O) с начальной маркировкой m0. Эта сеть может быть выполнена последовательными запусками переходов. Запуск разрешенного перехода tj в начальной маркировке образует новую маркировку m1 = b( m0, tj). В этой новой маркировке можно запустить любой другой разрешенный переход, например, образующий новую tk, маркировку m2 = b(m1, tk).

Выполнение сети Петри При выполнении сети Петри получаются две последовательности:

последовательность маркировок ( m0, m1, m2, …)

–  –  –

запущены (tj0, tj1, tj2,...).

Эти две последовательности связаны следующим соотношением:

b(mk, tjk) = mk+1 для k = 0, 1, 2,....

Непосредственно достижимая маркировка Для сети Петри C = (P, T, I, O) с маркировкой m маркировка m' называется непосред ственно достижимой из m, если существует переход tj, принадлежащий T, такой, что b (m, tj) = m'.

Множество достижимости Множество достижимости R(C, m) для сети Петри C = (P, T, I, O) с маркировкой m есть наименьшее множество маркировок, определенных следующим образом:

m принадлежит R(C, m) ;

1.

–  –  –

Для данной сети Петри и маркировки m=(1, 0, 0) непосредственно достижимыми являются две маркировки: (0, 1, 0) и (1, 0, 1).

Из (0, 1, 0) нельзя достичь ни одной маркировки, так как ни один переход не разрешен.

Из (1, 0, 1) можно получить (0, 1, 1) и (1, 0, 2).





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

Условие - это предикат или логическое описание состояния системы. Условие может принимать либо значение "истина", либо значение "ложь".

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

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

Эти условия называют предусловиями события.

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

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

Пример (условия и события)

Условия:

автомат-продавец ждет;

заказ прибыл и ждет;

автомат-продавец выполняет заказ;

заказ выполнен.

События:

Заказ поступил.

Автомат-продавец начинает выполнение заказа.

Автомат-продавец заканчивает выполнение заказа.

Заказ посылается на доставку.

Похожие работы:

«ГОСУДАРСТВЕННЫЙ СТАНДАРТ COL А А ССР НАДЕЖНОСТЬ В ТЕХНИКЕ Теркины и определения ГОСТ Т3377-75 Издание оЗД шальное : Издавельство стандартов Москва РАЗРАБОТАН Всесоюзным кзучно-исследовательским институтом стандартизации jBHHHC) Директор института Гличев А, В. Руководитель темы Мартынов Г,...»

«Національний технічний університет України “Київський політехнічний інститут” _ Кафедра інформаційно-телекомунікаційних мереж Лекция 1.6 BPMN Лекция 1.6 BPMN Лектор: к.т.н. Кот Т.М. Національний технічний університет України “К...»

«Версия 2014.1 Функциональные возможности: АРМ Каталогизатор 1. Обеспечена возможность выполнения ПАКЕТНЫХ ЗАДАНИЙ (по аналогии с АРМом Администратор-клиент см. релиз 2013.1) В связи с этим в раздел СЕРВИС главного меню введен режим ВЫПОЛНИТЬ ПАКЕТНОЕ ЗАДАНИЕ Поддерживаются только те команды пакетных заданий, которые связаны с функциона...»

«1 ВЛИЯНИЕ УСЛОВИЙ ИСПЫТАНИЯ НА МОДУЛЬ ДЕФОРМАЦИИ ГРУНТОВ Болдырев Г.Г., Гордеев А.В., Новичков А.Г. (ООО "НПП Геотек", ООО "Строй-Тех") Летом 2007 года на площадке проектируемого трехсекционного 9-ти этажного жилого дома в г.Набережные...»

«Побожий С.И., кандидат искусствоведения ДАВИД БУРЛЮК ИЗ ПРОШЛОГО ВЕКА Несмотря на то что за последние 20 лет в российских и украинских музеях, галереях состоялось немало выставок Давида Давидовича Бурлюка (1882–1967), мы еще далеки от полнома...»

«УДК 534.8+620 PACS: 43.60.+d Расчёт АРД диаграмм для систем ультразвукового контроля с применением фазированных решёток Базулин А.Е., Базулин Е.Г., Исмаилов Г.М. ООО "Научно-производственный центр "Эхо+" 123458, Москва, ул. Твардовского, д. 8, Технопарк "Строгино" E-mail: bazulin@echoplus.ru В статье описан подход к измерен...»

«2013, № 2 (32) Сергей СУЛЯК КАЗАК АНДРЕЙ СУЛЯК (к вопросу об участии выходцев из Молдавии в гайдамацком движении 1734 г.) Выходцы из Молдавии (русины и молдаване), называемые волохами (молдаванами), что указывало на их государственную принадлежность1, активно участвовали в общественно-политической ж...»

«Правила конкурса "Большой куш" Содержание 1. Регистрация и условия участия 2. Совершение операций по конкурсному счету 3. Завершение очередного тура конкурса и определение победителей 4. Перечень призов и награждение побе...»










 
2017 www.lib.knigi-x.ru - «Бесплатная электронная библиотека - электронные материалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.