OK-metodichka-2010-part2 (С.А. Ложкин - Лекции по основам кибернетики (2009)), страница 6

. . , qki âûïîëíåíî (2.2). Òîãäà â âåðøèíå v ðåàëèçóåòñÿ ôîðìóëà F = Fvâèäà (2.1), êîòîðàÿ èìååò ãëóáèíó q . Ïðè ýòîì ñ÷èòàåòñÿ,÷òî â âåðøèíå v ÑÔÝ Σf (x1 , . . . , xn ),åñëè ÔÀË f ðåàëèçóåòñÿ ôîðìóëîé Fv , è ÷òî ÑÔÝ ΣF, F = (f1 , . . . , fm ), èëèz1 = f1 , . . . , zm = fm , åñëèfj , j = 1, . . . , m, ÔÀË, ðåàëèçîâàííàÿ â òîé âûõîäíîéâåðøèíå ÑÔÝ Σ, êîòîðîé ïðèïèñàíà ÁÏ zj .ðåàëèçóåòñÿ ÔÀËëèçóåò ñèñòåìó ÔÀËñèñòåìó áóëåâûõ óðàâíåíèéðåàðåàëèçóåòÇàìåòèì, ÷òî êâàçèäåðåâî, êîòîðîå ñîîòâåòñòâóåò ôîðìóëå F, ðåàëèçóþùåé ÔÀË f , à òàêæå ëþáàÿ ÑÔÝ, ïîëó÷åííàÿ èç íåãî îòîæäåñòâëåíèåì èçîìîðôíûõ êâàçèïîääåðåâüåâ, ðåàëèçóåò è ôîðìóëó F, è ÔÀË f .

Òàê, ÑÔÝ íà ðèñ.{0,2,3}4.2 ðåàëèçóåò ôîðìóëó (2.3) è ÔÀË s3(x1 , x2 , x3 ), èëè{0,2,3}óðàâíåíèå z1 = s3(x1 , x2 , x3 ). ñîîòâåòñòâèè ñ Ÿ1 äâå ÑÔÝ ñ÷èòàþòñÿ èçîìîðôíûìè,36Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìåñëè îíè èçîìîðôíû êàê ïîìå÷åííûå ãðàôû, è ýêâèâàëåíòíûìè, åñëè îíè ðåàëèçóþò ðàâíûå ñèñòåìû ÔÀË. Çàìåòèì,÷òî ÑÔÝ âñåãäà ýêâèâàëåíòíà ñèñòåìå ôîðìóë, ðåàëèçóåìûõåþ íà ñâîèõ âûõîäàõ.

Çàìåòèì òàêæå, ÷òî èçìåíåíèå íóìåðàöèè äóã, âõîäÿùèõ â òàêóþ âåðøèíó v ÑÔÝ Σ, êîòîðîéñîïîñòàâëåí ÔÝ Ei ñ ñèììåòðè÷åñêîé ÔÀË ϕi , íå èçìåíÿåò ÔÀË, ðåàëèçóåìóþ â âåðøèíå v , à çíà÷èò, íå âëèÿåò íàôóíêöèîíèðîâàíèå Σ. Ñõåìû, ïîëó÷àþùèåñÿ äðóã èç äðóãàâ ðåçóëüòàòå óêàçàííûõ ïðåîáðàçîâàíèé, íàçûâàþòñÿ, à íîìåðà äóã, âõîäÿùèõ â âåðøèíó v ñ ñèììåòðè÷åñêîé ÔÀË, êàê ïðàâèëî, íå óêàçûâàþòñÿ. Ëåãêî âèäåòü, ÷òî â ñîîòâåòñòâóþùèõ äðóã äðóãó âåðøèíàõ èçîìîðôíûõ (êâàçèèçîìîðôíûõ) ÑÔÝ ðåàëèçóþòñÿ îäèíàêîâûå (ñîîòâåòñòâåííî ïîäîáíûå) ôîðìóëû, à çíà÷èò, è îäèíàêîâûåÔÀË. Ñëåäîâàòåëüíî, äâå èçîìîðôíûå (êâàçèèçîìîðôíûå)ÑÔÝ ýêâèâàëåíòíû, òî åñòü äëÿ ÑÔÝ ñïðàâåäëèâî íåðàâåíñòâî (1.7).Âåðøèíà ÑÔÝ íàçûâàåòñÿ, åñëè îíà ÿâëÿåòñÿñòîêîì, íî íå ÿâëÿåòñÿ âûõîäîì ñõåìû.

Ñõåìà íàçûâàåòñÿ, åñëè â íåé íåò âèñÿ÷èõ âåðøèí. Çàìåòèì, ÷òîñèñòåìà ôîðìóë ÿâëÿåòñÿ ïðèâåäåííîé ÑÔÝ, è ÷òî èç ëþáîé ÑÔÝ ìîæíî ïîëó÷èòü ýêâèâàëåíòíóþ åé ïðèâåäåííóþÑÔÝ ñ ïîìîùüþ îïåðàöèè. Çàìåòèì òàêæå, ÷òî ïðèâåäåííûå ÑÔÝ, è òîëüêî îíè, ïîëó÷àþòñÿ èç ñèñòåì êâàçèäåðåâüåâ â ðåçóëüòàòå îòîæäåñòâëåíèÿíåêîòîðûõ èçîìîðôíûõ êâàçèïîääåðåâüåâ, è ÷òî â ïðèâåäåííûõ ÑÔÝ âñå âåðøèíû ëåæàò íà öåïÿõ, èäóùèõ îò âõîäîâ ñõåìû ê åå âûõîäàì.Òàêæå êàê è äëÿ ôîðìóë, äëÿ êàæäîé ÑÔÝ Σ, Σ ∈ UCÁ,îïðåäåëèì ñëåäóþùèå ïàðàìåòðû (ôóíêöèîíàëû ñëîæíîñòè):êâàçè-èçîìîðôíûìèâèñÿ÷åéïðèâåäåííîéóäàëåíèÿ âèñÿ÷èõ âåðøèíñëîæíîñòü Σ, òî åñòü ÷èñëî âñåõ åå ÔÝ;2. D (Σ) ãëóáèíà Σ, òî åñòü ìàêñèìàëüíàÿ ãëóáèíà åå1.

L (Σ) Ÿ4.37ÑÔÝ, îöåíêà ÷èñëà ôîðìóë è ñõåìâåðøèí.3. R (Σ) äîâ.ðàíã Σ, òî åñòü ÷èñëî äóã,èñõîäÿùèõ èç åå âõî-Ëåììà 2.1 îáîáùàåòñÿ äëÿ ÑÔÝ ñëåäóþùèì îáðàçîì.Äëÿ ïðèâåäåííîé ÑÔÝ Σ, Σâûõîäîì, âûïîëíÿþòñÿ íåðàâåíñòâàËåììà 4.1.∈ UC, ñ îäíèìR (Σ) 6 L&,∨ (Σ) + 1 6 L (Σ) + 1 6 2D(Σ) ,(4.1)ãäå L&,∨ ÷èñëî ÔÝ & è ∨ â Σ.Ñ ñîäåðæàòåëüíîé òî÷êè çðåíèÿ ðàçëè÷íûå ôóíêöèîíàëû ñëîæíîñòè îòðàæàþò ðàçëè÷íûå ïàðàìåòðû ìîäåëèðóåìûõ ñõåì èëè ïðîãðàìì. Òàê, íàïðèìåð, ñëîæíîñòü ìîæåò õàðàêòåðèçîâàòü ñòîèìîñòü, ðàçìåðû èëè ïîòðåáëÿåìóþ ìîùíîñòü ÑÁÈÑ, à òàêæå âðåìÿ âûïîëíåíèÿ ïðîãðàììû íà îäíîì ïðîöåññîðå.

Ïðè ýòîì çàäåðæêà ñõåìû õàðàêòåðèçóåò âðåìÿ ñðàáàòûâàíèÿ ÑÁÈÑ èëè âðåìÿ âûïîëíåíèÿïðîãðàììû íà ïàðàëëåëüíûõ ïðîöåññîðàõ. Ðàíã ñõåìû îòðàæàåò ÷èñëî îáðàùåíèé ïðîãðàììû ê ïàìÿòè, â êîòîðîéõðàíÿòñÿ çíà÷åíèÿ âõîäíûõ ÁÏ è ò.ï.ΦÎáîçíà÷èì ÷åðåç UΦÁ (L, n) è UÁ [D, n] ìíîæåñòâî ôîðìóëF = F (x1 , . . . , xn ) íàä áàçèñîì Á, äëÿ êîòîðûõ L (F) 6 L èD (F) 6 D, ïðè÷åì èíäåêñ Á0 áóäåì, êàê îáû÷íî, îïóñêàòü.Çàìåòèì, ÷òî èç íåðàâåíñòâà (2.4) âûòåêàåò âêëþ÷åíèåUΦ [D, n] ⊆ UΦ 2D − 1, n .(4.2)Äëÿ ëþáûõ íàòóðàëüíûõ n, L, D âûïîëíÿþòñÿ íåðàâåíñòâàËåììà 4.2.

ΦU (L, n) 6 (10n)L+1 , ΦU (L, n) 6 (8n)L+1 , ΦU [D, n] 6 (8n)2D .(4.3)(4.4)(4.5)38Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìÄîêàçàòåëüñòâî. Îöåíèì ñâåðõó ÷èñëî ïîïàðíî íå èçîìîðô-íûõ (ïîïàðíî íå êâàçèèçîìîðôíûõ) ôîðìóë âî ìíîæåñòâåU Φ (L, n). Äëÿ òîãî, ÷òîáû çàäàòü ñ òî÷íîñòüþ äî èçîìîðôèçìà óïîðÿäî÷åííîå äåðåâî D, ñîîòâåòñòâóþùåå ôîðìóëåF, F ∈ UΦ (L, n), äîñòàòî÷íî:1. âûáðàòü óïîðÿäî÷åííîå äâîè÷íîå êîðíåâîå äåðåâî D0 ñq, q 6 L, íåëèñòîâûìè âåðøèíàìè, â êîòîðîì âåðøèíûñ ïîëóñòåïåíüþ çàõîäà 2 ïîìå÷åíû ÔÑ &, ∨;2.

êàæäûé èñòîê D0 ïîìåòèòü îäíîé èç ÁÏ x1 , . . . , xn , àâåðøèíû ñ ïîëóñòåïåíüþ çàõîäà 1 ÔÑ ¬.Ïðîíóìåðóåì ìíîæåñòâî íåëèñòîâûõ âåðøèí äåðåâà D0 ÷èñëàìè 1, 2, . . . , q â îáðàòíîì îòíîñèòåëüíî åñòåñòâåííîé íóìåðàöèè τ (ñì. Ÿ1) ïîðÿäêå è ñîïîñòàâèì êàæäîé òàêîé âåðøèíå v ñ ïîëóñòåïåíüþ çàõîäà d, d ∈ [1, 2] íàáîð α, α ∈ B d ,ãäå α = (α1 , . . . , αd ) è αj = 1 òîãäà è òîëüêî òîãäà, êîãäàäóãà ñ íîìåðîì j , âõîäÿùàÿ â v , íà÷èíàåòñÿ ñ ëèñòà äåðåâà D0 . Çàìåòèì, ÷òî íàáîð γ = (γ1 , .

. . , γL ), ãäå γi íàáîð, ñîïîñòàâëåííûé âåðøèíå ñ íîìåðîì i, åñëè 1 6 i 6 q ,è ïðîèçâîëüíûé íàáîð èç îáúåäèíåíèÿ B 1 ∪ B 2 â ñëó÷àåi > q , à òàêæå íàáîð ÔÑ & è ∨, ïðèïèñàííûõ òåì âåðøèíàìvi , 1 6 i 6 L, äëÿ êîòîðûõ γi ∈ B 2 , îäíîçíà÷íî îïðåäåëÿåòäåðåâî D0 ñ òî÷íîñòüþ äî èçîìîðôèçìà.Ñëåäîâàòåëüíî, ÷èñëî óïîðÿäî÷åííûõ äåðåâüåâ D0 ðàññìàòðèâàåìîãî âèäà íå áîëüøå, ÷åì 10L , à ÷èñëî ïîëó÷àåìûõ èç íåãî äåðåâüåâ D íå áîëüøå, ÷åì nL+1 , òàê êàê â ñèëóëåììû 2.1R (F) 6 L + 1.Ïåðåìíîæàÿ óêàçàííûå ÷èñëà, ïîëó÷àåì îöåíêó (4.3).

Îöåíêà (4.4) äîêàçûâàåòñÿ àíàëîãè÷íî ñ ó÷åòîì òîãî, ÷òî ïðè ñíÿòèè íóìåðàöèè ñ äóã äåðåâà D0 , òî åñòü ïðè ðàññìîòðåíèèôîðìóë ñ òî÷íîñòüþ äî êâàçèèçîìîðôèçìà, äâîè÷íûå íàáîðû äëèíû 2, ñîïîñòàâëåííûå åãî âåðøèíàì , ìîæíî âûáè-Ÿ4.ÑÔÝ, îöåíêà ÷èñëà ôîðìóë è ñõåì39ðàòü èç ìíîæåñòâà {(00) , (01) , (11)} è ïîýòîìó ÷èñëî íåóïîðÿäî÷åííûõ äåðåâüåâ D0 ðàññìàòðèâàåìîãî âèäà íå áîëüøå,÷åì 8L .Íåðàâåíñòâî (4.5) âûòåêàåò èç (4.4) è (4.2).Ëåììà äîêàçàíà.Çàìå÷àíèå. ×èñëî ïîïàðíî íå êâàçèèçîìîðôíûõ ôîðìóë âáàçèñå {&, ∨} îò ÁÏ X (n) ñëîæíîñòè íå áîëüøå, ÷åì L, íåïðåâîñõîäèò (6n)L+1 .Ëåììà 4.3.íåðàâåíñòâîÄëÿ ëþáûõ íàòóðàëüíûõ n è L âûïîëíÿåòñÿ CU (L, n) 6 (8 (L + n))L+1 .(4.6)Äîêàçàòåëüñòâî.

Çàìåòèì, ÷òî äëÿ òîãî, ÷òîáû çàäàòü ÑÔÝΣ, Σ ∈ UC (L, n), ñ òî÷íîñòüþ äî êâàçèèçîìîðôèçìà äîñòàòî÷íî:1. âûáðàòü å¼ îñòîâíîå íåóïîðÿäî÷åííîå íàääåðåâî D0 cq, q 6 L, íåëèñòîâûìè âåðøèíàìè, êîòîðûå ïîìå÷åíûÔÑ áàçèñà Á0 ;2. ïðèñîåäèíèòü êàæäûé ëèñò D0 ëèáî ê îäíîìó èç n âõîäîâ Σ, ëèáî ê îäíîé èç íåëèñòîâûõ âåðøèí D0 , îòëè÷íîé îò êîðíÿ.Îöåíêà (4.6) ïîëó÷àåòñÿ èç ïðèâåäåííîé â ëåììå 4.2 îöåíêè÷èñëà äåðåâüåâ D0 è îöåíêè ÷èñëà ñïîñîáîâ ïðèñîåäèíåíèÿêàæäîãî ëèñòà D0 ïóòåì èõ ïåðåìíîæåíèÿ.Ëåììà äîêàçàíà.40Ÿ5Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìÝêâèâàëåíòíûå ïðåîáðàçîâàíèÿ ñõåì èç ôóíêöèîíàëüíûõ ýëåìåíòîâ è ìîäåëèðîâàíèå ñ èõïîìîùüþ ôîðìóëüíûõ ïðåîáðàçîâàíèé.

Ìîäåëèðîâàíèå ýêâèâàëåíòíûõ ïðåîáðàçîâàíèéôîðìóë è ñõåì â ðàçëè÷íûõ áàçèñàõ, òåîðåìà ïåðåõîäàÐàñïðîñòðàíèì ââåäåííûå ⠟3 ïîíÿòèÿ è îáîçíà÷åíèÿ íàïðîèçâîëüíûé êëàññ ñõåì U.  ñîîòâåòñòâèè ñ îïðåäåëåíèÿìè èç Ÿ3 ýêâèâàëåíòíîñòü ñõåì Σ0 è Σ00 èç U èìååò ìåñòîòîãäà è òîëüêî òîãäà, êîãäà Σ0 è Σ00 ðåàëèçóþò ðàâíûå ñèñòåìû (ìàòðèöû) ÔÀË. Ïðè ýòîì, îáû÷íî, ïðåäïîëàãàåòñÿ,÷òî ñîîòâåòñòâóþùèå äðóã äðóãó ïîëþñà (âûõîäû, âõîäû) âΣ0 è Σ00 èìåþò îäèíàêîâûå ïîìåòêè, à ýêâèâàëåíòíîñòü Σ0 èΣ00 çàïèñûâàåòñÿ â âèäå òîæäåñòâàt : Σ0 ∼ Σ00 .Äëÿ ñõåì èç U, êàê è äëÿ ôîðìóë, îïðåäåëÿåòñÿ ðÿä¾ïðîñòåéøèõ¿ ïðåîáðàçîâàíèé, ñîõðàíÿþùèõ ýêâèâàëåíòíîñòüñõåì, êîòîðûå íàçûâàþòñÿ.

Òîæäåñòâîïîäñòàíîâêàìèb0 ∼ Σb 00 ,bt: Σêîòîðîå ïîëó÷àåòñÿ â ðåçóëüòàòå ïðèìåíåíèÿ îäíîé è òîéæå ïîäñòàíîâêè ê îáåèì ÷àñòÿì òîæäåñòâà t : Σ0 ∼ Σ00 , íàçûâàåòñÿt. Ñõåìà Σ0 íàçûâàåòñÿΣ, åñëèV Σ0 ⊆ V (Σ) ,E Σ0 ⊆ E (Σ)ïîäñòàíîâêîé òîæäåñòâàïîäñõåìîé ñõåìûè ëþáàÿ âåðøèíà v , v ∈ V (Σ0 ), êîòîðàÿ ëèáî îòíîñèòñÿ êìíîæåñòâó âõîäîâ (âûõîäîâ) Σ, ëèáî ñëóæèò êîíå÷íîé (ñîîòâåòñòâåííî íà÷àëüíîé) âåðøèíîé íåêîòîðîãî ðåáðà èç E(Σ)\E(Σ0 ), ÿâëÿåòñÿ âõîäîì (ñîîòâåòñòâåííî âûõîäîì) Σ0 .Ÿ5.Ïðåîáðàçîâàíèÿ íà îñíîâå òîæäåñòâ41Áóäåì ñ÷èòàòü, ÷òî äëÿ ñõåì èç U, êàê è äëÿ ôîðìóë,èìååò ìåñòî ïðèíöèï ýêâèâàëåíòíîé çàìåíû, òî åñòü çàìåb 0 ñõåìû Σ ýêâèâàëåíòíîé åé ñõåìîé Σb 00 ìûíÿÿ ïîäñõåìó Σe , êîòîðàÿ ýêâèâàëåíòíà ñõåìå Σ.

Ïðè ýòîìïîëó÷àåì ñõåìó Σâñå ââåäåííûå ⠟3 äëÿ ñëó÷àÿ ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé ôîðìóë ïîíÿòèÿ (îäíîêðàòíàÿ è êðàòíàÿ âûâîäèìîñòü,ïîëíîòà ñèñòåìû òîæäåñòâ è äð.), à òàêæå ñâÿçàííûå ñ íèìè îáîçíà÷åíèÿ ïåðåíîñÿòñÿ íà ñëó÷àé ÝÏ ñõåì èç U áåçèçìåíåíèé. Çàìåòèì, ÷òî âîïðîñ î ñóùåñòâîâàíèè êîíå÷íîéïîëíîé ñèñòåìû òîæäåñòâ (ÊÏÑÒ) ÿâëÿåòñÿ îäíèì èç îñíîâíûõ âîïðîñîâ, ñâÿçàííûõ ñ èçó÷åíèåì ÝÏ ñõåì èç çàäàííîãîêëàññà U.Ðàññìîòðèì ýòè âîïðîñû íà ïðèìåðå ÝÏ ÑÔÝ.

Ìû áóäåìèñïîëüçîâàòü âñå ââåäåííûå âûøå îáùèå ïîíÿòèÿ è îïðåäåëåíèÿ, êàñàþùèåñÿ ÝÏ ñõåì, ñ÷èòàÿ ïîäñòàíîâêîé ÑÔÝ ïåðåèìåíîâàíèå (ñ âîçìîæíûì îòîæäåñòâëåíèåì) åå âõîäíûõÁÏ è ïåðåèìåíîâàíèå (ñ âîçìîæíûì äóáëèðîâàíèåì è ñíÿòèåì1 ) åå âûõîäíûõ ÁÏ.Íàïîìíèì, ÷òî ôîðìóëû ïðåäñòàâëÿþò ñîáîé ÷àñòíûéñëó÷àé ÑÔÝ, è äëÿ îïðåäåëåííîñòè áóäåì ñ÷èòàòü, ÷òî ëþáàÿ ôîðìóëà F èç UΦÁ ÿâëÿåòñÿ ôîðìóëîé-ñëîâîì (ñì. Ÿ2), àñîîòâåòñòâóþùóþ åé ôîðìóëó-ãðàô, ò. å. êâàçèäåðåâî (ñì. Ÿ2),áóäåì îáîçíà÷àòü ÷åðåç F.