Сеть петри онлайн построение
Сети Петри. Структура и правила выполнения сетей Петри.
Сети Петри Править
Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.
Пример работы сети Петри
Сеть Петри представляет собой двудольный ориентированный граф, состоящий из вершин двух типов — позиций и переходов, соединённых между собой дугами. Вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры), способные перемещаться по сети.
Событием называют срабатывание перехода, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. События происходят мгновенно, либо разновременно, при выполнении некоторых условий.
Как и стандартные UML диаграммы, BPMN и EPC, сети Петри предоставляют возможность графически иллюстрировать процессы включающие выбор, итерации и одновременное выполнение. Но в отличие от данных стандартов, у сетей Петри четкая математическая формулировка и за ними стоит развитая математическая теория.
$ Введите сюда формулу $ ==Структура сетей Петри==
Сеть Петри состоит из 4-х элементов:
- множество позиций P,
- множество переходов T,
- входная функция I,
- выходная функция O.
Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.
Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход tj в множество позиций I(tj) , называемых входными позициями перехода . Выходная функция O отображает переход pi в множество позиций O(pi) , называемых выходными позициями перехода . Структура сети Петри определяется её позициями, переходами, входной и выходной функциями.
Сеть Петри С является четверкой, C=(P,T,I,O). P=
Произвольный элемент P обозначается символом pi , i=1, . n, а произвольный элемент T — символом tj, j=1, . m.
Правила выполнения сетей Петри Править
Выполнением сети Петри управляют количество и распределение фишек в сети. Сеть Петри выполняется посредством запусков переходов. Переход запускается удалением фишек из его входных позиций и образованием новых фишек, помещаемых в его выходные позиции.
Переход запускается, если он разрешен. Переход называется разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу дуг из позиции в переход. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками. Например, если позиции р1 и р2 служат входами для перехода t1, тогда t1 разрешен, если р1 и р2 имеют хотя бы по одной фишке. Для перехода t3 с входным комплектом
Определение. Переход $ t_j in T $ маркированной сети Петри $ C = (P, T, I, O, mu) $ с маркировкой $ mu $ , разрешен, если для всех $ p_j in P $ , $ mu (p_i) geq # (p_i, I(t_j)) $ .
Переход запускается удалением разрешающих фишек, из всех его входных позиций (количество удаленных фишек для каждой позиции соответствует числу дуг, идущих из этой позиции в переход), с последующим помещением фишек в каждую из его выходных позиций (количество помещаемых фишек в позицию соответствует количеству дуг входящих в данную позицию из перехода).
>Переход t3 I(t3) =
Определение. Переход $ t_j $ в маркированной сети Петри с маркировкой $ mu $ может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода $ t_j $ образуется новая маркировка $ mu^ <'>$ :
$ mu^ <'>(p_i) = mu (p_j) — # (p_i, I(t_j) + # (p_i, O(t_j)) $
Сети Петри — математический аппарат для моделирования
Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.
Сети Петри разрабатывались для моделирования систем с параллельными взаимодействующими компонентами. Сети Петри впервые предложил Карл Адам Петри. В докторской диссертации «Связь с автоматами» он сформулировал основные понятия теории связи асинхронных компонент вычислительной системы.
Сети Петри — инструмент моделирования
В настоящее время сети Петри применяются, в основном, в моделировании. Во многих областях исследований явление изучается не непосредственно, а косвенно, через модель. Модель — это представление, как правило, в математических терминах того, что считается наиболее характерным в изучаемом объекте или системе. Манипулируя моделью системы, можно получить новые знания о ней, избегая опасности, дороговизну или неудобства анализа самой реальной системы. Обычно модели имеют математическую основу.
Развитие теории сетей Петри проводилось по двум направлениям. Формальная теория сетей Петри занимается разработкой основных средств, методов и понятий, необходимых для применения сетей Петри. Прикладная теория сетей Петри связана главным образом с применением сетей Петри к моделированию систем, их анализу и получающимся в результате этого глубоким проникновением в моделируемые системы.
Моделирование в сетях Петри осуществляется на событийном уровне. Определяются, какие действия происходят в системе, какие состояние предшествовали этим действиям и какие состояния примет система после выполнения действия. Выполнения событийной модели в сетях Петри описывает поведение системы. Анализ результатов выполнения может сказать о том, в каких состояниях пребывала или не пребывала система, какие состояния в принципе не достижимы. Однако, такой анализ не дает числовых характеристик, определяющих состояние системы. Развитие теории сетей Петри привело к появлению, так называемых, «цветных» сетей Петри. Понятие цветности в них тесно связано с понятиями переменных, типов данных, условий и других конструкций, более приближенных к языкам программирования. Несмотря на некоторые сходства между цветными сетями Петри и программами, они еще не применялись в качестве языка программирования.
Не смотря на описанные выше достоинства сетей Петри, неудобства применения сетей Петри в качестве языка программирования заключены в процессе их выполнения в вычислительной системе. В сетях Петри нет строго понятия процесса, который можно было бы выполнять на указанном процессоре. Нет также однозначной последовательности исполнения сети Петри, так как исходная теория представляет нам язык для описания параллельных процессов.
Наилучшими возможностями описания параллельных систем обладают сети Петри. Они не менее мощные, чем MPI, PVM, SDL, UML и другие, но чтобы их выполнять на процессорах необходимо сделать из описания параллельного распределенное.
Динамика сети Петри
Процесс функционирования сети Петри может быть наглядно представлен графом достижимых маркировок . Состояние сети однозначно определяется её маркировкой — распределением фишек по позициям. Вершинами графа являются допустимые маркировки сети Петри, дуги помечены символом срабатывающего перехода. Дуга строится для каждого активированного перехода. Построение прекращается, когда мы получаем маркировки, в которых не активирован ни один переход либо маркировки, содержащиеся в графе.
Пример траектории в сети Петри
Виды сетей Петри
Некоторые виды сетей Петри:
WF-сети используются для проверки графов потоков работ на наличие таких структурных конфликтов, как «тупики» (англ. deadlocks) и «недостатки синхронизации» (англ. lack of synchronization). Структурные конфликты отсутствуют, если WF-сеть является бездефектной.
Свойство бездефектности соответствует двум хорошо известным свойствам сетей Петри — живости и ограниченности.
Анализ сетей Петри
Основными свойствами сети Петри являются:
В основе исследования перечисленных свойств лежит анализ достижимости. Методы анализа свойств сетей Петри основаны на использовании графов достижимых (покрывающих) маркировок, решении уравнения состояний сети и вычислении линейных инвариантов позиций и переходов. Применяются также вспомогательные методы редукции, позволяющие уменьшить размер сети Петри с сохранением ее свойств, и декомпозиции, разделяющие исходную сеть на подсети.
Универсальная сеть Петри
В 1974 году Тилак Аджервала показал, что ингибиторная сеть Петри является универсальной алгоритмической системой. В монографии В. Е. Котова приведен набросок доказательства, указывающий правила кодирования ингибиторной сетью программы счетного автомата Минского. Дж. Питерсон приводит примеры других расширенных классов сетей Петри, являющихся универсальной алгоритмической системой: синхронных и приоритетных. Построенная в явном виде универсальная сеть Петри насчитывала несколько тысяч вершин и недавно была уменьшена до 56 вершин.
Бесконечные сети Петри
Бесконечные сети Петри были введены для верификации вычислительных решеток и позволяют определять свойства сетей Петри для регулярных структур (линейная, древовидная, квадратная, треугольная, шестиугольная и гиперкуб) произвольного размера, полученных путем композиции типовых фрагментов.
Теория сетей Петри является хорошо известным и популярным формализмом, предназначенным для работы с параллельными и асинхронными системами. Основанная в начале 60-х годов немецким математиком К. А. Петри, в настоящее время она содержит большое количество моделей, методов и средств анализа, имеющих обширное количество приложений практически во всех отраслях вычислительной техники и даже вне ее.
Сети Петри
Сети Петри
Ребята, у меня возникла такая проблема, мне нужно сделать сеть петри. Задача звучит так: в.
Ординарная Сеть Петри для задачи об «обедающих философах»
Помогите с сетью Петри. дуб в этом Задача об обедающих философах. Пять философов отдыхают в.
Сети Петри . Любой простой пример программы с сетями Петри С++ или на других языках программирования
Помогите пожалуйста . Сети Петри . Любой простой пример программы с сетями Петри С++ или на других.
Сети Петри и С++
нужно с помощью сетей Петри описать протокол передачи данных и с помощью С++ написать программу.
А задача-то какая стоит ?
Что должна делать реализация ?
Гонять сеть по заданым начальным условиям или что ?
А то вопрос похож на следующий: «Помогите. Нужны исходники реализации квадратной матрицы. Для меня квадратная матрица — темный лес.»
хм) думаю ссылки на википедию не стоит выкладывать но все же спаибо, я хотел бы узнать ил увидеть материал где описываеться применение сетей петри для лингвоанализа, что то типа разложение слова на составляющие, его происхождение синонимы и прочее. вот так
Добавлено через 22 часа 20 минут
ну так чо кто нить чо нить предложит, чесно гвоояр хотелось бы увидеть готовую програмную реализацию, но это видимо только мечты, кто не хочет давать даром может я чо нить напишу для него взамен,хы..)
Всем доброе время суток.
Уважаемый автор вопроса. Если вы нашли код, то скиньте пожалуйста.
Уважаемые форумчанины, напиши пожалуйста любую реализацию динамических систем методом сетей петри. Можно и цветные.
odip,
Здравствуйте, мне как раз таки нужно реализовать дерево вывода прогона всех разметок сети петри. у меня разметки выводит, все в порядке, но я никак не могу додуматься до правильно нумерации этих разметок, дело в том, что у меня там рекурсия, и вот с ней голову ломаю, она работает так:
Находит новую разметку путем проверки текущей разметки с элементами каждого столбца матрицы Fp (матрица позиций), затем если есть столбец у которого все элементы меньше либо равны элементов текущей разметки, она отнимает от элементов разметки, элементы столбца этого, и прибавляет элементы соответствуйющей строки матрицы Ft (матрица переходов). Ну это все теория, метки при этом у меня находит она верно, но нумерация не та. на картинках ниже прилагаю, как есть (1-я) и как должна быть (2-я). И ещё код сам конечно. Спасибо..Главная функция конечно же CreateTree в ней все и вертится
| 10.04.2013, 16:33 |
| 10.04.2013, 16:33 |
Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь. Сети Петри СЕТИ Петри Сети Петри Сети Петри Моделирование сети Петри на С++. Параллельная реализация с MPIrrrFerПостановка задачи: Сети Петри: В сетях Петри происходит выполнение одного из возможных дискретных событий. Если в какой-то момент времени разрешено более одного перехода, то любой из них может стать «следующим» запускаемым. Пример работы сети Петри:
Описание работы программы: В автоматическом режиме программа случайным образом выбирает переход, если он доступен, переход выполняется, программа ищет разрешенные переходы. Это повторяется, пока не будет выполнено указанное число переходов. В ручном режиме алгоритм тот же, но выбор переходов предоставлен пользователю. Для моделирования позиций используется массив Sost, он содержит в себе данные о текущем положении меток в позициях. Условия переходов реализованы при помощи двумерных массивов mx1 и mx2. Массив mx1 содержит в себе условия, необходимые для выполнения перехода, mx2 содержит последствия выполнения перехода. Для вычисления разрешенных переходов используется функция FindActiveTransistions, в которой реализован параллельный поиск. Состояния переходов хранятся в массиве ch. Последствия перехода рассчитываются по массиву mx2 – используется строка, соответствующая выбранному переходу, по которой выполняется пересчёт состояний положений. При выполнении программы в автоматическом режиме происходит подсчёт времени работы каждого процесса, для сравнения их скорости работы. Так же ведётся подсчёт времени выполнения всей программы – оно выводится в главном процессе(ROOT). Причины распараллеливания: При большом количестве переходов их последовательный поиск будет занимать много времени. Для ускорения работы программы массив разбивается на части по количеству переходов (по столбцам). В итоге, при параллельном выполнении каждый процесс будет перебирать сегмент массива, равный (P*S)/N, а при последовательном P*S, где P – число переходов, S – число состояний, N – число процессов. Описание работы параллельных частей: Получив границы, каждый процесс выполняет поиск разрешенных переходов в рамках своего сегмента, результаты поиска записываются в буфер buf. Завершив поиск в своём сегменте, каждый процесс отправляет свои результаты всем другим процессам. Для этого используется функция MPI_Alltoall, она заменяет две функции, требующиеся для сбора фрагментов с результатами поиска каждого процесса в одном процессе (MPI_Gather) и рассылке полных данных каждому процессу (MPI_Scatter). Полные данные нужны для дальнейших расчётов состояния. диаграммы загрузки процессора для последовательной програмым и с распараллеливанием с openMP:   Загрузка...Похожие публикации detector |
