Pdf-xchange 0 Examples

 

---

27 
 
1.2-rasm.
 1.1-rasmda tasvirlangan hisoblash graflariga ekvivalent Petri 
tarmoqlari
 
Yuqorida ifodalangan usullar asosida qurilgan 1.1-rasmdagi hisoblashlar 
grafi uchun 1.2-rasmda Petri tarmoqlari tasvirlangan.
 
Markerlangan graflarning barcha 
v
j
va 
v
k
tugunlada
T
j,k
= W
j,k
uchun 
hisoblash graflarni modellashtirishining mumkinligini osongina ko`rsatish 
mumkin. Biroq, hisoblash graflari 
T
j,k
 > W
j,k 
holatli vaziyatlarni modellashtirish 
imkoniyatiga ko`ra markerlangan graflardan quvvatliroq vosita hisoblanadi. 
 
Boshqa tomondan esa, hisoblash graflari va chekli avtomatlar 
markerlangan graflar hamda chekli avtomatlar kabi solishtirilmaydi. Hisoblash 
graflari qaror qabul qilish yoki shartli bajarishni modellashtira olmaydi, bu 
cheklanish markerlangan graflar uchun ham o`rinli. Shunday qilib, model 
iyerarxiyasi 1.3-rasmda ko`rsatilgan ko`rinishga ega bo`ladi.
 
 
 
1.3- rasm. 
Modellar ierarxiyasiga hisoblash graflarning qo`shilishi
 

---

28 
Karp va Miller hisoblash graflarini, ayniqsa, faollik va xavfsizlik 
masalalarida atroflicha tadqiq qilishgan. Haqiqatda esa ularni hisoblash 
graflarining tugallanganlik shartlar(ya’ni nofaollik shartlari)ni ta’minlash va 
aniqlash masalasi qiziqtirgan. Ma’lumotlar navbati yoylar (vaziyatlar) kabi 
ifodalangan holatda Karp va Miller tomonidan o`tkazilgan cheklanishlar 
tadqiqotlari navbatni maksimal uzunligini aniqlashga yo`naltirilgan edi. 
Belgilashlardagi va maqsaddagi bunday farqlar hamda hisoblash graflari va 
markerlangan graflar orasidagi modellarni aniqlashdagi tafovutlar – hisoblash 
graflarining markerlangan graflar bo`yicha Karp va Miller natijalari va 
algoritmlari biror kishining urunishlari yaqinlashmaganligining sababi bo`lib 
xizmat qiladi.