1. Сети Петри - происхождение, основные понятия, область применения, свойства вычислений (1265177), страница 2
Текст из файла (страница 2)
. . , tk .Ðàçìåòêà M 0 äîñòèæèìà â ñåòè Ïåòðè π , åñëè îíàäîñòèæèìà èç íà÷àëüíîé ðàçìåòêè M0 â ñåòè Ïåòðè π .Ìíîæåñòâî âñåõ ðàçìåòîê, äîñòèæèìûõ (èç ðàçìåòêè M )â ñåòè Ïåòðè π , îáîçíà÷èì çàïèñüþ R(π) (ñîîòâåòñòâåííîR(π, M) ).Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÃðàôîì äîñòèæèìûõ ðàçìåòîê ñåòè Ïåòðè π íàçûâàåòñÿîðèåíòèðîâàííûé ãðàô Gπ , âåðøèíàìè êîòîðîãî ÿâëÿþòñÿäîñòèæèìûå ðàçìåòêè èç ìíîæåñòâà R(π) . ãðàôå Gπ èç âåðøèíû M â âåðøèíó M 0 âåäåò äóãà,ïîìå÷åííàÿ ïåðåõîäîì t â òîì è òîëüêî òîì ñëó÷àå, åñëètäëÿ ñåòè Ïåòðè π âûïîëíÿåòñÿ ñîîòíîøåíèå M −→ M 0 .Ãðàô äîñòèæèìûõ ðàçìåòîê ñåòè Ïåòðè ìîæåò áûòüêîíå÷íûì, íî ìîæåò áûòü òàêæå è áåñêîíå÷íûì.Êàæäûé ìàðøðóò â ãðàôå Gπ , èñõîäÿùèé èç íà÷àëüíîéâåðøèíû M0 , ñîîòâåòñòâóåò íåêîòîðîìó âû÷èñëåíèþ ñåòèÏåòðè π .Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêppt1t313tt 2 1 1 t1 @1@@HH1HHp6jH1R@ t41 - ttp2 @ 1p4@@R P1@PP t5qP1 - t2p5*$1%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêM0 = h3, 2, 0, 0, 0, 0iÑåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêppt1t313tt 2 1 1 t1 @1@@HH1HHp6jH1R@ t41 - ttp2 @ 1p4@@R P1@PP t5qP1 - t2p5*$1%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêppt1t3132 1 - t 1 t1 @1@@HH1HHp6jH1R@ t4t 1 - tp2 @ 1p4@@R P1@PP t5qP1 - t2p5*$1%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêM0 = h3,2, 0, 0, 0, 0i t 1)M1 = h1, 1, 1, 1, 0, 0iÑåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêppt1t313tt 2 1 1 t1 @1@@HH1HHp6jH1R@ t41 - ttp2 @ 1p4@@R P1@PP t5qP1 - t2p5*$1%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêppt1t313tt 2 1 1 t1 @1@@HH1HHp6jH1R@ t41 - tp2 @ 1p4@@R P1@PP t5q tP1 - t2p5*$1%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêM0 = h3,2,P0, 0, 0, 0iPPt2 PPP t 1)M1 = h1, 1, 1, 1, 0, 0iqPM2 = h3, 1, 0, 0, 1, 0iÑåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêppt1t3132 1 - t 1 t1 @1@@HH1HHp6jH1R@ t4t 1 - tp2 @ 1p4@@R P1@PP t5qP1 - t2p5*$1%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêppt1t3132 1 - t 1 t1p2 @ 1 @1@@HH1HHp6jH1@R t4t 1 - p4*$1@@R P1@PP t5q t 1 - Pt2p5%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêM0 = h3,2,P0, 0, 0, 0iPPt2 PPP t 1)qPM1 = h1, 1,P1, 1, 0, 0iPPPPt2M2 = h3, 1, 0, 0, 1, 0iPqPM3 = h1, 0, 1, 1, 1, 0iÑåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêppt1t313tt 2 1 1 t1 @1@@HH1HHp6jH1R@ t41 - tp2 @ 1p4@@R P1@PP t5q tP1 - t2p5*$1%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêppt1t3132 1 - t 1 t1p2 @ 1 @1@@HH1HHp6jH1@R t4t 1 - p4*$1@@R P1@PP t5q t 1 - Pt2p5%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêM0 = h3,2,P0, 0, 0, 0iPPt2 PPP t 1)M1 = h1, 1,P1, 1, 0, 0iqPM2 = h3, 1, 0, 0, 1, 0it2PP q) t1M3 = h1, 0, 1, 1, 1, 0iPPPPÑåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêppt1t313tt 2 1 1 t1 @1@@HH1HHp6jH1R@ t41 - tp2 @ 1p4@@R P1@PP t5q tP1 - t2p5*$1%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêppt1t313tt 2 1 1 t1p2 @ 1 @1@@HH1HHp6jHt411 - @Rp4*$1@@R P1@PP t5q tt 1 - Pt2p5%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏðèìåð ãðàôà äîñòèæèìûõ ðàçìåòîêM0 = h3,2,P0, 0, 0, 0iPPt2 PPP t 1)qPM1 = h1, 1,P1, 1, 0, 0iM2 = h3, 1, 0, 0, 1, 0i HHt2 HHHt2PP q) t1jM4 = h3, 0, 0, 0, 2, 0iM3 = h1, 0, 1, 1, 1, 0iPPPPòóïèêîâàÿ ðàçìåòêàè ò.
ä.Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÐàññìîòðèì ïðîèçâîëüíûé àëôàâèò A = {a1 , a2 , . . . , ak } èïîìåòèì êàæäûé ïåðåõîä t, t ∈ T , ñåòè Ïåòðè πíåêîòîðîé áóêâîé ϕ(t) èç ýòîãî àëôàâèòà.Ñâîáîäíûì ÿçûêîì ñåòè Ïåòðè π íàçûâàåòñÿ ìíîæåñòâîñëîât1 ,t2 ,...,tmL(π) = {w = ϕ(t1 )ϕ(t2 ) . . . ϕ(tm ) : ∃ M ∈ R(π) : M0 −→∗ M},êîòîðûìè ïîìå÷åíû ðàçíîîáðàçíûå ïîñëåäîâàòåëüíîñòèñðàáàòûâàíèé ïåðåõîäîâ.Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿßçûê ñåòè Ïåòðè π .pt3 c31 1 tH1HHp61@HjH@$1@*1 R@ t41 - ttpt11tt 2 -p2 @ 1ap4d1@@R P1@PP t5 aqP1 - t2 bp5bacda ∈ L(π), bb ∈ L(π), bba ∈/ L(π)%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÒåîðåìà î ñâîéñòâå ìîíîòîííîñòè ñåòåé Ïåòðè.Ïóñòü M è K äâå ðàçìåòêè ñåòè (P, T , F ) .Ïðåäïîëîæèì, ÷òî ïåðåõîä t àêòèâåí â ðàçìåòêå M ñåòèÏåòðè π1 = (P, T , F , W , M) , è â ðåçóëüòàòå åãîñðàáàòûâàíèÿ îáðàçóåòñÿ ðàçìåòêà M 0 .Òîãäà ïåðåõîä t òàêæå àêòèâåí â ðàçìåòêå M + K ñåòèÏåòðè π2 = (P, T , F , W , M + K ) , è â ðåçóëüòàòå åãîñðàáàòûâàíèÿ îáðàçóåòñÿ ðàçìåòêà M 00 = M 0 + K .Äîêàçàòåëüñòâî.tÅñëè M −→ M 0 , òî FW (•, t) M è ñïðàâåäëèâî ðàâåíñòâîM 0 = (M FW (•, t)) + FW (t, •) .Òîãäà F (•, t) M + K , è ïîýòîìó ïåðåõîä t àêòèâåí âðàçìåòêå M + K ñåòè π2 .Ïðè åãî ñðàáàòûâàíèè îáðàçóåòñÿ ðàçìåòêàM 00 = ((M + K ) FW (•, t)) + FW (t, •) = M 0 + K .
Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÑëåäñòâèå.Ïóñòü π1 = (P, T , F , W , M) è π2 = (P, T , F , W , M + K ) ïàðà ñåòåé Ïåòðè, â îñíîâå êîòîðûõ ëåæèò îäíà è òà æåñåòü (P, T , F ) . Òîãäà1) äëÿ ëþáîé ïîñëåäîâàòåëüíîñòè ïåðåõîäîâ t1 , t2 , . . . , tkè ðàçìåòêè M 0 âåðíî ñîîòíîøåíèåt1 ,t2 ,...,tt1 ,t2 ,...,tM1 −→∗ k M 0 =⇒ M + K −→∗ k M 0 + K .2) äëÿ ëþáîé ðàçìåòêè M 0 èç ìíîæåñòâà R(π1 ) ðàçìåòêàM 0 + K ïðèíàäëåæèò ìíîæåñòâó R(π2 ) .3) L(π1 ) ⊆ L(π2 ) .Ýòî îñíîâíàÿ òåîðåìà òåîðèè ñåòåé Ïåòðè; íà åå îñíîâåìîæíî ýôôåêòèâíî àíàëèçèðîâàòü ïîâåäåíèå ñåòåé.Ñåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿÑåòè Ïåòðè íàõîäÿò ïðèìåíåíèå âî ìíîãèõîáëàñòÿõ äåÿòåëüíîñòè, íå îãðàíè÷èâàÿñü îäíîéëèøü èíôîðìàòèêîé.Ðàññìîòðèì íåêîòîðûå èç ýòèõ ïðèëîæåíèé, àòàêæå âîçíèêàþùèå â íèõ çàäà÷è àíàëèçàïîâåäåíèÿ ñåòåé Ïåòðè.Ñåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿÒåëåêîììóíèêàöèîííûå ñèñòåìû.u-1áóôåð êàíàëñâÿçèuïðàâèëî êîììóòàöèèáóôåðÑåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿÒåëåêîììóíèêàöèîííûå ñèñòåìû.-1áóôåð êàíàëñâÿçèuïðàâèëî êîììóòàöèè- uáóôåðÑåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿÒåëåêîììóíèêàöèîííûå ñèñòåìû.-1áóôåð êàíàëñâÿçèu- uáóôåðïðàâèëî êîììóòàöèèÏðàâèëüíîå ôóíêöèîíèðîâàíèå ñåòè ïîäðàçóìåâàåò, ÷òî1) áóôåðû íå ïåðåïîëíÿþòñÿ,2) ñîîáùåíèÿ íå òåðÿþòñÿ, íå äóáëèðóþòñÿ è äîñòèãàþòïóíêòà íàçíà÷åíèÿ.Îïðåäåëèì ôîðìàëüíî ñîîòâåòñòâóþùèå ýòèìòðåáîâàíèÿì ñâîéñòâà ïîâåäåíèé ñåòåé Ïåòðè.Ñåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿÏîçèöèÿpâ ñåòè Ïåòðèπ = (P, T , F , W , M)íàçûâàåòñÿ îãðàíè÷åííîé , åñëè ñóùåñòâóåò òàêîå÷èñëîn, ÷òî äëÿ ëþáîé ðàçìåòêèâåðíî ðàâåíñòâî0M (p) ≤ nM 0 , M 0 ∈ R(π).Ñåòü Ïåòðè íàçûâàåòñÿ îãðàíè÷åííîé , åñëèëþáàÿ åå ïîçèöèÿ îãðàíè÷åíà.Î÷åâèäíî, ÷òî ñåòü Ïåòðè îãðàíè÷åíà òîãäà èòîëüêî òîãäà, êîãäà ìíîæåñòâî åå äîñòèæèìûõðàçìåòîêR(π)êîíå÷íî.,Ñåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿ12 5PPPPPPqu uiPPPP3PP )4Ïðèìåð íåîãðàíè÷åííîé ñåòè Ïåòðè.Ñåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿÏîçèöèÿpâ ñåòè Ïåòðèπ = (P, T , F , W , M)íàçûâàåòñÿ áåçîïàñíîé , åñëè äëÿ ëþáîé ðàçìåòêèM 0 , M 0 ∈ R(π), âåðíî ðàâåíñòâîM 0 (p) ≤ 1.Ñåòü Ïåòðè íàçûâàåòñÿ áåçîïàñíîé , åñëè ëþáàÿåå ïîçèöèÿ áåçîïàñíà.Ñâîéñòâî áåçîïàñíîñòè ðàçóìíî ïðîâåðÿòü òîëüêîäëÿ îðäèíàðíûõ ñåòåé Ïåòðè, ó êîòîðûõ âåñà âñåõäóã ðàâíû 1.Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿt1p1t 1 11pt31 -3H1HHp6HjH @1@@1R@ t41 - tp4p2 @ 1@@R P1@PP t5qP1 - t2p5Ïðèìåð íåáåçîïàñíîé ñåòè Ïåòðè.*$1%Ñåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿCåòü Ïåòðèπ = (P, T , F , W , M)íàçûâàåòñÿêîíñåðâàòèâíîé , åñëè äëÿ ëþáîé ðàçìåòêè00MðàâåíñòâîP, M ∈ R(π)P , âåðíî0M(p) =M (p) .p∈Pp∈P êîíñåðâàòèâíûõ ñåòÿõ îáùåå ÷èñëî ôèøåêîñòàåòñÿ íåèçìåííûì íà ïðîòÿæåíèè ëþáîãîâû÷èñëåíèÿ ñåòè.Íåòðóäíî ïðîâåðèòü, ÷òî ñåòü Ïåòðèπ = (P, T , F , W , M)ÿâëÿåòñÿ êîíñåðâàòèâíîéòîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîãî ïåðåõîäàt, t ∈ T, âåðíî ðàâåíñòâîFW (•, t) = FW (t, •).Ñåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿÏðîèçâîäñòâåííûå ïðîöåññû è áèçíåñ-ïðîöåññû.u-1çàãîòîâêàñòàíîêuèíñòðóìåíòèçäåëèåÑåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿÏðîèçâîäñòâåííûå ïðîöåññû è áèçíåñ-ïðîöåññû.-1çàãîòîâêàñòàíîêuèíñòðóìåíò- uèçäåëèåÑåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿÏðîèçâîäñòâåííûå ïðîöåññû è áèçíåñ-ïðîöåññû.-1çàãîòîâêàñòàíîêu- uèçäåëèåèíñòðóìåíòÏðàâèëüíîå ôóíêöèîíèðîâàíèå ñåòè ïîäðàçóìåâàåò, ÷òî1) ñòàíêè íå ïðîñòàèâàþò,2) ðàáî÷èå íå ìåøàþò äðóã äðóãó.Îïðåäåëèì ôîðìàëüíî ñîîòâåòñòâóþùèå ýòèìòðåáîâàíèÿì ñâîéñòâà ïîâåäåíèé ñåòåé Ïåòðè.Ñåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿÏåðåõîätâ ñåòè Ïåòðèπ = (P, T , F , W , M)íàçûâàåòñÿ æèâûì , åñëè äëÿ ëþáîé ðàçìåòêèM 0 , M 0 ∈ R(π) , ñóùåñòâóåò òàêàÿ ðàçìåòêàM 00 , M 00 ∈ R(π, M 0 ) , âåðíî ñîîòíîøåíèåFW (•, t) M 00 .Æèâîñòü ïåðåõîäàtîçíà÷àåò, ÷òî ëþáîå êîíå÷íîåâû÷èñëåíèå ìîæíî ïðîäîëæèòü òàêèì îáðàçîì,÷òîáû íà íåêîòîðîì øàãå ñðàáîòàë ïåðåõîät.Ñåòü íàçûâàåòñÿ æèâîé , åñëè âñå ïåðåõîäû ñåòèÿâëÿþòñÿ æèâûìè.Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt11tt 2 -pt331 1 tHH1Hp6HjH @1@$1@*1 R@ t41- t tp2 @ 1@1p4@R P1@PP t5qP1 - t2p5Ïåðåõîä t2 ÿâëÿåòñÿ æèâûì.Âñå îñòàëüíûå ïåðåõîäû æèâûìè íå ÿâëÿþòñÿ.1%Ñåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿÏåðåõîä t â ñåòè Ïåòðè π = (P, T , F , W , M) íàçûâàåòñÿóñòîé÷èâûì (persistent), åñëè äëÿ ëþáîé ðàçìåòêèM 0 , M 0 ∈ R(π) , è äëÿ ëþáîãî ïåðåõîäà t 0 , t 0 6= t , âåðíîñîîòíîøåíèåFW (•, t) M 0 ∧ FW (•, t 0 ) M 0 ⇒ FW (•, t)+FW (•, t 0 ) M 0 .Óñòîé÷èâîñòü ïåðåõîäà t îçíà÷àåò, ÷òî åñëè ýòîò ïåðåõîäìîæåò ñðàáîòàòü, òî íèêàêîé äðóãîé ïåðåõîä íå ìîæåò,ñðàáîòàâ, ëèøèòü åãî ýòîé âîçìîæíîñòè.Ñåòü íàçûâàåòñÿ óñòîé÷èâîé , åñëè âñå ïåðåõîäû ñåòèÿâëÿþòñÿ óñòîé÷èâûìè.Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt331 1 tHH1Hp6HjH @1@$1@*1 R@ t41- ttpt11tt 2 -p2 @ 1p41@@R P1@PP t5qP1 - t2p5Ïåðåõîä t1 ÿâëÿåòñÿ íåóñòîé÷èâûì.Âñå îñòàëüíûå ïåðåõîäû ÿâëÿþòñÿ óñòîé÷èâûìè.%Ñåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿÄðóãèå îáëàñòè ïðèìåíåíèÿ ñåòåé Ïåòðè.ïîçèöèÿïåðåõîäïîçèöèÿïðåäóñëîâèÿñîáûòèåïîñòóñëîâèÿâõîäíûåîïåðàòîðâûõîäíûåäàííûåðåñóðñûäàííûåðàáîòàïîòðåáëåííûåïðåäïîñûëêèðåñóðñûïðîèçâåäåííûåëîãè÷åñêîåïðàâèëîçàêëþ÷åíèÿÑåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ è ñâîéñòâàïîâåäåíèÿÇàäà÷è àíàëèçà ñåòåé Ïåòðè ýòî çàäà÷è ïðîâåðêèñâîéñòâ îãðàíè÷åííîñòè, áåçîïàñíîñòè, æèâîñòè,óñòîé÷èâîñòè, à òàêæå äâå öåíòðàëüíûå çàäà÷è òåîðèèñåòåé Ïåòðè:I ïðîáëåìà äîñòèæèìîñòè : äëÿ çàäàííîé ñåòè Ïåòðèπ = (P, T , F , W , M) è çàäàííîé ðàçìåòêè M 0ïðîâåðèòü âêëþ÷åíèå M 0 ∈ R(π) ;I ïðîáëåìà R-ýêâèâàëåíòíîñòè : äëÿ çàäàííîé ïàðûñåòåé Ïåòðè π1 = (P, T1 , F1 , W1 , M1 ) èπ2 = (P, T2 , F2 , W2 , M2 ) ñ îäíèì è òåì æå ìíîæåñòâîìïîçèöèé P ïðîâåðèòü ðàâåíñòâî R(π1 ) = R(π2 ) .Èçó÷åíèå ýòèõ çàäà÷ ïðîâåäåì â ñëåäóþùèõëåêöèÿõ.ÊÎÍÅÖ ËÅÊÖÈÈ 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
