Сети Петри

В абстрактном автомате рассматриваются последовательные переходы состояния. Поэтому такая модель неприменима для объектов, способных выполнять свои функции параллельно. Для моделирования таких объектов используют сети Петри. Сети Петри – это инструмент описания и исследования мультипрограммных, асинхронных, распределенных, параллельных, недетерминированных и/или стохастических систем обработки информации.

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

Моделирование в сетях Петри осуществляется на событийном уровне. Определяются, какие действия происходят в системе, какие состояние предшествовали этим действиям и какие состояния примет система после выполнения действия. Выполнения событийной модели в сетях Петри описывает поведение системы. Анализ результатов выполнения может сказать о том, в каких состояниях пребывала или не пребывала система, какие состояния в принципе не достижимы. Однако такой анализ не дает числовых характеристик, определяющих состояние системы.

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

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

Сети Петри могут применяться:

1) Для моделирования бизнес-процессов. Функциональные диаграммы в нотации IDEF3 могут быть преобразованы в сеть Петри. Каждой работе на диаграмме соответствует переход сети Петри. Позиции соответствуют стрелкам, соединяющим работы напрямую и перекресткам. Метки соответствуют продукции, документов и т.д. Причем в зависимости от перехода интерпретация метки может отличаться.

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

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

Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

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

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

Виды сетей Петри

Некоторые виды сетей Петри:

• Временная сеть Петри — переходы обладают весом, определяющим продолжительность срабатывания (задержку).
• Стохастическая сеть Петри — задержки являются случайными величинами.
• Функциональная сеть Петри — задержки определяются как функции некоторых аргументов, например, количества меток в каких-либо позициях, состояния некоторых переходов.
• Цветная сеть Петри — метки могут быть различных типов, обозначаемых цветами, тип метки может быть использован как аргумент в функциональных сетях.
• Ингибиторная сети Петри — возможны ингибиторные дуги, запрещающие срабатывания перехода, если во входной позиции, связанной с переходом ингибиторной дугой находится метка.

Анализ сетей Петри

Основными свойствами сети Петри являются:

• Ограниченность — число меток в любой позиции сети не может превысить некоторого значения K.
• Безопасность — частный случай ограниченности, K=1.
• Сохраняемость — постоянство загрузки ресурсов, постоянна. Где N_i — число маркеров в i-той позиции, A_i — весовой коэффициент.
• Достижимость — возможность перехода сети из одного заданного состояния (характеризуемого распределением меток) в другое.
• Живость — возможностью срабатывания любого перехода при функционировании моделируемого объекта.

В основе исследования перечисленных свойств лежит анализ достижимости.

Моделирование в сетях Петри осуществляется на событийном уровне. Определяются, какие действия происходят в системе, какие состояние предшествовали этим действиям и какие состояния примет система после выполнения действия. Выполнения событийной модели в сетях Петри описывает поведение системы. Анализ результатов выполнения может сказать о том, в каких состояниях пребывала или не пребывала система, какие состояния в принципе не достижимы. Однако, такой анализ не дает числовых характеристик, определяющих состояние системы. Развитие теории сетей Петри привело к появлению, так называемых, “цветных” сетей Петри. Понятие цветности в них тесно связано с понятиями переменных, типов данных, условий и других конструкций, более приближенных к языкам программирования. Несмотря на некоторые сходства между цветными сетями Петри и программами, они еще не применялись в качестве языка программирования.

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

2. Нормализация таблиц при проектировании баз данных. Нормальные формы (1НФ, 2НФ, 3НФ, НФБК).

Реляционная база данных содержит как структурную, так и семантическую информацию. Структура базы данных определяется числом и видом включенных в нее отношений, и связями типа "один ко многим", существующими между кортежами этих отношений. Семантическая часть описывает множество функциональных зависимостей, существующих между атрибутами этих отношений. Дадим определение функциональной зависимости - Если даны два атрибута X и Y некоторого отношения, то говорят, что Y функционально зависит от X, если в любой момент времени каждому значению X соответствует ровно одно значение Y.

Функциональная зависимость обозначается X -> Y. Отметим, что X и Y могут представлять собой не только единичные атрибуты, но и группы, составленные из нескольких атрибутов одного отношения.

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

Некоторые функциональные зависимости могут быть нежелательны.

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

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

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

• не должны появляться ранее отсутствовавшие кортежи;

• на отношениях новой схемы должно выполняться исходное множество функциональных зависимостей.

1NF - первая нормальная форма.

Для обсуждения первой нормальной формы необходимо дать два определения:

Простой атрибут - атрибут, значения которого атомарны (неделимы).

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

Теперь можно дать

Определение первой нормальной формы: отношение находится в 1NF если значения всех его атрибутов атомарны.

В базе данных отдела кадров предприятия необходимо хранить сведения о служащих, которые можно попытаться представить в отношении

СЛУЖАЩИЙ(НОМЕР_СЛУЖАЩЕГО, ИМЯ, ДАТА_РОЖДЕНИЯ, ИСТОРИЯ_РАБОТЫ, ДЕТИ).

Из внимательного рассмотрения этого отношения следует, что атрибуты "история_работы" и "дети" являются сложными, более того, атрибут "история_работы" включает еще один сложный атрибут "история_зарплаты".

Данные агрегаты выглядят следующим образом:

• ИСТОРИЯ_РАБОТЫ (ДАТА_ПРИЕМА, НАЗВАНИЕ, ИСТОРИЯ_ЗАРПЛАТЫ),

• ИСТОРИЯ_ЗАРПЛАТЫ (ДАТА_НАЗНАЧЕНИЯ, ЗАРПЛАТА),

• ДЕТИ (ИМЯ_РЕБЕНКА, ГОД_РОЖДЕНИЯ).

Их связь представлена на рис. 1.

Рис.1. Исходное отношение.

Для приведения исходного отношения СЛУЖАЩИЙ к первой нормальной форме необходимо декомпозировать его на четыре отношения, так как это показано на следующем рисунке:

Рис.2. Нормализованное множество отношений.

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

Алгоритм нормализации описан Е.Ф.Коддом следующим образом:

• Начиная с отношения, находящегося на верху дерева (рис. 1.), берется его первичный ключ, и каждое непосредственно подчиненное отношение расширяется путем вставки домена или комбинации доменов этого первичного ключа.

• Первичный Ключ каждого расширенного таким образом отношения состоит из Первичного Ключа, который был у этого отношения до расширения и добавленного Первичного Ключа родительского отношения.

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

2NF - вторая нормальная форма.

Очень часто первичный ключ отношения включает несколько атрибутов (в таком случае его называют составным) - см., например, отношение ДЕТИ, показанное на рис. 2. При этом вводится понятие полной функциональной зависимости.

Определение: неключевой атрибут функционально полно зависит от составного ключа если он функционально зависит от всего ключа в целом, но не находится в функциональной зависимости от какого-либо из входящих в него атрибутов.

Пример:

Пусть имеется отношение ПОСТАВКИ (N_ПОСТАВЩИКА, ТОВАР, ЦЕНА).

Поставщик может поставлять различные товары, а один и тот же товар может поставляться разными поставщиками. Тогда ключ отношения - "N_поставщика + товар". Пусть все поставщики поставляют товар по одной и той же цене. Тогда имеем следующие функциональные зависимости:

• N_поставщика, товар -> цена

• товар -> цена

Неполная функциональная зависимость атрибута "цена" от ключа приводит к следующей аномалии: при изменении цены товара необходим полный просмотр отношения для того, чтобы изменить все записи о его поставщиках. Данная аномалия является следствием того факта, что в одной структуре данных объединены два семантических факта. Следующее разложение дает отношения во 2НФ:

• ПОСТАВКИ (N_ПОСТАВЩИКА, ТОВАР)

• ЦЕНА_ТОВАРА (ТОВАР, ЦЕНА)

Определение второй нормальной формы:

Отношение находится во 2НФ, если оно находится в 1НФ и каждый неключевой атрибут функционально полно зависит от ключа.

3NF - третья нормальная форма.

Перед обсуждением третьей нормальной формы необходимо ввести понятие транзитивной функциональной зависимости.

Пусть X, Y, Z - три атрибута некоторого отношения. При этом X --> Y и Y --> Z, но обратное соответствие отсутствует, т.е. Z -/-> Y и Y -/-> X. Тогда Z транзитивно зависит от X.

Пусть имеется отношение ХРАНЕНИЕ (ФИРМА, СКЛАД, ОБЪЕМ), которое содержит информацию о фирмах, получающих товары со складов, и объемах этих складов. Ключевой атрибут - "фирма". Если каждая фирма может получать товар только с одного склада, то в данном отношении имеются следующие функциональные зависимости:

• фирма -> склад

• склад -> объем

При этом возникают аномалии:

• если в данный момент ни одна фирма не получает товар со склада, то в базу данных нельзя ввести данные о его объеме (т.к. не определен ключевой атрибут)

• если объем склада изменяется, необходим просмотр всего отношения и изменение кортежей для всех фирм, связанных с данным складом.

Для устранения этих аномалий необходимо декомпозировать исходное отношение на два:

• ХРАНЕНИЕ (ФИРМА, СКЛАД)

• ОБЪЕМ_СКЛАДА (СКЛАД, ОБЪЕМ)

Определение третьей нормальной формы:

Отношение находится в 3НФ, если оно находится во 2НФ и каждый неключевой атрибут нетранзитивно зависит от первичного ключа.

BCNF - нормальная форма Бойса-Кодда.

Эта нормальная форма вводит дополнительное ограничение по сравнению с 3НФ. Определение нормальной формы Бойса-Кодда:

Отношение находится в BCNF, если оно находится во 3НФ и в ней отсутствуют зависимости атрибутов первичного ключа от неключевых атрибутов.

Ситуация, когда отношение будет находится в 3NF, но не в BCNF, возникает при условии, что отношение имеет два (или более) возможных ключа, которые являются составными и имеют общий атрибут. Заметим, что на практике такая ситуация встречается достаточно редко, для всех прочих отношений 3NF и BCNF эквивалентны.

3. Составить программу, которая формирует очередь, добавляя в неё произвольное количество компонент.