Теория сетей Петри и моделирование систем
Утверждено Редакционно-издательским советом университета
в качестве учебного пособия
НОВОСИБИРСК
2010
УДК 004.421 (075.8)
В 316
Рецензенты: <...> Структура сети Петри
Сеть Петри состоит из четырех элементов: множество позиций Р,
множество переходов Т, входная функция I и выходная функция O. <...> Входная и выходная функции связаны с переходами и позициями. <...> Входная функция I отображает переход tj в множество позиций I(tj),
называемых входными позициями перехода. <...> Выходная функция O
отображает переход tj в множество позиций O (tj), называемых выходными позициями перехода. <...> Структура сети Петри определяется ее позициями, переходами,
входной и выходкой функциями. <...> I : T → P∞ является входной
функцией – отображением из переходов в комплекты позиций. <...> O : T → P∞
есть выходная функция – отображение из переходов в комплекты позиций. <...> Позиция pi является входной позицией перехода tj в том случае,
если pi I(t j); pi является выходной позицией, если pi O(tj). <...> Входы и
выходы переходов представляют собой комплекты позиций. <...> Использование комплектов, а не множеств для входов и выходов перехода
позволяет позиции быть кратным входом либо кратным выходом перехода. <...> Кратность входной позиции pi для перехода tj есть число появлений позиции во входном комплекте перехода, #( pi, I(tj)). <...> Аналогично кратность выходной позиции pi для перехода tj есть число
3
появлений позиции в выходном комплекте перехода, #( pi, O(tj)). <...> Если
входная и выходная функции являются множествами (а не комплектами), то кратность каждой позиции есть либо 0, либо 1. <...> Входные и выходные функции используются для отображений позиций в комплекты переходов, а также их можно использовать для
отображения переходов в комплекты позиций. <...> Определим, что переход
tj является входом позиции pi, если pi есть выход tj. <...> Переход tj есть
выход позиции pi, если pi есть вход tj. <...> Теоретико-графовым представлением сети
Петри является двудольный ориентированный мультиграф. <...> В соответствии с этим <...>
Теория_вычислительных_процессов._Ч._2._Теория_сетей_Петри_и_моделирование_систем.pdf
Министерство образования и науки Российской Федерации
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Е.Л. ВЕРЕТЕЛЬНИКОВА
ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ
ПРОЦЕССОВ
Часть 2. Теория сетей Петри и моделирование систем
Утверждено Редакционно-издательским советом университета
в качестве учебного пособия
НОВОСИБИРСК
2010
Стр.1
УДК 004.421 (075.8)
В 316
Рецензенты:
И.А. Полетаева, канд. техн. наук, доцент,
А.А. Боровков, канд. техн. наук, доцент
Работа подготовлена на кафедре автоматики для студентов
III–IV курсов АВТФ дневного и заочного отделений, обучающихся
по специальности 230105
В 316
Веретельникова Е.Л.
Е.Л. Вере-тельникова. – Новосибирск : Изд-во НГТУ, 2010. – Ч. 2.
Теория сетей Петри и моделирование систем. – 60 с.
основных принципов построения сетей Петри и их использования в моделировании.
Пособие подразделено на темы, в рамках каждой из которых предложены
теоретический материал, проиллюстрированный примерами, а также
упражнения для самостоятельной работы.
Пособие адресовано студентам, изучающим теорию вычислительных
процессов.
УДК 004.421 (075.8)
Вертельникова Евгения Леонидовна
ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ
Часть 2
ТЕОРИЯ СЕТЕЙ ПЕТРИ И МОДЕЛИРОВАНИЕ СИСТЕМ
Учебное пособие
Выпускающий редактор И.П. Брованова
Корректор Л.Н. Киншт
Редактор Н.В. Городник
___________________________________________________________________________________
Подписано в печать 03.03.2010. Формат 60 Ч 84 1/16. Бумага офсетная. Тираж 100 экз.
Уч.-изд. л. 3,48. Печ. л. 3,75. Изд. № 258. Заказ № Цена договорная
___________________________________________________________________________________
Отпечатано в типографии
Новосибирского государственного технического университета
630092, г. Новосибирск, пр. К. Маркса, 20
ISBN 978-5-7782-1340-1
2
© Веретельникова Е.Л., 2010
© Hовосибиpский государственный
технический университет, 2010
Компьютерная верстка Л.А. Веселовская
Дизайн обложка А.В. Ладыжская
ISBN 978-5-7782-1340-1
Приведены теоретический материал и практические задания для освоения
Теория вычислительных процессов : учеб. пособие /
Стр.2
Содержание
Тема 1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ............................................... 3
1.1. Структура сети Петри .................................................................... 3
1.2. Графы сетей Петри ........................................................................ 5
1.3. Маркировка сетей Петри ............................................................. 10
1.4. Правила выполнения сетей Петри .............................................. 11
1.5. Пространство состояний сети Петри .......................................... 14
Тема 2. СЕТИ ПЕТРИ ДЛЯ МОДЕЛИРОВАНИЯ ........................... 20
2.1.События и условия ....................................................................... 20
2.2. Конечные автоматы ..................................................................... 23
2.3. Представление блок-схемы сетями Петри .................................. 26
2.4. Задачи синхронизации ................................................................. 30
Задача о взаимном исключении .................................................. 30
Задача о производителе/потребителе .......................................... 32
Задача об обедающих мудрецах .................................................. 34
Задача о чтении/записи................................................................ 35
2.5. Химические системы ................................................................... 37
Тема 3. АНАЛИЗ СЕТЕЙ ПЕТРИ ...................................................... 39
3.1. Задачи анализа сетей Петри ........................................................ 39
Безопасность ................................................................................ 39
Ограниченность ........................................................................... 39
Сохранение .................................................................................. 40
Активность................................................................................... 42
Достижимость и покрываемость ................................................ 43
3.2. Методы анализа ........................................................................... 44
Дерево достижимости.................................................................. 44
Матричные уравнения ................................................................. 54
Литература.............................................................................................. 58
Приложение. Расчетно-графическое задание. ....................................... 59
Стр.61