Практическое занятие №3: Раскрашенные сети Петри

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №3 ПРЕДСТАВЛЕНИЕ МОДЕЛИ ОБЪЕКТА В ВИДЕ
РАСКРАШЕННОЙ СЕТИ ПЕТРИ
1 Цель занятия
Научится строить и исследовать раскрашенные сети Петри.
2 Общие теоретические сведения
В классических сетях Петри все маркеры однотипные и элементарные, а в раскрашенной сети Петри
использует различные типы маркеров. Первоначальные попытки различать маркеры сети Петри были связаны
с присваиванием им характеристик, представленных натуральным числом: маркер типа 1, маркер типа 2,
маркер типа 3 и т.д. Также индивидуальность маркерам присваивалась путем разрешения перехода и
результатов их срабатывания. Индивидуальность маркеров наиболее наглядно (для небольшого числа их
типов) изображают с помощью цвета: зеленый, красный, синий и т.п. Поэтому сети, различающие
характеристики маркеров (или их групп) традиционно называют раскрашенными, даже если маркер
представлен переменной сложного абстрактного типа. Раскраска вершин-позиций, т.е. использование
разноцветных маркеров, позволяет учесть разнородность состояний или потоков информации, отображаемой в
сети Петри.
Цветные сети Петри характеризуются следующими особенностями (рис. 1, а–б):
– разметка сети задается с помощью индивидуальных, т. е. различимых маркеров;
– за каждым маркером в раскрашенной сети может быть закреплен соответствующий цвет (тип);
– функционирование раскрашенной сети Петри зависит не только от наличия маркеров во входных
позициях, но также и от их цвета (типа);
– позиции также могу иметь цвет, при этом позиция может содержать маркеры только приписанного ей
цвета (типа);
– переход раскрашенной сети Петри может сработать, если в каждой входной позиции имеются маркеры с
цветом и в количестве, определенным цветом (или значением выражения) соответствующей входной дуги
перехода или цветом самого перехода;
– спецификация раскрашенной сети Петри включает не только описание структуры (позиций, переходов,
дуг), но и декларации сети Петри, которые состоят из описания множеств цветов (типов), объявления
переменных, операций или функций;
– за каждым элементом раскрашенной сети Петри закрепляется соответствующая метка: имя, множество
цветов, инициализирующее выражение или охранные функции;
– каждая позиция может иметь три разных типа меток: имя, множество цветов и инициализирующее
выражение;
– переход может содержать два типа меток: имя перехода и охранные функции (логическое выражение,
которое должно быть выполнено до срабатывания перехода);
– дуга может быть описана двумя типами меток: инициализирующим выражением и множеством цветов;
– при срабатывании перехода маркеры удаляются из его входных позиций и добавляются в выходные
позиции согласно количеству и цвету дуг, позиций или инициализирующему выражению при заданном
связывании позиции и перехода.
P2
P1
t1
Красный
Зеленый
Красный
Зеленый
Голубой
а
Красный
P1
t1
Красный
Зеленый
P2
Зеленый
Голубой
б
Рис. 1. Простейшая раскрашенная Сеть Петри: а – ситуация до срабатывания перехода t1; б –
ситуация после срабатывания перехода t1
Основной причиной высокой эффективности раскрашенных сетей Петри является то, что они позволяют получить
значительно более краткие и удобные описания, в отличие от тех, которые могут быть получены с помощью простых
сетей Петри. В сетях высокого уровня сложность моделей может быть разделена между структурой сети,
инициализирующими выражениями и описанием. Это позволяет осуществлять описание значительно более сложных
систем и анализировать процессы преобразования данных с помощью общепринятых выражений вместо сложного
набора позиций, переходов и дуг.
Рассмотрим модель процесса сдачи экзамена для системы кафедра. Имеется три типа позиций: студенты,
преподаватель и экзаменационные билеты. Определены три множества цветов: множество с элементами «студент»,
множество с элементами «преподаватель» и множество с элементами «экзаменационный билет». Чтобы запустить
переход t1 (принятие экзамена), необходимо наличие маркеров в позициях студент, преподаватель и экзаменационный
биле (рис. 1, а). Переменные «студент, «преподаватель» и «билет» используются для извлечения маркеров из входных
позиций и добавления их в выходные позиции сети.
После того, как один из студентов сдаст экзамен, из студенческой группы выбирается следующий студент,
экзаменационный билет и преподаватель. Студент, который был извлечен из позиции P1, будет помещен в позицию P4,
так как выходной дуге перехода t1, присвоена переменная с именем «студент». Преподаватель, который был извлечен из
позиции P2, будет возвращен в позицию P2, так как выходной дуге перехода t1, присвоена переменная с именем
«преподаватель». Экзаменационный билет, который был извлечен из позиции P3, будет помещен в позицию P5, так как
выходной дуге перехода t1, присвоена переменная с именем «билет» (рис. 2, б).
P1
Студенты=25
студент
P2
P4
студент
преподаватель
Преподаватели=2
билет
билет
P3
Студенты=0
Экзаменационные
билеты=0
P5
Экзаменационные
билеты=30
а
P1
Студенты=24
студент
P2
P4
студент
преподаватель
Преподаватели=2
билет
билет
P3
Студенты=1
Экзаменационные
билеты=1
P5
Экзаменационные
билеты=29
б
Рис. 2. Пример цветной Сети Петри: а – ситуация до срабатывания перехода t1; б – ситуация
до срабатывания перехода t1
3 Задачи для самостоятельного решения студентами
Варианты:
1 Покупка автомобиля
2 Покупка продуктов
3 Покупка туристического тура
4 Подача документов в вуз
5 Покупка верхней одежды в магазине
6 Заказ веб-страницы
7 Заказ обеда в ресторане
8 Заказ и выполнение фотосессии
9 Покупка товара в интернет-магазине
10 Покупка смартфона и аксессуаров
11 Заказ справки в деканате
12 Съём квартиры
13 Покупка еды в столовой
14 Пошив одежды на заказ
15 Покупка стационарного компьютера
Пример позиций: осознание необходимости, расчёт с кассиром, выбор транспорта для
посещения магазина, анализ прайс-листа, оформление кредита в банке и т.д.
3.1. Для каждого варианта выделить не менее 3-х потоков (например, документы, финансы,
люди, реклама и т.д.) с не менее 3-мя ветвлений. Построить раскрашенную сеть Петри на не менее 20
позиций. Для сети Петри привести список всех позиций и переходов с обозначениями.
3.2. Провести анализ свойств построенной сети Петри по аналогии с практикой № 2.