моделирование СМО   ОКМ   ДМ   экономическая информатика   4GL   Теория и практика обработки информации

Простые сети Петри

Сеть Петри из трех элементов: множество мест , множество переходов и отношение инцидентности.

Простая сеть Петри - это такой набор N = (S,T,F), где
  1. - множество мест;
  2. - множество переходов таких, что .
  3. - отношение инцидентности такое, что
    (а) ;
    (б)

Условия в пункте 3 говорят, что для каждого перехода существует единственный элемент , задающий для него входное мультимножество мест и выходное мультимножество . Дадим определение входному и выходному мультимножеству.

Входное и выходное мультимножества мест и переходов - находится из следующих условий:
Пусть задана сеть .
  1. Если для некоторого перехода имеем , то будем обозначать ;
  2. .

Будем говорить, что - входные, а - выходные места перехода . Таким образом, согласно определению, справедливо . Далее будем говорить, что место инцидентно переходу если или .

Расширим функции и на мультимножества переходов. Пусть есть мультимножество переходов такое, что . Тогда положим

.

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

Пример. Пример сети

  • В качестве простого примера расссмотрим сеть , где

    1. ;

    2. ;

    3.

  • В графической форме сеть представлена на Рис.1. Сеть имеет четыре места и три перехода. Отношение задает дуги сети. Так, например, элемент задает четыре дуги: из в и из в с кратностями 2, из в и из в с единичными кратностями. Для перехода справедливо и . Для места можно вычислить и .

    Рис. 1: Пример графа сети Петри

    Само по себе понятие сети имеет статическую природу. Для задания динамических характеристик используется понятие маркировки сети , т.е. функции , сопоставляющей каждому месту целое число. Графически маркировка изображается в виде точек, называемых метками (tokens), и располагающихся в кружках, соответствующих местам сети. Отсутствие меток в некотором месте говорит о нулевой маркировке этого места.

    Маркированная сеть Петри - это набор , где
    1. - сеть;
    2. - начальная маркировка.

    Пример. Пример маркированной сети.

  • На Рис.2 приведен пример маркированной сети. В начальной маркировке место имеет две метки (токена), место - одну метку, а места , - ни одной метки, т.е. .
  • Рис. 2: Пример маркированной сети Петри

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

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

    Правило срабатывания переходов - это следующий алгоритм
    Пусть маркированная сеть.
    1. Переход считается возбужденным (активированным) при маркировке , если ;
    2. Переход , возбужденный (активированный) при маркировке , может сработать, приведя к новой маркировке , которая вычисляется по правилу: . Срабатывание перехода обозначается как .

    Иными словами, переход считается возбужденным (активированным) при некоторой маркировке, если в каждом его входном месте имеется количество меток не менее кратности соответствующих дуг. Возбужденный (активированный) переход может сработать, причем при срабатывании из каждого его входного места изымается, а в каждое входное добавляется некоторое количество меток, равное кратности соответствующих дуг. Если одновременно возбуждено (активировано) несколько переходов, сработать может любой из них или любая их комбинация. Например, пусть в сети на рисунке 2 сработают переходы и . Получим сеть представленную на рисунке 3.

    Рис. 3: Новая сеть с маркировкой .

    Композициональный подход к построению сетей Петри предполагает возможность построения более сложных сетей из менее сложных составляющих. Для этого вводятся точки доступа, которые позволяют объединять простые сети путём синхронизации событий и состояний (переходов и мест).

    T-точка доступа - это точка, определяемая следующими условиями
    Пусть задана сеть и некоторый алфавит . Т-точкой доступа называется набор , где

    1. - имя (идентификатор) t-точки доступа;
    2. - некоторый алфавит;
    3. - пометочная функция, где . Запись обозначает множество всех конечных и непустых мультимножеств, определённых на множестве .
    S-точка доступа - это точка, определяемая следующими условиями
    Пусть задана сеть . Тогда s-точкой доступа сети N называется набор , где

    1. - имя (идентификатор) s-точки доступа;
    2. - множество такое, что .

    Введённые понятия точек доступа предоставляют возможность ввести две основные операции над сетями Петри для построения композициональных сетей:

    1. Операция слияния переходов - позволяет порождать и описывать синхронизацию параллельных процессов (tmerge);

    2. Операция слияния мест - позволяет применять к сетям операции последовательной композиции, выбора, итерации и другие (smerge).

    Рис. 4: Пример операции слияния переходов

    Рис. 5: Пример операции слияния мест

    Приведённые операции имеют следующий смысл:

    При слиянии мест - определяется набор состояний в сети, которые идентифицируются, как состояние сети, определённое именем s-точки доступа. Слияние различных сетей производится так, что если в одной сети достигнуто описанное состояние, то в другой сети это состояние также получается достигнутым;

    При слиянии переходов – определяется алфавит событий, видимых из t-точки доступа. Каждый переход в сети помечается либо невидимым событием, либо комбинацией событий из алфавита точки доступа. Слияние по переходам производится так, что если при срабатывании одной сети возникает некоторая комбинация событий, то эта же комбинация событий происходит во второй сети.

    моделирование СМО   ОКМ   ДМ   экономическая информатика   4GL   Теория и практика обработки информации

    (время поиска примерно 20 секунд)


    Знаете ли Вы, в чем фокус эксперимента Майкельсона?

    Эксперимент А. Майкельсона, Майкельсона - Морли - действительно является цирковым фокусом, загипнотизировавшим физиков на 120 лет.

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

    В эксперименте Майкельсона ставится вопрос о движении эфира относительно покоящегося в лабораторной системе интерферометра. Однако, если мы ищем эфир, как базовую материю, из которой состоит всё вещество интерферометра, лаборатории, да и Земли в целом, то, естественно, эфир тоже будет неподвижен, так как земное вещество есть всего навсего определенным образом структурированный эфир, и никак не может двигаться относительно самого себя.

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

    НОВОСТИ ФОРУМА

    Форум Рыцари теории эфира


    Рыцари теории эфира
     29.11.2020 - 11:44: СОВЕСТЬ - Conscience -> РАСЧЕЛОВЕЧИВАНИЕ ЧЕЛОВЕКА. КОМУ ЭТО НАДО? - Карим_Хайдаров.
    29.11.2020 - 11:36: ЭКОЛОГИЯ - Ecology -> Биологическая безопасность населения - Карим_Хайдаров.
    29.11.2020 - 11:36: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> Проблема государственного терроризма - Карим_Хайдаров.
    29.11.2020 - 11:33: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Галины Царёвой - Карим_Хайдаров.
    29.11.2020 - 09:10: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Пламена Паскова - Карим_Хайдаров.
    29.11.2020 - 09:04: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> ПРАВОСУДИЯ.НЕТ - Карим_Хайдаров.
    29.11.2020 - 09:01: ЭКОЛОГИЯ - Ecology -> ПРОБЛЕМЫ МЕДИЦИНЫ - Карим_Хайдаров.
    29.11.2020 - 08:58: ЭКОЛОГИЯ - Ecology -> ЭКОЛОГИЯ ДЛЯ ВСЕХ - Карим_Хайдаров.
    28.11.2020 - 15:48: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Юрия Воробьевского - Карим_Хайдаров.
    28.11.2020 - 11:37: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> ЗА НАМИ БЛЮДЯТ - Карим_Хайдаров.
    28.11.2020 - 11:36: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Аманды Вольмер - Карим_Хайдаров.
    28.11.2020 - 09:04: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Александра Флоридского - Карим_Хайдаров.

    Боровское исследовательское учреждение - Bourabai Research Bourabai Research Institution