1. Сети Петри - происхождение, основные понятия, область применения, свойства вычислений (1265177)
Текст из файла
Ìîäåëèïîñëåäîâàòåëüíûõèïàðàëëåëüíûõâû÷èñëåíèéÂ.À. ÇàõàðîâËåêöèÿ 1.1. Ñåòè Ïåòðè: ïðîèñõîæäåíèå.2. Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿ3. Ñåòè Ïåòðè: îáëàñòè ïðèìåíåíèÿ èñâîéñòâà ïîâåäåíèÿÑåòè Ïåòðè: ïðîèñõîæäåíèå 1949 Ð. Ôåéíìàí ïðåäëîæèë èñïîëüçîâàòü âêâàíòîâîé ôèçèêå ãðàôè÷åñêèé ñïîñîá îïèñàíèÿâçàèìîäåéñòâèÿ ýëåìåíòàðíûõ ÷àñòèö:@ôîòîí@ôîòîí@âçàèìîäåéñòâèåyýëåêòðîíy@@@ïîçèòðîíR@À ìîæíî ëè îïèñûâàòü îñóùåñòâëåíèå õèìè÷åñêèõðåàêöèé ïðè ïîìîùè ïîäõîäÿùèõ ãðàôîâûõêîíñòðóêöèé?Ñåòè Ïåòðè: ïðîèñõîæäåíèåÒàêîé ñïîñîá ïðåäëîæèë â 1939 ã. (îïóáëèêîâàí â1962 ã.) Êàðë Ïåòðè.'$'$12--&%&%I@@12@@@@@12@'$@'$R@@ @2&%1&%Ñåòè Ïåòðè: ïðîèñõîæäåíèåÒàêîé ñïîñîá ïðåäëîæèë â 1939 ã. (îïóáëèêîâàí â1962 ã.) Êàðë Ïåòðè.êèñëîðîäO2'$ww'$1âîäà2--H2 O @&%&%I@@12@@@@@12@'$@'$R@âîäîðîäwýíåðãèÿ@ H2 w wE21&%&%Ñåòè Ïåòðè: ïðîèñõîæäåíèåÒàêîé ñïîñîá ïðåäëîæèë â 1939 ã.
(îïóáëèêîâàí â1962 ã.) Êàðë Ïåòðè.ãîðåíèå:êèñëîðîäO22H2 + O2 → 2H2 O'$w1'$w-âîäà2-H2 Ow @&%&%wI@@12@@@@@12@'$@'$R@âîäîðîäýíåðãèÿ@ H2 wE21&%&%Ñåòè Ïåòðè: ïðîèñõîæäåíèåÒàêîé ñïîñîá ïðåäëîæèë â 1939 ã. (îïóáëèêîâàí â1962 ã.) Êàðë Ïåòðè.ãîðåíèå:êèñëîðîäO22H2 + O2 → 2H2 O'$w'$12-y y-âîäàH2 O @&%&%I@@12@@@@@12@y'$@'$R@âîäîðîäýíåðãèÿ@ H2 wE21&%&%Ñåòè Ïåòðè: ïðîèñõîæäåíèåÒàêîé ñïîñîá ïðåäëîæèë â 1939 ã. (îïóáëèêîâàí â1962 ã.) Êàðë Ïåòðè.êèñëîðîäO2'$w'$12-- yyâîäàH2 O @&%&%I@@12@@@@@12@'$@'$R@âîäîðîäýíåðãèÿ@ yH2 wE21&%&%Ñåòè Ïåòðè: ïðîèñõîæäåíèåÒàêîé ñïîñîá ïðåäëîæèë â 1939 ã.
(îïóáëèêîâàí â1962 ã.) Êàðë Ïåòðè.êèñëîðîäO2'$w'$1âîäà2--H2 O @&%&%I@@12@@@@y @@12y'$@'$R@âîäîðîäýíåðãèÿ@ yH2 wE21&%&%ýëåêòðîëèç:2H2 O → 2H2 + O2Ñåòè Ïåòðè: ïðîèñõîæäåíèåÒàêîé ñïîñîá ïðåäëîæèë â 1939 ã. (îïóáëèêîâàí â1962 ã.) Êàðë Ïåòðè.êèñëîðîäO2'$w'$1âîäà2--H2 O @&%&%I@ w@12@@@@@12@'$@'$R@âîäîðîäýíåðãèÿ@ w wH2 wE21&%&%ýëåêòðîëèç:2H2 O → 2H2 + O2Ñåòè Ïåòðè: ïðîèñõîæäåíèåÒàêîé ñïîñîá ïðåäëîæèë â 1939 ã. (îïóáëèêîâàí â1962 ã.) Êàðë Ïåòðè.êèñëîðîäO2'$ww'$1âîäà2--H2 O @&%&%I@@12@@@@@12@'$@'$R@âîäîðîäwýíåðãèÿ@ H2 w wE21&%&%Ñåòè Ïåòðè: ïðîèñõîæäåíèåÑåòè Ïåòðè ïîçâîëÿþò îïèñûâàòü ñëîæíûåõèìè÷åñêèå ïðîöåññû.ïèðèò FeS2 îêñèä æåëåçà âîäà H2 O Fe2 O32 1P4PPPq P1PPqPäèîêñèä ñåðû1 PP1 111 PqPSO28PP11q 1P2êèñëîðîäO2êàòàëèçàòîðòðèîêñèä 11 V2 O5ñåðû SO3 1-ñåðíàÿêèñëîòàH2 SO41Òåõíîëîãèÿ ïðîèçâîäñòâà ñåðíîé êèñëîòû.Ñåòè Ïåòðè: ïðîèñõîæäåíèåÂïîñëåäñòâèè áûëî îáíàðóæåíî, ÷òî ñåòè Ïåòðèëó÷øå âñåãî ïðèãîäèëèñü äëÿ îïèñàíèÿ ïîâåäåíèÿðàñïðåäåëåííûõ ñèñòåì âçàèìîäåéñòâóþùèõïðîöåññîâ, â êîòîðûõ ïðîÿâëÿþòñÿ òàêèå ñâîéñòâàêàêIèòåðàöèîííîå âûïîëíåíèå äåéñòâèé(ðåêóðñèÿ),Iïàðàëëåëüíîå âûïîëíåíèå äåéñòâèé,Iíåîäíîçíà÷íîñòü âûáîðà î÷åðåäíîãî äåéñòâèÿ,Iêîíêóðåíöèÿ çà âû÷èñëèòåëüíûå èèíôîðìàöèîííûå ðåñóðñû.Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÎïðåäåëåíèå 1.Ñåòüþ íàçûâàåòñÿ äâóäîëüíûé îðèåíòèðîâàííûé ãðàôN = (P, T , F ) , â êîòîðîìI P íåïóñòîå ìíîæåñòâî ïîçèöèé (ìåñò, places);I T íåïóñòîå ìíîæåñòâî ïåðåõîäîâ (transitions);I F ⊆ (P × T ) ∪ (T × P) íåïóñòîå ìíîæåñòâî äóã(arcs).Ïðè ýòîì ïðåäïîëàãàåòñÿ, ÷òî ìíîæåñòâà ïîçèöèé èïåðåõîäîâ íå ïåðåñåêàþòñÿ, ò.å.
P ∩ T = ∅ , è êàæäàÿâåðøèíà ñåòè x, x ∈ P ∪ T , èíöèäåíòíà õîòÿ áû îäíîéâåðøèíå äðóãîãî òèïà, ò.å. èçîëèðîâàííûå âåðøèíûîòñóòñòâóþò.Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt11 @p2 @pt33- HHHHp6jH@@@Rt4-*$p4@@R P@PP t5qP- t2p5Ïðèìåð ñåòèN = (P, T , F )%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÄëÿ êàæäîãî ýëåìåíòà ñåòèçàïèñüþ•xx, x ∈ P ∪ Tìíîæåñòâî ýëåìåíòîâ, îáîçíà÷èì{y : (y , x) ∈ F }x ,,ÿâëÿþùèõñÿ ïðåäøåñòâåííèêàìè ýëåìåíòàà çàïèñüþx•{y : (x, y ) ∈ F }ýëåìåíòà x .ìíîæåñòâî ýëåìåíòîâÿâëÿþùèõñÿ ïîñëåäîâàòåëÿìè,Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt11 @p2• = {t1 , t2 }p2 @@pt33- HHHHp6jH@@@Rt4•-*$p4t5 = {p5 , p6 }@R P@PP t5qP- t2p5t5• = ∅%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏóñòü X ïðîèçâîëüíîå íåïóñòîå ìíîæåñòâî.Òîãäà ìóëüòèìíîæåñòâîì ñ îñíîâîé X íàçîâåì âñÿêóþôóíêöèþ M : X → N , ãäå N = {0, 1, 2, .
. . } .Îñíîâà X ýòî ñïèñîê òèïîâ ðåñóðñîâ, à ìóëüòèìíîæåñòâîM ýòî ïåðå÷åíü êîëè÷åñòâà ðåñóðñîâ êàæäîãî òèïà. Äëÿêàæäîãî ýëåìåíòà x, x ∈ X , çíà÷åíèå M(x) íàçûâàåòñÿêðàòíîñòüþ ýëåìåíòà x â ìóëüòèìíîæåñòâå M . ìóëüòèìíîæåñòâå, â îòëè÷èå îò ìíîæåñòâà, ìîæåò áûòüíåñêîëüêî êîïèé îäíîãî è òîãî æå ýëåìåíòà. ÅñëèM(x) = 0 äëÿ íåêîòîðîãî ýëåìåíòà x , òî ýòî îçíà÷àåò, ÷òîâ ìóëüòèìíîæåñòâå M íåò íè îäíîé êîïèè ýëåìåíòà x .Åñëè ìíîæåñòâî-îñíîâà X ëèíåéíî óïîðÿäî÷åíà, ò.å.X = hx1 , x2 , .
. . , xn i , òî ìóëüòèìíîæåñòâî M ïðåäñòàâèìîöåëî÷èñëåííûì âåêòîðîì hM(x1 ), M(x2 ), . . . , M(xn )i .Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÄëÿ ìóëüòèìíîæåñòâ ìîæíî ââåñòè îïåðàöèè àíàëîãè÷íûåîïåðàöèÿì íàä ìíîæåñòâàìèÏóñòü M, N äâà ìóëüòèìíîæåñòâà ñ îäíîé è òîé æåîñíîâîé X = hx1 , x2 , . .
. , xn i . ÒîãäàM ∪N = hmax(M(x1 ),N(x1 )),max(M(x2 ),N(x2 )),. . . ,max(M(xn ),N(xn ))i,M ∩N = hmin(M(x1 ),N(x1 )),min(M(x2 ),N(x2 )), . . . , min(M(xn ),N(xn ))i,M + N = hM(x1 ) + N(x1 ), M(x2 ) + N(x2 ), . . . , M(xn ) + N(xn )i ,M N = hM(x1 ) N(x1 ), M(x2 ) N(x2 ), . . . , M(xn ) N(xn )i ,ãäå(k − m, åñëè k ≥ m,k m =0, åñëè k < m.Íàïðèìåð, â ñëó÷àå M = h3, 5, 1i, N = h2, 0, 4i((M ∩ N) + M) (M ∪ N) = h2, 0, 0iÑåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÎïðåäåëåíèå 2.Îáûêíîâåííîé ñåòüþ Ïåòðè íàçûâàåòñÿ ñèñòåìàπ = (P, T , F , W , M0 ) , â êîòîðîéI (P, T , F ) ñåòü;I W ìóëüòèìíîæåñòâî ñ îñíîâîé F ðàñïðåäåëåíèåâåñîâ íà äóãàõ ñåòè;I M0 ìóëüòèìíîæåñòâî ñ îñíîâîé P íà÷àëüíàÿðàçìåòêà ñåòè.Ïîçèöèè ýòî òèïû ðåñóðñîâ, à ïåðåõîäû ýòîïðåîáðàçîâàòåëè ðåñóðñîâ.Ðàñïðåäåëåíèå âåñîâ îöåíèâàåò çíà÷èìîñòü êàæäîãî òèïàðåñóðñîâ äëÿ âûïîëíåíèÿ ïðåîáðàçîâàíèé.Íà÷àëüíàÿ ðàçìåòêà ýòî èñõîäíîå ñîñòîÿíèå ðåñóðñîâ.Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt11 @p2 @pt33- HHHHp6jH@@@Rt4-*$p4@@R P@PP t5qP- t2p5ÑåòüN = (P, T , F )%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt331 1 HH1HHp6jH @1@$1@*1 R@ t41 - pt112 -p2 @ 11p4@@R P1@PP t5qP1 - t2p5Ðàñïðåäåëåíèå âåñîâ ïåðåõîäîâW%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt113 @2p2 @pt330- HHHHp6jH@@@R0t4-*$0p4@@R P@t5PP 0qP- t2p5Íà÷àëüíàÿ ðàçìåòêàM0%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt11ttt @ôèøêè (tokens)pt33- HHHHp6jH@@R@@ t4R@tt- p4p2 @@@R P@PP t5qP- t2*p5Íà÷àëüíàÿ ðàçìåòêàM0 = h3, 2, 0, 0, 0, 0i$%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt331 1 tHH1HHp6jH @1@$1@*1 R@ t41- ttpt11tt 2 -p2 @ 11p4@@R P1@PP t5qP1 - t2%p5Îáûêíîâåííàÿ ñåòü Ïåòðèπ = (P, T , F , W , M0 )Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÐàçìåòêîé ñåòè N = (P, T , F ) íàçûâàåòñÿ âñÿêîåìóëüòèìíîæåñòâî M ñ îñíîâîé P ; ýòî ðàñïðåäåëåíèåðåñóðñîâ ïî òèïàì (ïîçèöèÿì).Ìíîæåñòâî âñåõ ðàçìåòîê ñåòè N îáîçíà÷èì çàïèñüþ MPÍà ìíîæåñòâå ðàçìåòîê ââåäåì îòíîøåíèå ÷àñòè÷íîãîïîðÿäêà: M1 M2 ⇔ ∀ x ∈ P : M1 (x) ≤ M2 (x).Íàïðèìåð, h2, 4, 0, 1i h3, 4, 2, 2i .Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÄëÿ çàäàííîãî ðàñïðåäåëåíèÿ âåñîâ W íà ìíîæåñòâå äóãñåòè N = (P, T , F ) è äëÿ çàäàííîãî ïåðåõîäà t, t ∈ T ,ââåäåì äâà âèäà ðàçìåòîê FW (•, t) è FW (t, •) , êîòîðûåîïðåäåëÿþòñÿ ñîîòíîøåíèÿìè:(W (p, t) åñëè (p, t) ∈ F ,FW (•, t)(p) =0 èíà÷å;(W (t, p) åñëè (t, p) ∈ F ,FW (t, •)(p) =0 èíà÷å.Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt331 1 HH1HHp6jH @1@$1@*1 R@ t41- tpt11tt 2 -p2 @ 11p4@@R P1@PP t5qP1 - t2%p5Îáûêíîâåííàÿ ñåòü Ïåòðèπ = (P, T , F , W , M0 )Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt331 1 HH1HHp6jH @1@$1@*1 R@ t41- tpt11tt 2 -p2 @ 1p41@@R P1@PP t5qP1 - t2p5FW (•, t1 ) = h2, 1, 0, 0, 0, 0i%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt331 - t 1 HH1HHp6jH @1@$1@*1 R@ t41- tpt112 -p2 @ 1p41@@R P1@PP t5qP1 - t2p5FW (t1 , •) = h0, 0, 1, 1, 0, 0i%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÏîâåäåíèå ñåòè Ïåòðè ïðîÿâëÿåòñÿ â ïîñëåäîâàòåëüíîìñðàáàòûâàíèè ïåðåõîäîâ, ïðèâîäÿùåì ê èçìåíåíèþðàçìåòêè.Ïóñòü çàäàíà ñåòü Ïåòðè π = (P, T , F , W , M0 ) , ïåðåõîät, t ∈ T , è ðàçìåòêà ñåòè M .Îïðåäåëåíèå 3.Ïåðåõîä t ñ÷èòàåòñÿ àêòèâíûì â ðàçìåòêå M , åñëèâûïîëíåíî óñëîâèå FW (•, t) M .Ðàçìåòêà, â êîòîðîé íè îäèí ïåðåõîä ñåòè íå ÿâëÿåòñÿàêòèâíûì, íàçûâàåòñÿ òóïèêîâîé .Îïðåäåëåíèå 4.Ðåçóëüòàòîì ñðàáàòûâàíèÿ àêòèâíîãî â ðàçìåòêå Mïåðåõîäà t ÿâëÿåòñÿ ðàçìåòêàM 0 = (M FW (•, t)) + FW (t, •).Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÒàêèì îáðàçîì, íà ìíîæåñòâå ðàçìåòîê MP ñåòè Ïåòðèπ = (P, T , F , W , M0 ) ìîæíî ââåñòè îòíîøåíèåñðàáàòûâàíèÿ ïåðåõîäîâ :ðàçìåòêà M 0 íåïîñðåäñòâåííî ñëåäóåò çà ðàçìåòêîé Mîòíîñèòåëüíî ïåðåõîäà t, t ∈ T , (îáîçíà÷àåòñÿ çàïèñüþtM −→ M 0 ) â òîì è òîëüêî òîì ñëó÷àå, êîãäà1) ïåðåõîä t àêòèâåí â ðàçìåòêå M , è2) ðàçìåòêà M 0 ÿâëÿåòñÿ ðåçóëüòàòîì ñðàáàòûâàíèÿïåðåõîäà t â ðàçìåòêå M .Ðåôëåêñèâíî-òðàíçèòèâíîå çàìûêàíèå îòíîøåíèÿñðàáàòûâàíèÿ ïåðåõîäîâ óñëîâèìñÿ îáîçíà÷àòü çàïèñüþt1 ,t2 ,...,tM −→∗ k M 0 :t1 ,t2 ,...,tttt12kM −→∗ k M 0 ⇔ M −→M1 −→· · · −→M 0.Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt331 1 t1HHHHp6jH @1@$1@*1R@ t41 - ttt1p1tt 2 -p2 @ 1p41@@R P1@PP t5qP1 - t2p5h3, 2, 0, 0, 0, 0i%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt331 - t 1 t1HHHHp6jH @1@$1@*1R@ t4tt 1 - t1p12 -p2 @ 1p41@@R P1@PP t5qP1 - t2p5t1h3, 2, 0, 0, 0, 0i −→h1, 1, 1, 1, 0, 0i%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt331 - t 1 t1HHHHp6jH @1@$1@*1R@ t4t 1 - t1p12 -p2 @ 1p41@@R P1@PP t5q t 1 - Pt2p5tt12h3, 2, 0, 0, 0, 0i −→h1, 1, 1, 1, 0, 0i −→h1, 0, 1, 1, 1, 0i%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt331 1 tHH1Hp61@HjH@t$1@*1 R@ t4t 1 - pt112 -p2 @ 1p41@@R P1@PP t5q t 1 - Pt2p5tt12h3, 2, 0, 0, 0, 0i −→h1, 1, 1, 1, 0, 0i −→h1, 0, 1, 1, 1, 0it3−→ h1, 1, 0, 1, 1, 1i%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt331 1 tHH1Hp61@HjH@tt$1@*1 R@ t41 - pt112 -p2 @ 1p41@@R P1@PP t5q t 1 - Pt2p5tt12h3, 2, 0, 0, 0, 0i −→h1, 1, 1, 1, 0, 0i −→h1, 0, 1, 1, 1, 0it3t4−→ h1, 1, 0, 1, 1, 1i −→ h1, 1, 0, 0, 1, 2i%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿpt331 1 tHH1Hp61@HjH@t$1@*1 R@ t41 - pt112 -p2 @ 1p41@@R P1@PP t5qP1 - t2p5tt12h3, 2, 0, 0, 0, 0i −→h1, 1, 1, 1, 0, 0i −→h1, 0, 1, 1, 1, 0it3t4t5−→ h1, 1, 0, 1, 1, 1i −→ h1, 1, 0, 0, 1, 2i −→h1, 1, 0, 0, 0, 1i%Ñåòè Ïåòðè: îñíîâíûå ïîíÿòèÿÂû÷èñëåíèåì ñåòè Ïåòðè π = (P, T , F , W , M0 ) íàçûâàåòñÿâñÿêàÿ ïîñëåäîâàòåëüíîñòü (êîíå÷íàÿ èëè áåñêîíå÷íàÿ)íåïîñðåäñòâåííî ñëåäóþùèõ äðóã çà äðóãîì ðàçìåòîê,íà÷èíàþùàÿñÿ íà÷àëüíîé ðàçìåòêîé M0 :tttti+112iM0 −→M1 −→· · · −→Mi −→ · · · .Ðàçìåòêà M 0 äîñòèæèìà èç ðàçìåòêè M â ñåòè Ïåòðè πt1 ,t2 ,...,tk(îáîçíà÷àåòñÿ M −→∗ M 0 ), åñëè îòíîøåíèå M −→∗ M 0âûïîëíÿåòñÿ äëÿ íåêîòîðîé ïîñëåäîâàòåëüíîñòè ïåðåõîäîât1 , t2 , .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
