Алгоритмические сети и их применение. Михайлов В.В - 5 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

5
1. ÏÎÍßÒÈÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÕ ÑÅÒÅÉ
1.1. Îïðåäåëåíèå àëãîðèòìè÷åñêîé ñåòè
Àëãîðèòìè÷åñêàÿ ñåòü (ðèñ. 1, à) îïðåäåëÿåòñÿ êàê îðèåíòèðîâàííûé
ãèïåðãðàô áåç ïåòåëü ïðè âåðøèíàõ G(V,X), â êîòîðîì äóãè îáîçíà÷àþò
ìîäåëüíûå ïåðåìåííûå x
i
∈ X,
1,in=
, à âåðøèíû v
j
∈ V – ôóíêöèîíàëü-
íûå ñîîòíîøåíèÿ (îïåðàòîðû), f
j
∈ F,
1,jm
=
, ñâÿçûâàþùèå ìîäåëüíûå
çíà÷åíèÿ ïåðåìåííûõ íà èíòåðâàëå âðåìåíè, ñîîòâåòñòâóþùåì ∆t [3].
Ñòðóêòóðà ïåðåìåííûõ ñåòè X = X
âõ
∪ X
âûõ
∪ X
âí
, ãäå X
âõ
, X
âûõ
, X
âí
– ñîîòâåòñòâåííî âõîäíûå, âûõîäíûå è âíóòðåííèå ïåðåìåííûå, ïðè-
÷åì X
âõ
∩ X
âûõ
= ∅, X
âõ
∩ X
âí
= ∅, X
âûõ
∩ X
âí
= ∅. Ó÷èòûâàÿ, ÷òî âñå
âåðøèíû AC íàáëþäàåìû, ìîæíî çàäàòü X = X
âõ
∪ X
âû÷
, X
âû÷
– âû÷èñ-
ëÿåìûå ïåðåìåííûå AC, X
âû÷
= X
âûõ
∪ X
âí
.
Ôîðìàëüíî àëãîðèòìè÷åñêàÿ ñåòü (AC) ìîæåò áûòü îïðåäåëåíà ñëå-
äóþùèì îáðàçîì:
AC: = <P,Q,X,F,P→F,Q→X>,
ãäå P – ìíîæåñòâî âåðøèí ñåòè; Q – ìíîæåñòâî äóã ñåòè; X – ìíîæåñòâî
ïåðåìåííûõ, ïðè ýòîì X = ∪X
i
; X
i
– ìíîæåñòâî ïåðåìåííûõ i-é âåðøè-
íû; I – ìíîæåñòâî âñåõ èíäåêñîâ âåðøèí; F – ìíîæåñòâî îïåðàòîðîâ;
P→F – èçîìîðôíîå îòîáðàæåíèå P íà F, ò. å. èíäåêñ îïåðàòîðà ìîæíî
ñ÷èòàòü èíäåêñîì âåðøèíû; Q→X – îòîáðàæåíèå Q íà X.
Îïåðàòîð f
i
∈ F îïèñûâàåòñÿ êàê f
i
: = <X
iin
,f
i
,X
iout
>, ãäå X
iin
, X
iout
–
ìíîæåñòâî âõîäíûõ è âûõîäíûõ ïåðåìåííûõ îïåðàòîðà, f
i
– ñèìâîë
îïåðàöèè èëè ôóíêöèè. Äëÿ íåêîììóòàòèâíûõ îïåðàòîðîâ â X
iin
, X
iout
äîëæåí áûòü çàäàí ÷àñòè÷íûé ïîðÿäîê ýëåìåíòîâ. Òàê, äëÿ îïåðàöèè
âû÷èòàíèÿ â X
iin
íåîáõîäèìî îòìåòèòü óìåíüøàåìîå, ïîðÿäîê ñëåäîâà-
íèÿ îñòàëüíûõ ïåðåìåííûõ íåñóùåñòâåíåí.  îáùåì ñëó÷àå f
i
ìîæåò
áûòü èìåíåì íåêîòîðîãî ïðîãðàììíîãî ìîäóëÿ èëè äðóãîé AC, îïåðàòî-
ðû ìîãóò áûòü îïðåäåëåíû íàä äåéñòâèòåëüíûìè ÷èñëàìè, ëîãè÷åñêè-
ìè ïåðåìåííûìè, ñêàëÿðàìè, âåêòîðàìè, ìàòðèöàìè, èíôîðìàöèîííû-
ìè ñòðóêòóðàìè è äð.  ñîñòàâ îïåðàòîðîâ AC âêëþ÷àåòñÿ îïåðàòîð çà-
äåðæêè, êîòîðûé çàäàåò èñõîäíîå ñîñòîÿíèå ìîäåëèðóåìîìó ïðîöåññó è
îïèñûâàåò ïåðåõîä ìîäåëè íà ñëåäóþùèé øàã èëè îïðåäåëÿåò çàäåðæêó
ïîÿâëåíèÿ íåêîòîðîé ïåðåìåííîé â ÷àñòè AC. AC áóäåì íàçûâàòü êàíî-
íè÷åñêîé, åñëè âñå îïåðàòîðû çàäåðæêè îïðåäåëÿþò ðåêóððåíòíûå ñî-
îòíîøåíèÿ îòíîñèòåëüíî îäíîé è òîé æå âåëè÷èíû è ñ îäèíàêîâûì
øàãîì åå èçìåíåíèÿ. Èíûìè ñëîâàìè, â êàíîíè÷åñêîé AC âñå îïåðàòî-
ðû çàäåðæêè ñðàáàòûâàþò îäíîâðåìåííî è îáåñïå÷èâàþò ôîðìèðîâàíèå
îäíîãî âíåøíåãî öèêëà ñ÷åòà îïåðàòîðîâ ñåòè.

Страницы