46.Конечные автоматы, сети Петри.

Понятие конечного автомата является удобной математической схемой для описания функционирования тех объектов и систем, для которых характерно наличие дискретных состояний и дискретный характер работы во времени. Однако для моделирования ряда объектов, например средств вычислительной техники (СВТ) и вычислительных сетей, использование абстрактно-автоматной математической схемы встречает трудности, несмотря на то, что данные объекты могут быть представлены как дискретные переходные системы. это объясняется тем, что конечный автомат является последовательной алгоритмической схемой, a СВТ могут выполнять свои функции параллельно и асинхронно, независимо друг от друга, за исключением некоторых заданных точек, называемых точками взаимодействия параллельных процессов. Описание функционирования c использованием конечного автомата и таких случаях теоретически возможно, однако требует рассмотрения большего числа состоянии и увеличения сложности модели. Сеть Петри — это ориентированный граф, содержащий позиции, определяющие условия, имеющиеся в системе, и переходы, отображающие связанные с этими условиями действия. В позициях проставляются метки, если соответствующее условие выполнено. Передвижение меток по сети определяет последовательность изменения состояний моделируемого объекта. Позиции изображаются кружками, переходы — планками. Позиции соединяют дугой с переходом, если выполнение заданного условия является необходимым для запуска связанного с данным переходом действия. Переход соединяют дугой с позицией, если связанное с ним действие порождает условии, представленного данной позицией. Динамика функционирования сетей Петри определяется правилами срабатывания переходов. Изменение состояния сети связано с механизмом изменения маркировок позиций. В случае простой сети Петри: ■ выполняется только активный переход, т. e. такой, во всех входных позициях которого имеются нулевые метки; ■ срабатывание перехода может наступить через любой конечный промежуток времени после его активизации; ■ если в некотором состоянии сети активными оказываются несколько переходов, то всегда выполнятся только какой-то один из них; ■ в результате срабатывания перехода число меток в каждой входной позиции уменьшаются на единицу, а число меток во всех выходных позициях увеличиваются на единицу. Для моделирования СВТ используются следующие типы сетей Петри: • Временные сети Петри - в описание сети дополнительно вводятся задержки при перемещении меток, отнесенные либо к переходам, либо к позициям. • Стохастические сети Петри - для разрешения конфликтных ситуаций в описание дополнительно вводятся случайные задержки или вероятности срабатывания активных переходов. • Приоритетные сети Петри - конфликтные ситуации разрешаются введением различных приоритетов для сетей. • Ингибиторные сети Петри — содержат запрещающие ветви. Свойства сетей Петри: 1. Ограниченность — число меток в любой позиции не может быть больше некоторого числа k —числа конечных состояний. 2. Достижимость — возможность достижении заданных маркировок. 3. Сохраняемость — невозможность возникновения или уничтожения ресурсов в сети Петри.