Реализация алгоритма преобразования неординарной сети Петри в ординарную

Описана програмна реалізація алгоритму перетворення неординарної мережі Петрі в ординарну. В основу програми покладено алгоритм, що був запропонований Хаком. Аалгоритм релізовано в програмному забезпеченні “Перетворювач мереж Петрі”, створеному на мові програмування C++Builder....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2004
Автори:	Усатюк, О.В., Крывый, С.Л.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут програмних систем НАН України 2004
Теми:	Формальные методы в программировании
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/1679
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Реализация алгоритма преобразования неординарной сети Петри в ординарную /О.В. Усатюк, С.Л.Крывый// Проблеми програмування. — 2004. — N 2,3. — С. 81-88. — Бібліогр.: 5 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-1679
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-16792025-02-09T09:52:29Z Реализация алгоритма преобразования неординарной сети Петри в ординарную Усатюк, О.В. Крывый, С.Л. Формальные методы в программировании Описана програмна реалізація алгоритму перетворення неординарної мережі Петрі в ординарну. В основу програми покладено алгоритм, що був запропонований Хаком. Аалгоритм релізовано в програмному забезпеченні “Перетворювач мереж Петрі”, створеному на мові програмування C++Builder. Реализация алгоритма преобразования неординарной сети Петри в ординарную. Описана программная реализация алгоритма преобразования неординарной сети Петри в ординарную. В основу программы положен алгоритм преобразования, предложенный Хаком. Алгоритм реализован в программном обеспечении «Преобразователь сетей Петри», созданному на языке программирования C++Builder. O.V. Usatyuk, S.L. Krivoi Realisation of transformation algorithm of non-ordinary Petri Net into ordinary. An realization of transformation non-ordinary Petri net into ordinary. A basis of the program is the algorithm, offered by Hak. The given algorithm realized in the software «The Converter of networks of Petri», created on the programming language C ++ Builder. 2004 Article Реализация алгоритма преобразования неординарной сети Петри в ординарную /О.В. Усатюк, С.Л.Крывый// Проблеми програмування. — 2004. — N 2,3. — С. 81-88. — Бібліогр.: 5 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/1679 51.681.3 ru application/pdf Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Формальные методы в программировании Формальные методы в программировании
spellingShingle	Формальные методы в программировании Формальные методы в программировании Усатюк, О.В. Крывый, С.Л. Реализация алгоритма преобразования неординарной сети Петри в ординарную
description	Описана програмна реалізація алгоритму перетворення неординарної мережі Петрі в ординарну. В основу програми покладено алгоритм, що був запропонований Хаком. Аалгоритм релізовано в програмному забезпеченні “Перетворювач мереж Петрі”, створеному на мові програмування C++Builder.
format	Article
author	Усатюк, О.В. Крывый, С.Л.
author_facet	Усатюк, О.В. Крывый, С.Л.
author_sort	Усатюк, О.В.
title	Реализация алгоритма преобразования неординарной сети Петри в ординарную
title_short	Реализация алгоритма преобразования неординарной сети Петри в ординарную
title_full	Реализация алгоритма преобразования неординарной сети Петри в ординарную
title_fullStr	Реализация алгоритма преобразования неординарной сети Петри в ординарную
title_full_unstemmed	Реализация алгоритма преобразования неординарной сети Петри в ординарную
title_sort	реализация алгоритма преобразования неординарной сети петри в ординарную
publisher	Інститут програмних систем НАН України
publishDate	2004
topic_facet	Формальные методы в программировании
url	https://nasplib.isofts.kiev.ua/handle/123456789/1679
citation_txt	Реализация алгоритма преобразования неординарной сети Петри в ординарную /О.В. Усатюк, С.Л.Крывый// Проблеми програмування. — 2004. — N 2,3. — С. 81-88. — Бібліогр.: 5 назв. — рос.
work_keys_str_mv	AT usatûkov realizaciâalgoritmapreobrazovaniâneordinarnojsetipetrivordinarnuû AT kryvyjsl realizaciâalgoritmapreobrazovaniâneordinarnojsetipetrivordinarnuû
first_indexed	2025-11-25T13:05:56Z
last_indexed	2025-11-25T13:05:56Z
_version_	1849767715069231104
fulltext	УДК 51.681.3 РЕАЛИЗАЦИЯ АЛГОРИТМА ПРЕОБРАЗОВАНИЯ НЕОРДИНАРНОЙ СЕТИ ПЕТРИ В ОРДИНАРНУЮ О.В. Усатюк, С.Л. Крывый Институт кибернетики им. Глушкова НАН Украины, email: oleg_usa@parus.com.ua О.В. Усатюк, С.Л. Кривий Реалізація алгоритму перетворення неординарної мережі Петрі в ординарну. Описана програмна реалізація алгоритму перетворення неординарної мережі Петрі в ординарну. В основу програми покладено алгоритм, що був запропонований Хаком. Аалгоритм релізовано в програмному забезпеченні “Перетворювач мереж Петрі”, створеному на мові програмування C++Builder. О.В. Усатюк, С.Л. Кривой Реализация алгоритма преобразования неординарной сети Петри в ординарную. Описана программная реализация алгоритма преобразования неординарной сети Петри в ординарную. В основу программы положен алгоритм преобразования, предложенный Хаком. Алгоритм реализован в программном обеспечении «Преобразователь сетей Петри», созданному на языке программирования C++Builder. O.V. Usatyuk, S.L. Krivoi Realisation of transformation algorithm of non-ordinary Petri Net into ordinary. An realization of transformation non-ordinary Petri net into ordinary. A basis of the program is the algorithm, offered by Hak. The given algorithm realized in the software «The Converter of networks of Petri», created on the programming language C ++ Builder. Введение Построение модели дискретной системы – это важный этап в представлении абстрактных событий, которых может быть большое множество (например: выполнение операторов программы, переходы триггера из одного состояния в другое или прерывания операционной системы). Формализованное представление какой- нибудь дискретной системы является довольно сложным процессом, поскольку реальная система функционирует в реальном времени, т.е. события в рассматриваемой системе происходят в некоторые моменты времени и длятся некоторое время. Поэтому ведение времени в дискретных системах обычно заменяется на причинно - следственные связи между событиями. Модели такого типа называются асинхронными [1], к ним также принадлежат и сети Петри. Одной из главных особенностей сетей Петри является то, что анализ некоторой построенной по описанной схеме системы позволяет выявить ее достоинства или недостатки, узкие места, которые в последствии можно устранить, что в свою очередь позволяет использовать сети Петри для моделирования и анализа в различных отраслях науки и техники. Особый интерес в этой области представляет некоторый подкласс сетей Петри – так называемые ординарные сети, о котором речь пойдет ниже. 1. Основные определения Далее приводятся основные необходимые формальные определения. Определение 1. Сетью будем называть тройку (P, T, F), где P – непустое множество элементов сети, называемых местами, T – непустое множество элементов сети, называемых переходами, PTTPF ×∪×⊆ – отношение инцидентности, и для (P, T, F) выполнены следующие условия: A1) ∅=∩ TP (множества мест и переходов не пересекаются); А2) ):,()( yFxxFyTPyTPxF ∨∪∈∃∪∈∀∧∅≠ (т.е. любой элемент сети инцидентен хотя бы одном элементу другого типа); А3) если для произвольного элемента сети Xx ∈ обозначить через x⋅ , множество его входных элементов }\|{ yFxy , а через ⋅x - множество его выходных элементов }\|{ xFyy , то )()()(:, 21212121 ppppppPpp =⇒⋅=⋅∧⋅=⋅∈∀ , (т.е. сеть не содержит пары мест, которые инцидентны одному и тому же множеству переходов). Графическим представлением сети служит в общем случае двудольный ориентированный граф с двумя типами вершин; вершины места изображаются кружочками, вершины-переходы – барьерами. Из вершины x в вершину y ведет дуга, тогда и только тогда, когда x F y. Определение 2. Сетью Петри будем называть набор N=(P, T, F, W, M0), где (P, T, F) – конечная сеть (множество TPX ∪= конечно), а }0{\: NFW → и NPM →:0 – две функции, называемые соответственно кратностью дуг и начальной разметкой. Первая сопоставляет каждой дуге число n>0 (кратность дуги). Если n>1, то в графическом представлении сети число n выписывается рядом с короткой чертой, пересекающей дугу. Часто такая дуга будет также заменяться пучком из n дуг, соединяющих соответствующие элементы сети. Условимся никак не отмечать кратность дуг, равную 1. Такую сеть будем называть ординарной.[4] Вторая функция сопоставляет каждому месту Pp ∈ некоторое число NpM ∈)(0 (разметка места). В графическом представлении сети разметка места p изображается помещением в вершину-кружок числа )(0 pM или, если это число невелико, соответствующего числа точек (фишек). Функционирование сети Петри описывается формально с помощью множества последовательностей срабатываний и множества достижимых в сети разметок. Эти понятия определяются через правила срабатывания переходов сети. На основе отношения инцидентности F и функции кратности дуг W можно ввести функцию инцидентности NPTTPF →×∪×: , которая определяется как    ¬ =∧ = ).(,0 ),),((, ),( xFyесли nyxWxFyеслиn yxF Если места сети упорядочены, то можно каждому переходу t сопоставить два целочисленных вектора )()( tFиtF ⋅⋅ длиной n, где n = \| P \|: ).,(),,...,()( ),,(),,...,()( 1 1 iin iin ptFbгдеbbtF tpFbгдеbbtF ==⋅ ==⋅ Переход t может сработать при некоторой разметке M сети N, если ),( ptF ′ , т.е. каждое входное место p перехода t имеет разметку, не меньшую, чем кратность дуги, соединяющей p и t. Для ординарной сети Петри условие срабатывания перехода означает, что любое входное место этого перехода имеет ненулевую разметку, т.е. содержит хотя бы одну фишку. Другими словами, если все дуги сети имеют одну и ту же кратность 1, то такая сеть относится к подклассу ординарных сетей. Наличие в сетях Петри дуг с кратностью, большей , чем единица, позволяет естественно моделировать реальные дискретные системы, н во многих случаях теоретического анализа сетей удобней ограничиться рассмотрением ординарных сетей. 2. Алгоритм построения ординарной сети Петри Вопрос о том, насколько результаты исследования ординарных сетей переносимы на общий случай сетей разрешил Хак [2]. Он показал, что подкласс ординарных сетей не является существенным сужением класса сетей Петри, и по отношению к большинству своих сетей оба класса оказываются эквивалентными в том смысле, что для сети Петри с заданным набором свойств можно построить ординарную сеть, обладающую тем же набором свойств [3]. Далее представлено предложенное Хаком преобразование произвольной сети Петри N=(P, T, F, W, M0) в ординарную сеть N’=(P’, T’, F’, M0), и состоит оно в следующем: 1) Для каждого места Pp ∈ определяется максимальная кратность n(p) дуг, инцидентных этому месту по формуле )).,(),((max)( ptFtpFpn Tt += ∈ 2) Каждому месту Pp ∈ будет соответствовать в сети N’ множество P’(p) из n(p) мест p1, p2, ... , pn(p), где n(p) – определенная выше максимальная кратность дуг для места p. Таким образом, общее число мест в P’ равно сумме максимальных кратностей для всех мест из P, т.е. ).( pPP Pp ′=′ ∈ U 3) Каждому переходу Tt ∈ соответствует в T’ единственный переход, обозначаемый тем же символом t, но в сети N’ появляется также множество },...,,{)( )(21 pnrrrpT =′ новых переходов, которые связывают места p1,p2, ... , pn(p) из множества P’(p) в кольцевую сеть. При этом, если n(p)=1, то новые переходы не вводятся. Таким образом, ).)((U Pp pTTT ∈ ′∪=′ 4) Для каждой дуги сети N, связывающей место p с некоторым переходом t и имеющей кратность W(p,t), заводятся W(p,t) дуг, связывающих t с местами p1, p2, ... , pn(p). При этом распределение дуг в сети N’ по местам p1, p2, ... , pn(p) происходит произвольным образом, лишь бы не возникали ситуации, когда переход и место связаны более, чем одной дугой [4]. Для последнего пункта следует сделать замечание, касательно распределения дуг, поскольку предлагаемый «произвольный» порядок все-таки должен быть как-то оговорен и формализован. В программном обеспечении, которое будет рассмотрено ниже, при реализации этого отдельно взятого пункта, был использован подход, который состоит в следующем: поскольку переход и место могут быть связаны только одной дугой в ординарной сети, то матрицы инцидентности ),( ptF ′ и ),( tpF ′ будут содержать только единичные коэффициенты. Так как количество переходов (t) полученной матрицы F ′ равно ∑ ∈ + Pp n(p) \|T\| , а количество мест (p) равно Xx∈ , что, собственно, и определяет размерность полученной матрицы инцидентности, то предлагается леворекурсивное заполнение коэффициентами соответствующих результирующих матриц инцидентности единичными коэффициентами. Заметим, что количество единичных коэффициентов в строках и столбцах матриц ),( ptF ′ и ),( tpF ′ для первых \| T \| переходов соответственно будет равно сумме коэффициентов строк и столбцов исходных матриц ),( ptF и ),( tpF для каждого из переходов. Также следует отметить тот факт, что оставшаяся часть результирующей матрицы инцидентности размерностью ∑∑ ∈∈ × PpPp n(p)n(p) представляет собой диагональную матрицу с единичными коэффициентами. Причем если количество переходов исходной сети Петри было равно t, а количество мест равно p, и при этом количество переходов результирующей матрицы равно ptt ′+=′ , а мест ∑ ∈ =′ Pp n(p)p , то диагональные матрицы будут сформированы следующим образом (для ),(),( tpFиptF ′′ соответственно ): для ),( ptF ′ для ),( tpF ′ 0001 1000 01002 00101 21 t pt pt ppp ′ +′−′ +′−′ ′′′ M LM 1000 0100 0010 0001 21 2 1 p p p tptpt ′ ′ ′ ′+′−′+′−′ M LM Как видно из представленных частей результирующих матриц инцидентности, в первой из них представлено закрытие кольцевой сети, что соответствует пункту 3 алгоритма построения ординарной сети Петри. Рассмотренный выше алгоритм нашел свое применение при создании программного обеспечения по преобразованию произвольной заданной сети Петри в соответствующую ей ординарную сеть, - о нем, а также об особенностях его использования пойдет речь в следующем разделе. 3. О реализации алгоритма преобразования Описанный выше алгоритм преобразования для сетей Петри был реализован в программном обеспечении «Преобразователь сетей Петри», написанном на языке программирования C++Builder. Программа представляет собой Windows – приложение, позволяющее производить ввод сети Петри и производить расчет коэффициентов для ординарной сети Петри. Общий вид приложения показан на рис 1. Рис. 1. Как видно из рисунка, ввод коэффициентов матрицы инцидентности для произвольной сети Петри происходит в двух таблицах, размерность которых задается при помощи полей: «Количество условий-мест сети Петри», а также «Количество событий-переходов сети Петри». Увеличение или уменьшение значений в этих полях осуществляется посредством использования стрелок «вверх/вниз», а также можно вводить нужные значения с клавиатуры. Перемещение по полям таблицы производится при помощи клавиш «влево/вправо» и «вверх/вниз», «Enter» - исправление значения. Есть возможность одновременной очистки всех введенных коэффициентов, для этого можно воспользоваться соответствующим пунктом главного меню «Функции», как показано на рис. 2. Рис. 2. Программа также позволяет сохранять введенные коэффициенты матриц инцидентности в файл или загружать предварительно сохраненные сети Петри из файла. Осуществляется эта возможность при помощи пунктов основного меню «Файл» - рис. 3. Рис. 3. Неактивными пунктами меню на рисунке 3 можно будет пользоваться после выполнения работы алгоритма по преобразованию произвольной сети Петри в ординарную. Описание работы с этими пунктами меню будет дано ниже по тексту статьи. На рис. 2 также есть подменю «Расчет ординарной сети Петри». Посредством выбора этого пункта меню или аналогичной кнопки на главной форме производится запуск расчета сети Петри, в процессе которого программа может выдавать некоторые информационные сообщения. Рис. 4. Сообщение на рис. 4 выдается для проведения возможного контроля за ходом работы алгоритма, поскольку информация о сумме максимальных кратностей дуг соответствует второму шагу работы алгоритма, изложенного выше. Об успешном проведении расчета ординарной сети программа выдаст соответствующее сообщение типа «Расчет ординарной сети Петри произведен за 20 мсек». Таким образом пользователь может также получить информацию о затратах времени на проведение расчета ординарной сети. Это может быть полезно, когда необходимо проследить временную зависимость работы алгоритма при различных входных параметрах, т.е. при задании различных матриц инцидентности, соответствующих произвольным сетям Петри. Рис. 5. Следует отметить, что визуальное отображение полученных матриц может занимать довольно продолжительные интервалы времени, поэтому в программе предусмотрено соответствующе сообщение пока описанный процесс выполняется, – показано на рисунке 5. После того как процесс заполнения таблиц с результирующими матрицами инцидентности уже завершился, пользователь видит форму, показанную на рис. 6. На форме также содержится информация о времени, затраченном на построение ординарной сети Петри. При желании можно также увидеть размерность матриц инцидентности, информация об этом содержится в левом верхнем углу каждой из таблиц, находящихся на форме. Этим работа с формой не заканчивается. Дело в том, что было бы весьма полезно получить матрицу инцидентности не в виде двух составляющих, а как единую целую, - в программе предусмотрена и такая возможность, хотя о ней речь пойдет ниже. Почему нельзя было сразу отобразить двухмерную матрицу инцидентности ординарной сети Петри, - потому, что при наличии в полученной сети полуциклов они в такой матрице исчезают. Для этого и были показаны составляющие матрицы инцидентности на форме с результатами вычислений. На рассматриваемой форме ест возможность сохранения результатов вычислений, для чего необходимо воспользоваться пунктом контекстного меню «Сохранить ординарную сеть в файл...» (рис. 8), после этого появляется стандартное окно Windows, в котором указывается имя файла и путь, по которому нужно провести сохранение. После успешного сохранения программа выдаст соответствующее сообщение. Есть также возможность получения двухмерной матрицы инцидентности для дальнейших исследований. Для вызова этой функции достаточно воспользоваться соответствующим пунктом контекстного меню «Получить 2D – матрицу инцидентности для ординарной сети Петри», как показано на рис. 7. После вызова этого пункта меню, пользователь получает новую форму (рис. 8) с соответствующей двухмерной матрицей инцидентности, причем также существует возможность сохранения полученных результатов в файл при помощи соответствующего пункта контекстного меню, причем сохранение производится в формате TSS (усеченное множество решений) [5]. Рис. 6. Пункт контекстного меню «Закрыть» присутствует на всех выше и ниже указанных формах и работает одинаково - закрывает активную форму, аналогичного результата можно достичь путем использования соответствующей кнопки в правом нижнем углу формы. Рис. 7. Рис. 8. Возможность сохранения результатов вычислений, представленных на форме (рис. 8), осуществляется посредством вызова контекстного меню (рис. 9), а затем выбора пункта меню «Сохранить ординарную сеть в формате TSS». Эта возможность весьма полезна при дальнейшем анализе ординарной сети, например: при поиске в полученной матрице инцидентности T-инвариантов, а также при произведении некоторых преобразований с матрицей для нахождения S-инвариантов. Рис. 9. Представленное программное обеспечение содержит также большое множество проверок на введенные (или не введенные) коэффициенты или загружаемую из файла информацию, которые, в принципе, являются нормой для программ такого рода. Поэтому при отсутствии всех необходимых параметров процесс получения ординарной сети Петри может не начаться, - в этом случае следует четко следовать замечаниям программы. Наличие такого рода нюансов в программе изменяется от версии к версии, информацию о которой можно получить, воспользовавшись пунктом главного меню «О программе ...». 4. Примеры работы программы. Далее представлены некоторые примеры работы рассмотренного программного обеспечения с временными затратами на преобразование сетей Петри. 1). Для заданной сети Петри получим такие первоначальные матрицы инцидентности:       = 1 2 ),( ptF , ( )10),( =tpF . t1 t2 p1 Сумма максимальных кратностей дуг равна 2: n(p) = max p (2+0, 1+1) = max p (2,2) = 2. Результирующее количество мест 2=′p и переходов 42)( =+=′ pnt , при этом матрицы имеют вид:             =′ 01 10 01 11 ),( ptF и       =′ 1000 0110 ),( tpF . Расчет ординарной сети в этом случае произведен за 0 мсек. Результирующая ординарная сеть Петри имеет вид: 2). Для заданной сети Петри получим такие первоначальные матрицы инцидентности:           = 00 10 02 ),( ptF ,       = 210 010 ),( tpF . Сумма максимальных кратностей дуг равна 4: 422)2,2( 02 21 02 max 0020 1110 0002 max)( =+==           =           ++ ++ ++ = pp pn . Результирующее количество мест 4=′p и переходов 73)( =+=′ pnt , при этом матрицы имеют вид:                       =′ 0001 1000 0100 0010 0000 0001 0011 ),( ptF и             =′ 1000000 0100000 0010110 0001110 ),( tpF t2 t1 t3 t4 p1 p2 t1 t2 t3 p1 p2 Расчет ординарной сети в этом случае произведен за 0 мсек. Результирующая ординарная сеть Петри имеет вид: Литература: 1. Genrich H., Lauterbach K., Thiagarajan P.S. Elements of general net theory. – In: Lecture Notes of Computer Science. Berlin: Springer-Verlag, 1979, p. 21-164. 2. Hack M. Decision problems for Petri nets and vector addition systems. – Project MAC Memo 59. Cambridge, 1975. 3. Hack M. Decidability questions for Petri nets. – Laboratory for Computer Science TR 161. Cambridge, 1976. 4. Котов В.Е. Сети Петри. М.: Наука. Главная редакция физико-математической литературы, 1984, с.11-58. 5. Усатюк О.В. Реализация инкрементной версии алгоритма построения минимального множества решений системы линейных уравнений на множестве натуральных чисел. Киев. УСиМ. – 2002. - №2, с.26-34. t6 t1 t2 t3 t4 t5 t7 p1 p2 p3 p4

Реализация алгоритма преобразования неординарной сети Петри в ординарную

Репозитарії

Схожі ресурси