Расширенные модели сетей Петри (области ограничения, переходы исключающее или, сети со сдерживающими дугами, сети с приоритетами, временные сети)

Одно из ограничений на моделирование с помощью сетей Петри - это невозможность проверить некоторую неограниченную позицию на наличие точно определенной маркировки. Это ограничение называется проверкой на нуль и означает, что сеть Петри не может проверить неограниченную позицию на нуль. Расширение сети Петри направлено на создание возможности проверки на нуль.

Область ограничения — это множество позиций. Правило запуска модифицируется таким образом, что переход может быть запущен тогда и только тогда, когда в результирующей маркировке не все позиции, входящие в область ограничения, одновременно имеют фишки (не пусты). Например, если {p1, p4} есть область ограничения, то в любой момент времени либо p1 либо p4 должны быть пусты. Если p1 не пуста, то фишка не может быть помещена в p4 до тех пор, пока все фишки из р1 не будут удалены, и наоборот.

Переход исключающее или С использованием области ограничения.

Переключатель — это специальный переход со специальным входом, называемым переключающим, и точно двумя выходами (один помечен символом е для пустого переключающего входа, а другой помечен символом f — для непустого переключающего входа). Переключаемый переход запускается, когда он разрешен (независимо от состояния специального переключающего входа). Когда он запускается, фишка помещается в выход, помеченный символом е, если переключающий вход пуст, или в выход, помеченный символом f, если переключающий вход не пуст. Таким образом, в зависимости от состояния переключателя запуск переключаемого перехода приведет к одной из двух возможных маркировок. Фишка удаляется из переключающего входа, если он имел ее, поэтому после того, как переключаемый переход запустится, переключающий вход будет пуст.

Позиция переключающего входа изображе- а в виде пятиугольника. а — пустой переключатель; б — полный переключатель.

Ингибиторная сеть со сдерживающими дугами.

 сдерживающая дуга (   -отрицание)

Правило запуска сети: переход считается разрешенным если фишки присутствуют во всех его обычных входах и отсутствуют в сдерживающих. Ингибиторная сеть - самый мощный класс расширения сетей Петри. Все другие расширения эквивалентны ингибиторным сетям.

Сети с приоритетами  Переходам могут быть сопоставлены приоритеты, тогда если 2 перехода t1 и t2 разрешены, то запустится тот, у которого выше приоритет.

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

22. Содержание

    • Математическая индукция. Принципы простой индукции, модифицированной простой индукции, строгой индукции.
    • 1) Доказать, что справедливо s(1);
    • Основные принципы доказательства правильности для блок-схем с использованием индукции. Инварианты цикла при доказательстве правильности.
    • Метод индуктивных утверждений как обобщение метода доказательства правильности с использованием индукции. Верификация программ.
    • Метод индуктивных утверждений.
    • Метод индуктивных утверждений
    • Надежность программных средств
    • Доказательство правильности программы
    • Формализация доказательства с помощью индуктивных утверждений. Множество условий верификации.
    • Аксиоматический подход к доказательству частичной правильности и его идентичность методу индуктивных утверждений.
    • Рекурсивные программы. Доказательство их правильности методом структурной индукции. Рекурсия
    • Метод структурной индукции
    • Моделирование. Природа моделируемых систем. Применение теории сетей Петри. Прикладная и чистая теории сетей Петри.
    • Структура сетей Петри. Способы задания сетей Петри. Графы сетей Петри.
    • Маркировка сетей Петри. Правила выполнения сетей Петри. Пространство состояний сетей Петри.
    • События и условия. Моделирование процесса сетью Петри. Примитивные и непримитивные события. Одновременность и конфликт.
    • Сети Петри для моделирования. Моделирование аппаратного обеспечения сетями Петри (конечные автоматы, эвм с конвейерной обработкой, кратные функциональные блоки).
    • Сети Петри для моделирования. Моделирование программного обеспечения сетями Петри (блок-схемы, обеспечение параллелизма).
    • Сети Петри в решении задач синхронизации: задача о взаимном исключении, задача о производителе/потребителе, задача об обедающих мудрецах, задача о чтении/записи, p- и V-системы и др.
    • Задачи анализа сетей Петри: безопасность, ограниченность, сохранение, активность, покрываемость.
    • Дерево достижимости сети Петри.
    • Использование дерева достижимости для анализа сетей Петри.
    • Матричные уравнения и их использование для анализа сетей Петри.
    • Сети Петри с ограничениями и подклассы сетей Петри.
    • 1) Автоматные сети Петри
    • 2) Маркированные графы
    • 3) Сети свободного выбора
    • 4) Правильные сети Петри
    • Расширенные модели сетей Петри (области ограничения, переходы исключающее или, сети со сдерживающими дугами, сети с приоритетами, временные сети)
    • Взаимосвязь мощности моделирования и мощности разрешения сетей Петри