Екі негізгі бағытталған граф. Петри желісінің сызба көрсетіліуі. Петри желісін таңбалау. Петри желісі

Loading...


бет1/2
Дата28.03.2020
өлшемі0.66 Mb.
  1   2
Екі негізгі бағытталған граф. Петри желісі. Петри желісінің сызба көрсетіліуі. Петри желісін таңбалау.

Петри желісі - динамикалық дискретті жүйені модельдеуге арналған математикалық құрылғы. Ең бірінші рет 1962 жылы Карл Петри іске асырды.

1-сурет. Петри желісінің мысалы. Ақ дөңгелек – орны, сызық – орын ауыстыру, қара дөңгелек – таңбалар.

Петри желісі – екі жақты бағытталған мультиграф, ол екі типті шыңнан тұрады: бір-бірімен доға арқылы байланысқан орны мен орын ауыстырулар. Бір типтің шыңы тікелей байланысқа түсе алмайды, орындарда таңбалар(маркерлар) болады, олар желі бойынша қозғалысты еркін жасайды.

Таңба кіріс орнынан шығыс орынға бағытталған кезде, орын ауыстыру үрдісі жүреді, оны оқиға деп атайды. Оқиға тез немесе әртүрлі уақытқа байланысты орындалады, ол шарттардың орындалуына байланысты.

Сонымен Петри желесі дегеніміз мультиграф, себебі ол графтың бір шыңынан екінші шыңына дейін еселі доғаның болуына жол береді. Доғаның белгілі бір бағыты болғандықтан, ол бағытталған мультиграф. Граф шыңдарын екі көпмүшеге(орны мен орын ауыстыру) бөлуге болады, осылайша бір көпмүше элементінен әр доға екінші көпмүше элементіне бағытталады. Оны екі жақты бағытталған мультиграф(двудольный ориентированный мультиграф) деп атайды.

Петри желісі параллель өзара байланысқан компоненттері бар жүйе үшін жобаланған еді, оны Карл Адам Петри өзінің «Связь автоматов» атты еңбегінде жариялап, есептеуіш жүйедегі асинхронды компоненттерінің байланысы жайлы негізгі түсініктерін енгізді.

Петри желісінің динамикасы

Петри желісінің қызмет ету үрдісін жеткілікті маркирлеу графында көруге болады. Маркирлеу – маркерлерді(таңбаларды) орны бойынша орналастыру. Желінің жағдайы оның таңбалануы арқылы анықталады – орын бойынша фишкаларды орналастыру.Граф шыңы - Петри желісінің жеткілікті маркирленуі, доға – іске асатын орын ауыстыру белігісімен белгіленіп тұр. Доға әр қимылға түсетін орын ауыстыру үшін құрылады. Қимылға түспейтін орын ауыстыру немесе графта бар таңбалар пайда болса, оны құрастыру тоқтайды. Жеткілікті маркирлеу графы автомат болып табылады.



Петри желісінің кейбір түрлері:

  • Уақытша Петри желісі – іске асу(тоқтату) ұзақтығымен анықталатын орын ауыстыру.

  • Стохастикалық Петри желісі – тоқтатулар кездейсоқ өлшем ретінде болады.

  • Функционалды Петри желісі - тоқтатулар кейбір аргументтердің функциясы ретінде анықталады, мысалы, қайсыбір орындағы таңба саны, кейбір орын ауыстырулардың жағдайы.

  • Түрлі-түсті Петри желісі – түс арқылы белгіленген таңбалар әртүрлі типті болуы мүмкін. Таңба типі аргумент ретінде қолданылуы мүмкін.

  • Ингибиторлы Петри желісі - ингибиторлы доғаның орын ауыстыруымен байланысқан кіріс орында таңба болса, орын ауыстырудың іске асуына тыйым салатын ингибиторлы доға.

  • Иерархиялық желі – мүмкін осындай иерархиялық желілер енгізілген тез әрекет етпейтін орын ауыстырулардан тұрады. Мұндай орын ауыстырудың іске асуы толық өмірлік циклдың іске асқанын сипаттайды.

  • WF-желі. WF-желі – жұмыс ағымының желісі. Оны құрастырған Вил ван дер Аальст(Work –жұмыс, Flow- ағым). PN = (P,T,F) Петри желісі жұмыс ағымының желісі деп аталады, егер: 1) і-ға кіретін орын ауыстырулары жоқ тек бір і орны бар; 2) 0-ға кіретін орын ауыстырулары жоқ тек бір соңғы орны бар; 3) берілген желінің әр түйіні і-дан 0-ге дейінгі жолда орналасқан. WF-желілер жұмыс ағымындағы графтардың ақауларын тексеру үшін пайдаланады.

Ақаудың жоқ болуы немесе дұрыс аяқталу келесі талаптарға сай болуы керек:

  1. 0 соңғы орны і орнынан кез-келген орын ауыстырудың реттілігі кезінде қол жетімді;

  2. WF-желілер үрдіске қатыспайтын артық орыннан тұрмайды.

  3. Соңғы орынға жеткен кезде аралық орындарда фишкалар қалмауы тиіс.

Ақаудың болмауы Петри желісінің екі жақсы қасиетіне сәйкес келеді: жандылығы және шектеулілігі.

Петри желісінің сараптамасы

2-сурет. Петри желісіндегі орын ауыстыру мысалы.

Петри желісінің негізгі қасиеттері:


  • шектеулілік – кез-келген желі орнында таңба саны белгілі К мәнінен артық бола алмайды;

  • қауіпсіздік – шектеуліліктің жеке жағдайы, K=1;

  • сақтандылық – қорды жүктеу тұрақтылығы –тұрақты . Мұндағы і орындағы таңба саны,  салмақты коэффициент;

  • қол жетімділік – желінің берліген жағдайдан басқаға орын ауыстыру мүмкіндігі;

  • жандылығы – жобаланатын нысан қызмет еткен кезде кез-келген орын ауыстырудың іске асу мүмкіндігі.

Аталған қасиеттерді зерттеу негізіне жетімділік сараптамасы кіреді. Петри желісінің қасиетін сараптау әдісі жетімділік графын пайдалану, желі жағдайының теңдеуін шешу, орын мен орын ауыстырулардың сызықты инварианттылығын есептеу болып табылады. Сонымен қатар, қосымша әдістер де пайдаланылады: редукция – Петри желісін қасиеттерін сақтай отырып көлемін кішірейту және декомпозиция – бастапқы желіні желі астына бөлшектеу.

1974 жылы Тилак Аджервала Петридің ингибиторлы желісі әмбебап алгоритмдік жүйе екенін көрсетті. Петридің шексіз желісі есептеуіш торды верификациялау үшін енгізілді және Петри желісінің қасиетін күнделікті құрылым(сызықты, ағаш типті, шаршы, үшбұрышты, алты бұрышты, гиперкуб) үшін анықтауға мүмкіндік берді.

Петри желісін анықтау мысалдары

Петри желісі  төрттігімен анықталады, мұндағы Р және Т – орын мен орын ауыстырулардың қорытынды көпмүшесі. І және О – кіріс және шығыс функциялардың көпмүшесі. Орын дөңгелек арқылы белгіленсе, ал орын ауыстыру қалың сызықпен белгіленеді; І функциясына орыннан орын ауыстыруға , ал О функциясына орын ауыстырудан орынға бағытталған доғалар сәйкес келеді.

Петри желісінде екі типті нысан болады: динамикалық – орынның ішінде таңбамен белгіленеді және статикалық – Петри желісінің шыңдары сәйкес келеді.

3-сурет. Петри желісінің мысалы






Достарыңызбен бөлісу:
  1   2
Loading...


©melimde.com 2020
әкімшілігінің қараңыз

    Басты бет
рсетілетін ызмет
Жалпы ережелер
ызмет стандарты
дістемелік кешені
бекіту туралы
туралы хабарландыру
біліктілік талаптары
кіміні аппараты
Конкурс туралы
жалпы біліктілік
ойылатын жалпы
мемлекеттік кімшілік
жалпы конкурс
білім беретін
Барлы конкурс
республикасы білім
ызмет регламенті
бойынша жиынты
ткізу туралы
конкурс атысушыларына
біліктілік талаптар
атысушыларына арнал
Республикасы кіметіні
идаларын бекіту
облысы кімдігіні
мемлекеттік ызмет
рсетілетін ызметтер
стандарттарын бекіту
Конкурс ткізу
дебиеті маманды
мемлекеттік мекемесі
Мектепке дейінгі
дістемелік сыныстар
дістемелік материалдар
ауданы кіміні
конкурс туралы
жалпы білім
рметті студент
облысы бойынша
мектепке дейінгі
мыссыз азаматтар
Мемлекеттік кірістер
білім беруді
дарламасыны титулды
Конкурс жариялайды
дістемелік кешен
мелетке толма
ызметтер стандарттарын
разрядты спортшы
аласы кіміні
директоры бдиев

Loading...