Лекция
Привет, Вы узнаете о том , что такое сети петри, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое сети петри, моделирование автоматных систем сетями петри , настоятельно рекомендую прочитать все из категории Теория конечных автоматов.
Аппаратом описания сложных систем последовательно-параллельных процессов являются формальные системы типа сетей Петри, моделирующие динамические свойства систем.
Сеть Петри — математический объект, используемый для моделирования динамических дискретных систем, предложенный Карлом Петри в 1962 году.
Определяется как двудольный ориентированный мультиграф, состоящий из вершин двух типов — позиций и переходов, соединенных между собой дугами. Вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры), способные перемещаться по сети. Событием называют срабатывание перехода, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. События происходят мгновенно либо разновременно, при выполнении некоторых условий.
Сеть Петри есть мультиграф, так как он допускает существование кратных дуг от одной вершины графа к другой. Так как дуги являются направленными, то это ориентированный мультиграф. Вершины графа можно разделить на два множества (позиции и переходы) таким образом, что каждая дуга будет направлена от элемента одного множества (позиций или переходов) к элементу другого множества (переходов или позиций); следовательно, такой граф является двудольным ориентированным мультиграфом.
Изначально разрабатывались для моделирования систем с параллельными взаимодействующими компонентами; основные положения теории связи асинхронных компонент вычислительной системы Петри сформулировал в докторской диссертации «Связь автоматов»
Элементы сетей Петри
В сетях Петри вводятся объекты двух типов: динамические – изображаются метками (маркерами) внутри позиций и статические – им соответствуют вершины сети петри . Распределение маркеров по позициям называют маркировкой. Маркеры могут перемещаться в сети. Каждое изменение маркировки называют событием, причем каждое событие связано с определенным переходом. Считается, что события происходят мгновенно и разновременно при выполнении некоторых условий. Каждому условию в сети Петри соответствует определенная позиция. Совершению события соответствует срабатывание (возбуждение или запуск) перехода, при котором маркеры из входных позиций этого перехода перемещаются в выходные позиции. Последовательность событий образует моделируемый процесс. Перемещаемые по сети маркеры часто называют фишками.
Переходы в сети Петри являются событиями, которые изменяют состояния в реальной системе. На рис. 3.1 приведен пример интерпретации сети Петри.
Итак, сеть Петри – это набор
N = (T, P, A), T ∩ Р = Ø,
где Т = {t1, t2, ..., tn} – подмножество вершин, называющихся переходами;
Р = {p1, р2, ..., pm} – подмножество вершин, называющихся позициями (местами);
А ⊆ (T×P) ∩ (P×T) – множество ориентированных дуг.
Некоторые виды сетей Петри:
Сеть Петри – это четверка С = {Р, Т, I, О}, где Р – конечное множество позиций, Т– конечное множество переходов, I: Р → Т∞ – входная функция, отображающая переходы в комплекты переходов, О: Т → Р∞ – выходная функция, отображающая переходы в комплекты позиций. Графически сеть Петри изображают в виде мультиграфа с вершинами двух видов: кружки соответствуют позициям, планки – переходам. Функции I и О представляются дугами (рис. 5.18).
Рис. 5.18
Позиции, дуги из которых ведут в переход tj, называются входными для tj, аналогично позиции, в которые ведут дуги из перехода tj, называются выходными для tj. Множество входных позиций обозначают I(tj), а выходных – О(tj). В сети Петри, изображенной на рис. 5.18,
I(t1) ={p1 , p1, p1},
O(t1) ={p3 , p4, p4}.
ФункцииI и О удобно обобщить и на отображение из позиций в комплекты переходов (Р → Т∞), что позволяет обозначать множества входных и выходных переходов позиции pi, определяемые аналогично множествам входных и выходных позиций перехода, соответственно как I(pi) и O(pi). В сети Петри, изображенной на рис. 5.18, I (p3) = {t1, t2}, O (p3) = { t2,t4}.
Введенные понятия относятся к статической структуре сети Петри. Динамические свойства сети Петри определяются с помощью понятия маркировки. Маркировка μ сети Петри С = (Р, Т, I, О) – это функция, отображающая множество позиций Р в множество неотрицательных целых чисел N. Маркировка изображается с помощью помещаемых внутрь позиций фишек (точек). Так, маркировка сети Петри, приведенной на рис. 5.18, определяется как μ (p1) = μ (p3) = 1, μ (p2) = μ (p4) = μ (p5) = 0
Удобно представлять маркировку как n-вектор μ = (μ1, μ2, …, μn) (где n = |Р|), каждый элемент которого μi есть μ(pi), а также как комплектμ, в который входят позиции сети pi Р и # (pi, μ) = μ (pi). Об этом говорит сайт https://intellect.icu . Сеть Петри С с определенной в ней маркировкой μ называется маркированной сетью Петри.
Маркировка сети может изменяться в результате запуска переходов. Переход tj маркированной сети Петри С с маркировкой μ называется разрешенным, если I (tj) 
μ, т. е. в каждой входной позиции tj находится не меньше фишек, чем из этой позиции исходит дуг в tj. Всякий разрешенный переход может запуститься. В результате запуска перехода tj маркировка сети μ изменяется на новую: μ'= μ – I (tj) + О (tj), т. е. из всякой входной позиции pi перехода ti удаляется столько фишек, сколько дуг ведет из pi в tj, а в каждую выходную позицию pk помещается столько фишек, сколько дуг ведет из tj в pk. Последовательность запусков переходов называется выполнением сети Петри.
Рассмотрим выполнение сети Петри, изображенной на рис. 5.18. В начальной маркировке разрешен только переход t2. При его запуске фишка удалится из p3, а затем в позиции p2 и p3 добавится по фишке, т. е. в результате запуска в новой маркировке μ'появится фишка еще и в p2. Теперь становятся разрешенными переходы t2, t4. Поскольку запуститься может любой переход, предположим, что запускается переход t4. После его запуска из позиции p2 и p3 фишки удалятся, а в позиции p5 появится одна фишка. В получившейся маркировке μ'' не разрешен ни один переход. На этом выполнение сети Петри заканчивается.
Рассмотрим маркировку μ сети Петри С = (Р, Т, I, О). Маркировка μ' называется непосредственно достижимой из μ, если найдется такой переход tj 
T, разрешенный в μ, что при его запуске получается маркировка μ'; в этом случае пара (μ, μ') принадлежит отношению непосредственной достижимости, определенному на Р∞. Это отношение называется отношением достижимости. Маркировки μ' такие, что (μ, μ') принадлежат отношению достижимости, называются достижимыми из μ. Множество достижимых из μ маркировок сети Петри С называется множеством достижимости и обозначается R (С, μ).
Интерпретация сетей Петри основана на понятиях условия и события. Для возникновения события необходимо выполнение некоторых условий, называемых предусловиями. Возникновение события может привести к нарушению предусловий и к выполнению некоторых других условий, называемых пост-условиями. В сети Петри условия моделируются позициями, события – переходами. Предусловия события представляются входными позициями соответствующего перехода, постусловия – выходными позициями. Возникновение события моделируется запуском перехода. Выполнение условий представляется наличием фишек в соответствующих позициях, невыполнение – их отсутствием.
Рассмотрим, например, простую вычислительную систему, последовательно обрабатывающую задания, которые поступают во входную очередь. Когда процессор свободен и во входной очереди имеется задание, оно обрабатывается процессором, затем выводится. Эту систему можно промоделировать сетью Петри, изображенной на рис. 5.19.
Установим, какие особенности систем учитывают сети Петри. Это прежде всего асинхронность. В сети Петри отсутствует понятие времени. Время возникновения событий никак не указывается, но, тем не менее, структура сети Петри устанавливает частичный порядок возникновения событий. Далее, поскольку возникновение событий представляется запуском переходов, предполагается, что события происходят мгновенно. Если же моделируемое событие имеет отличную от нуля длительность, как, например, событие «задание обрабатывается» (рис. 5.19), и это существенно, то оно представляется в виде двух мгновенных событий типа «начало события», «конец события» и условия «событие происходит» (рис. 5.20). Кроме того, считается, что события происходят неодновременно (мгновенные события не могут происходить одновременно). Действительно, если допустить одновременное возникновение некоторых событий i и j, которым в сети Петри соответствуют переходы ti и tj, то можно ввести дополнительный переход tij с I (tij) = I (ti) + I (tj), О (tij) = О (ti) + О (tj), интерпретирующийся как одновременное возникновение событий i и j. В этом случае переходы можно запускать последовательно.
Сети Петри используют в основном как формальный аппарат при моделировании систем, которым присущ параллелизм. Возможны два принципиально различных подхода к использованию сетей Петри. В первом система моделируется сетью Петри, которая преобразуется по определенным правилам к некоторому «оптимальному» виду. Во втором, более общепринятом, подходе сначала с помощью обычных средств создается проект системы и по нему строится модель в виде сети Петри. Затем исследуются свойства полученной сети и делаются выводы о свойствах и характеристиках проекта. Этот процесс заканчивается, когда сеть Петри будет обладать необходимыми свойствами.
Одной из наиболее важных задач анализа сетей Петри является задача достижимости: достижима ли маркировка μ' из начальной маркировки μ данной сети Петри? Важность этой задачи обусловлена тем, что маркировка служит интерпретацией состояния системы. Решение задачи достижимости позволит определить, достижимо ли определенное состояние, будь оно «хорошим» или «плохим» для системы.
Рис. 5.21
Для решения задач анализа имеется два основных подхода. Первый основан на построении дерева достижимости. Дерево достижимости – это ориентированное корневое дерево, вершинам которого соответствуют возможные маркировки, дугам – переходы. Корневой вершине соответствует начальная маркировка. Из каждой вершины исходят дуги, соответствующие разрешенным переходам. Построение дерева осуществляется последовательно, начиная с корневой вершины; на каждом шаге строится очередной ярус дерева. Например, дерево достижимости для сети Петри, изображенной на рис. 5.21а, после трех шагов имеет вид, приведенный на рис. 5.22а (маркировки представлены векторами). Очевидно, что если не использовать при построении дерева определенные соглашения, то активные (даже ограниченные) сети Петри будут иметь бесконечное дерево достижимости.
Рис. 5.22
Назовем вершины (и соответствующие маркировки), построенные на очередном шаге алгоритма, граничными. Если в какой-либо граничной маркировке нет разрешенных переходов, то будем называть такую маркировку терминальной. Если какая-либо граничная вершина имеет маркировку, уже существующую в дереве, то назовем ее дублирующей. Для терминальных и дублирующих вершин не будем строить исходящих из них дуг. Это обеспечивает конечность дерева достижимости для ограниченной сети Петри (например, рис. 5.21а, 5.22а). Для неограниченных сетей требуется как-то обозначить неограниченное число фишек в позиции. Пусть ω обозначает такое число, причем ω + а = ω, ω – а = ω, а < ω, ω ≤ ω, где а – произвольное целое положительное число. Будем использовать при построении дерева достижимости следующее правило. Пусть граничная вершина μ не является терминальной или дублирующей. Для каждого разрешенного перехода tj в маркировке μ построим дугу, исходящую из μ. Дугу будем помечать переходом tj. Маркировка μ' новой вершины определяется следующим образом. Если 
(pi) = ω, то μ'(pi) = ω. Если на пути от корневой вершины к μ существует вершина μ'', такая, что в результате запуска в μ перехода tj число фишек в каждой позиции не меньше чем в μ'', а в позиции pi строго больше, то μ'(pi) = ω. В противном случае μ'(pi) – число фишек в позиции pi, получающееся после запуска tj из μ (рис. 5.22б).
Рис. 5.23
Непосредственная трактовка сети Петри возможна в двух вариантах: прямом и инверсном. Инверсный вариант заключается в том, что условия связывают с переходами сети, а события – с позициями.
Прямой вариант состоит в том, что условия связывают с позициями сети, а события – с переходами. Обратимся к рис. 5.23, где представлена модель обслуживания очереди заявок со стороны двух процессов, претендующих на использование некоторого разделяемого ресурса. Фишка в позиции Р1 означает, что поступила заявка от первого процесса, а фишка в позиции Р2свидетельствует о приходе заявки со стороны второго процесса. Наличие фишки в позиции Р3 говорит о том, что ресурс свободен. Начальная маркировка показана на рис. 5.23а. Допустим, что заявка от первого процесса поступила несколько раньше. При этом срабатывает переход t1. Это значит, что из очереди к ресурсу выбран первый процесс, после чего достигается маркировка, показанная на рис. 5.23б.
Следующим срабатывает переход t7, причем в рамках перехода первый процесс использует выделенный ему ресурс, а очередной маркировкой будет та, которая приведена на рис. 5.23в. В этой ситуации существуют условия для срабатывания перехода t3. Это срабатывание означает, что первый процесс обрабатывает результаты, связанные с использованием ресурса, а новая маркировка приобретает вид, представленный на рис. 5.23г.
Теперь складываются условия для освобождения ресурса первым процессом: срабатывает переход t5. Достигнутая при этом маркировка (рис. 5.23д) означает, что ресурсом может воспользоваться второй процесс. На этом завершается цикл работы первого процесса. Опишем его в терминах событий и условий.
Событие t1. Действие: выбор первого процесса из очереди к ресурсу.
Предусловие: Р1 – есть заявка от первого процесса; Р3 – ресурс свободен.
Постусловие: Р4, Р6 – заявка первого процесса выполнена.
Событие t7. Действие: использование первым процессом ресурса.
Предусловие: Р6 – заявка первого процесса выполнена.
Постусловие: Р7 – результаты от использования первым процессом ресурса получены.
Событие t3. Действие: обработка результатов, связанных с использованием ресурса.
Предусловие: Р4 – заявка первого процесса выполнена; Р7 – результаты от использования первым процессом ресурса получены.
Постусловие: Р8 – обработка результатов, связанных с использованием ресурса, закончена.
Событие t5. Действие: освобождение первым процессом ресурса.
Предусловие: Р8 – обработка результатов, связанных с использованием ресурса, закончена.
Постусловие: Р10 – первый процесс завершил цикл своей работы; Р3 – ресурс свободен.
В инверсном варианте сети Петри позиции соответствуют операциям (т.е. событиям) реализуемого процесса, а переходы – условиям (т.е. состояниям) смены операций. Переходу соответствует операторная формула вида
Z(t) =F(хl(t), ..., xn(t)),
где Z (t) – выходная логическая переменная; F – оператор; xi(t), i = 1, n – входные логические переменные.
Истинность выходной логической переменной является необходимым условием срабатывания перехода.
1. Построить конечный автомат, продающий пиво и выдающий сдачу. Автомат может принимать монеты достоинством 5 и 10 пенсов, а кружка пива стоит 15 пенсов. Кроме отверстий для приема монет и выдачи сдачи, у автомата есть кнопки «Налив» и «Сброс».
2. Построить КА, выбрасывающий все комментарии из программы на языке Си с учетом возможных строковых констант, которые, конечно, изменять нельзя. Комментарий в языке Си – это любая строка, ограниченная сложными скобками: /* ... */ либо парой слэшей // и концом строки. Внутри строковой константы могут встретиться константные символы. Они вводятся с двойными кавычками.
3. Построить КА, выдающий остаток от деления вводимого десятичного числа на 3.
4. Построить КА, выдающий результат деления вводимого 5-ричного числа на 3. Результат выдается в форме: <частное> (<остаток>). Число вводится со старших разрядов и заканчивается маркером конца «#». Результат представляется также в пятеричной системе счисления.
5. Построить КА, выдающий остаток от деления вводимого троичного числа на 4. Построить два варианта автомата: для случая, когда число вводится со старших разрядов, и для случая, когда число вводится с младших разрядов.
6. Построить КА, выбрасывающий лишние пробелы в тексте.
7. Построить КА, добавляющий бит нечетности к цепочке из 0 и 1.
8. Построить автомат Мура, управляющий светофором автоматического регулирования транспорта на обычном перекрестке. Учесть, что в одном направлении разрешено движение t1 секунд, а в другом – t 2 секунд.
Указание. Единственным входным событием автомата является событие завершения тайм-аута. Поэтому это – автономный автомат, который выдает циклическую последовательность выходов.
9. (Автоматический светофор). Решите проблему регулирования транспорта на Т-образном перекрестке (рис. 5.24), на котором основной поток транспорта идет с запада на восток, а с юга подходит второстепенная дорога.
Четыре светофора управляют движением транспорта, каждый может показывать один из трех сигналов:К, Ж, 3. Очевидно, что они должны управляться согласованно, причем так, чтобы не создавалась аварийная ситуация (например, не было бы сигнала «Зеленый» на всех четырех светофорах). Устройство управления выдает четверки сигналов, например, <К;3;Ж;3> – на первом светофоре красный, на втором и четвертом – зеленый, а на третьем – желтый. Рис. 5.24
Считая, что транспорт в направлении второстепенной дороги движется редко, построить конечный автомат Мура, управляющий перекрестком по запросам транспорта. Запросы транспорта автоматически передаются с помощью сенсоров α и β. На этих сенсорах устанавливается значение 1, если в соответствующем месте появляется машина. Входами в автомат управления служат пары <0,0>; <0,1>; <1,0>; <1,1> состояний сенсоров (α и β, а выходами – четверки сигналов светофоров.
Анализ данных, представленных в статье про сети петри, подтверждает эффективность применения современных технологий для обеспечения инновационного развития и улучшения качества жизни в различных сферах. Надеюсь, что теперь ты понял что такое сети петри, моделирование автоматных систем сетями петри и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Теория конечных автоматов
Комментарии
Оставить комментарий
Теория конечных автоматов
Термины: Теория конечных автоматов