Mavzu: parallel dasturlashda kelishuv. Petri tarmog‘i magistrant: A

Invariantlik va Petri tarmog’ida kelishuv
PNni tahlil qilishda matritsali yondashuvda asosiy tushunchalar p- va t-invariantlar tushunchalari va mos keladigan o'zgarmas va izchil PN tushunchalaridir.
Butun vektor Y = (y1, y2,…, yn), bu chiziqli tizimning yechimi

belgilanmagan Petri to'rining p-invarianti < C, − > deyiladi.
Eslatma. Bu yerda va pastda t ustun belgisi vektor yoki matritsani ko‘chirish operatsiyasini bildiradi.
Butun vektor X = (x1, x2,…, xm), bu chiziqli tizimning yechimidir
XC = 0,
NSP < C, − > ning t-invarianti deyiladi. Shunga ko'ra, agar u p-invariantga ega bo'lsa, NSP o'zgarmas (consistent) deb ataladi.
Y > 0 (t-invariant X > 0), uning barcha komponentlari yi (xj) musbat
Keling, o'zgarmas va/yoki izchil NSP tushunchalari bilan uning sig'imi va faolligi bilan bog'liq bayonotlar to'plamini sanab o'tamiz.
xususiyatlari.
1. Agar mavjud bo'lsa, NSP izchil bo'ladi
m 0 belgisi va o'tish otishmalarining ketma-ketligi s shunday bo'ladi
nima
0 0
m mk
s →
.
2. Agar NSP cheklangan va tirik bo'lsa, u holda kelishilgan.
3. Agar NSP o'zgarmas bo'lsa, u holda u chegaralangan.
4. Invariant NSP pozitsiyalari to'plami boshi berk ko'cha va tuzoqni hosil qiladi.
5. Agar NSP uchun < C, − > butun sonli musbat vektor Y mavjud bo‘lsa, CY t < 0 bo‘lsa, u holda < C, − > jonsiz va mos kelmaydigan bo‘lib, P* = {pi | yi > 0} boshi berk ko‘chani hosil qiladi.
6. Agar tirik SP < C, µ o > butun vektor Y, Y > 0 bo‘lsa, shunday bo‘ladiki.
CY t > 0, keyin < C, µ o > cheklanmaydi.
7. Agar NSP < C, − > uchun CY t > 0 bo‘ladigan Y, Y > 0 vektor mavjud bo‘lsa, u holda:
a) < C, − > tirik bo‘lsa, u chegaralanmagan;
b) < C, − > izchil emas;
c) pozitsiyalar to'plami P* = {pi | yi > 0} - tuzoq.
8. X = (x1, x2,…, xm), X > 0 butun vektori mavjud bo‘lgandagina NSP < C, − > chegaralanmagan bo‘ladi, buning uchun
XC > 0.
9. Agar NSP < C, − > uchun X > 0 butun vektor mavjud bo'lsa, shunday qilib
bu XC < 0, keyin:
a) chegaralanganligi sharti bilan < C, − > jonsizdir;
b) < C, − > invariant emas.
10. Agar NRS < C, − > chegaralangan va izchil NRS bo'lsa, u o'zgarmasdir va har qanday belgilangan NS < C, µ o > uchun erishish mumkin bo'lgan belgilar to'plami juftlik bilan taqqoslanmaydigan vektorlardan iborat. Shuni ta'kidlash kerakki, berilgan chegaralangan va izchil NSP uchun < C, - >
belgilar to'plamining kardinalligi bo'yicha yuqori chegarani hisoblash mumkin.
Masalan, xavfsiz < C, µ o > uchun quvvatni aniqlash oson
erishish mumkin bo'lgan belgilar to'plami Ck n bilan chegaralanadi, bu erda juft n uchun k = n/2 va toq n uchun k = (n-1)/2.
11. Agar NSP < C, − > chegaralangan va tirik bo‘lsa, u ham izchil va o‘zgarmasdir.
12. Agar NSP < C, − > invariant va nomuvofiq bo‘lsa, u holda
jonsiz.
13. Agar NSP < C, − > izchil va o‘zgarmas bo‘lsa, u holda emas.
cheklangan.
Keling, yuqoridagi bayonotlarning ba'zilariga izoh beraylik (ko'pchilik
mazmuni nuqtai nazaridan ancha shaffof
va o'quvchi tasviriy misollarni o'ziga xos mashq sifatida ko'rib chiqsa yaxshi bo'ladi). Avvalo, biz munosabatlarni muhokama qilishimiz kerak
NSP ning cheklanganlik va jonlilik xususiyatlari bilan o'zgarmaslik va izchillik tushunchalari. Xususan, 3-bayon etarli shartni beradi,
va 8-tasdiq chegaralanganlik uchun zarur va yetarli shartdir.

tomonidan berilgan NSP uchun p-invariantni hisoblashga harakat qilaylik

guruch. 2.16 va yorliq. 2.2. (2.3) shartga asosan tenglamalar tizimi bo'ladi
quyidagi shaklga ega:

Buni ko'rish oson, chunki uning nolga teng bo'lmagan yechimlari to'plami bo'sh

u invariant emas. Shuning uchun 3-tasdiqning sharti qanoatlanmaydi. Biroq, ushbu NSPning cheksizligi to'g'risida xulosa chiqarish uchun 8-bayonning shartini tekshirish kerak, ya'ni. XC > 0 bo'lgan butun X > 0 vektorini topishga harakat qiling. Buni ko'rish oson
tengsizliklar tizimi

ning X > 0 yechimi yo‘q, chunki (X > 0) ∧ (x1 > x2 > x3) ⇒ x3 < x1 + x2, birinchi tengsizlikka zid: x3 > x1 + x2. Shuning uchun NSP cheklangan.
Vaziyatni tekshirish orqali ushbu NSP jonli emasligini tekshirish oson
5-bayon: Y > 0 uchun CY t < 0 tengsizligining yechimi bor, ya’ni. (y2 < y1) ∧ (y3 < y1 + y2) ∧ (y1 < y3) shartni qanoatlantiradigan yechim, masalan, Y = (3, 2, 4).
Keling, NRSni ko'rib chiqaylik, u avvalgisidan faqat t3 dan p1 gacha yoyda 2 og'irlik mavjudligi bilan farq qiladi. Tegishli insidans matritsasi bo'ladi
o'xshamoq:

Bu sistemada shartni qanoatlantiradigan cheksiz Y > 0 yechimlar to‘plami mavjud: y1 = y2, y3 = 2y1.
Masalan, Y = (1, 1, 2). Shuning uchun NSP o'zgarmas va chegaralangan.
8-taklifning sharti ushbu NSS uchun qanoatlantirmasligini ko'rish oson: tengsizliklar tizimi


X > 0 uchun yechimga ega emas, chunki ikkinchi va uchinchi tengsizliklardan
x1 > x2 > x3 ni nazarda tutadi, bu birinchi tengsizlikka mos kelmaydi.
Muvofiqlik xususiyati tizim qarori bilan belgilanishi mumkin
XC = 0 ko'rinishdagi tenglamalar, ya'ni,


x1 = x2 = x3 ni qanoatlantiruvchi X > 0 butun son yechimlarining cheksiz to'plamiga ega, masalan X = (1, 1, 1) . Bu yechimlarning barchasi NSP ning t-invariantlaridir.
Ehtiyotkor o'quvchi buni yuqoridagilardan payqagan bo'lishi mumkin
Bayonotlarga ko'ra, jonlilikning yo'qligi uchun faqat etarli sharoitlar mavjud va shuning uchun tiriklik xususiyatini tekshirish har doim ham ushbu yondashuv doirasida amalga oshirilmaydi.
Darhaqiqat, oxirgi misol tiriklik mulkining "makkorligi" ni ko'rsatadi, ya'ni: shunga qaramay.
NSP o'zgarmas, cheklangan va izchil; u (tarkibiy jihatdan) tirik emas, ya'ni. mos keladigan Petri tarmog'i < C, µ o > tirik bo'lgan µ 0 yorlig'i mavjud emas. Unda
uchun ushbu Petri tarmog'ining markirovka diagrammasini qurish orqali tekshirish mumkin
0
m = (2 0 0). Diagrammadan ko'rinib turibdiki, p1 va p2 dan markerlarning cheksiz oqib chiqishi imkoniyatini hisobga olgan holda, har doim µ(p1) = µ(p3) = 0 va t2 o'tish o'lik bo'lgan belgiga erishish mumkin.
Quyidagi faktga ham e'tibor qaratsak. Bunga qaramay
masalan, CY t < 0 qanoatlanmaydigan shunday Y > 0 ning mavjudligi sharti,
bu tarmoqda blokirovka mavjud {p1, p3}. Shuning uchun, boshi berk ko'chaga tushib qolganidan,
jonlilikning yo'qligi ham CY t < 0 bo'lgan Y > 0 ning mavjudligini bildirmaydi.
Petri to'rlarining konservatizm xususiyati alohida e'tiborga loyiqdir.
bu NSP ning p-invariant tushunchasi bilan uzviy bog'liqdir. Gap shundaki
(2.3) shakldagi tenglamalar tarmoq ishining statsionar rejimlariga mos keladi. Shuning uchun Y vektori invariant nomini oldi. Ushbu argumentlarda zaruriy aniqlik Petri to'rlarining asosiy tenglamasini quyidagi o'zgartirish orqali kiritiladi (2.2). Ko'paytirish
unga
Y t , biz skalyar tenglamani olamiz

uchun (2.3) dan kelib chiqadiki, tarmoqdagi marker doimiy doimiydir
Petri: µ ⋅Y t = const , ya'ni. Petri'ining Y invarianti bilan har qanday yorlig'i uchun bu o'zgarmas va markalash vektorining mahsuloti doimiy barqarordir.
Bu qonun Kirxgofning doimiylik qonunining bevosita analogidir
elektr zanjiridagi zaryadlar oqimi.
Ko'rinib turibdiki, NSP ning o'zgarmasligi ta'rifida shunday belgilab qo'yilgan
Y vektorining komponentlari musbat bo'lishi kerak. Haqiqatan ham,
agar i > 0 har qanday i uchun to‘g‘ri bo‘lsa, konservatizm xossasi, ya’ni. marker oqimining doimiyligi butun Petri tarmog'ini qamrab oladi.
Umuman olganda, NSP uchun juda ko'p invariantlar bo'lishi mumkin,
ular orasida, albatta, barcha komponentlar ijobiy bo'lmaganlar bo'lishi mumkin. Bunday invariantlar uchun tarmoqning konservativ deb ataladigan komponenti haqida gapirish odatiy holdir, ya'ni: agar Yr vektori NSP ning p-invariantlaridan biri bo'lsa, u ma'lum bir kichik to'plamni tanlaydi.
Pr ⊂ P pozitsiyalari shundayki, pi ∈ Pr vektorning i-komponenti Yr dan katta bo'lsa.
nol. Bu kichik to'plam o'zgarmas Yr va shakllarning tayanchi deb ataladi
tarmoqning konservativ komponenti, buning uchun uning pozitsiyalaridagi markerlarning vaznli yig'indisi ish paytida doimiy bo'ladi:

P-invariantning qiymatiga ko'ra, konservativ komponentning har bir pozitsiyasi uchun k markerlar sonining yuqori chegarasini topish mumkinligini tushunish oson.

tarmoqlar. Shunday qilib, pi ∈ Pr pozitsiyasi uchun

bu yerda ⎣ x⎦ x - x dan kichik yoki teng eng yaqin butun son.
Masalan, insidans matritsasi bo'lgan NSP uchun

minimal musbat p-invariant Y = (1 1 2). Vektorning barcha komponentlari ijobiy bo'lgani uchun butun tarmoq o'zgarmasdir,

bular. konservativ.
Y ning qiymatini (2.5) ga almashtirib, mk 0 = (2 0 0) vektorni dastlabki etiketka sifatida qabul qilib, xarakteristik belgilar tenglamasini topamiz.
tarmoqlar.
Keling, yozamiz:

qayerda m
i, 1 ≤ i ≤ 3, m1 + m2 ni bildiruvchi vektorning komponentlari
+2m
3 = 2. Bu tenglamaning mi ≥ 0 shartidagi butun sonli yechimlari,
1 ≤ i ≤ 3 belgilari bo'ladi: 200, 110, 020 va 001.
Invariant PN ning erishish mumkin bo'lgan belgilari to'plamining xarakterli tenglamasini bilish, shuningdek, o'lik nuqta mavjudligini tekshirishga yordam beradi.
belgilar. O'lik nuqtani belgilash sharti har qanday SP o'tishlarini ishga tushirishning mumkin emasligi sharti bilan bir xil. Topish maqsadida
bunday shartda a funktsiyaning matritsali tasviri (kirish pozitsiyalari va o'tishlarning insidans funktsiyasi) ishlatiladi. Shunday qilib, bizning misolimiz uchun

Ushbu matritsaning qatorlari o'tishlarni tetiklash uchun minimal belgilash vektorlarini aniqlaganini ko'rish oson. Shubhasiz, har qanday o'lik bo'lmagan nuqta
belgilash berilgan matritsaning kamida bitta qatorini qamrab olishi kerak. Shunday qilib, berilgan matritsa uchun o'lik holati quyidagi mantiqiy ifoda bilan berilishi mumkin:

shaklga osongina aylantiriladi:

Tizimni birgalikda hal qilib:


biz yagona qiymatni olamiz m = (0 2 0) , bu o'lik belgiga mos keladi.
Ko'rib chiqilgan misollar Petri to'rlarini strukturaviy tahlil qilish muammosini hal qilishning o'zgarmas usulining samaradorligi va ravshanligini ko'rsatadi.
Bugungi kunga kelib, invariantlarni qidirish uchun juda ko'p algoritmlar paydo bo'ldi, ularning aksariyati butun son usullariga asoslangan.
chiziqli dasturlash. Biroq, ularning murakkabligi tufayli ular keyingi rivojlanishga erisha olmadilar, chunki ularning fonida yanada samarali evristik usullar paydo bo'ldi.
Ularni qisqacha tavsiflab, shuni ta'kidlash mumkinki,
ular kengaytirilgan tarmoq insidans matritsasi satrlari va ustunlarini o'zgartirish uchun tsiklik protseduraning variantlari ekanligi. Jarayon matritsa qolguncha bajariladi, uning qatorlari o'zgarmaslar to'plamining yaratuvchi oilasini ifodalaydi.
Keyin har qanday invariantni generatsiya qiluvchi oiladan invariantlarning chiziqli birikmasi sifatida olish mumkin.
P-invariantlar bilan ishlashda
konservativ komponentlar ochiladi, lekin ular t-invariant bo'lsa, u holda
ular o'tish otishmalarining takrorlanuvchi ketma-ketligini belgilaydi (cheksiz izlar). Invariantlarni qidirish natijalari yanada ko'proq bo'lishi mumkin
yanada nozik xususiyatlarni o'rnatish uchun ishlatiladi (masalan, har xil turdagi adolat).
s = (1 1) bo'ladi. Ushbu yechim ikkita ketma-ketlikka mos keladi
t
1t2 va t2t1. Biroq, na biri, na boshqasi qabul qilinmaydi, chunki qo'shma korxona
dastlabki belgidan chiqa olmaydi (1000).

Matritsa tenglamasining yechimi mavjud bo'lgan Petri tarmog'i,
lekin p4 pozitsiyasiga etib bo'lmaydi
Yuqoridagi misollar matritsali yondashuvning jozibadorligini va cheklovlarini ko'rsatadi.