С.А. Ложкин - Лекции по основам кибернетики (2010) (1132804), страница 11
Текст из файла (страница 11)
Ëåììà Øåííîíà79b0 è Σb 00 ïîëó÷àþòñÿ èç ñõåì Σ0 è Σ00 ñíÿòèåì âûõîäîâñõåìû Σè îòîæäåñòâëåíèåì âõîäîâ ñîîòâåòñòâåííî.Äëÿ ñóïåðïîçèöèè ñõåì âèäà Σ = Σ00 (Σ0 ) õàðàêòåðíî, êàêïðàâèëî, òî, ÷òî ñõåìà Σ ðåàëèçóåò ôóíêöèè, ïîëó÷àþùèåñÿ â ðåçóëüòàòå ñîîòâåòñòâóþùåé ïîäñòàíîâêè (âñåõ èëè ÷àñòè) ôóíêöèé, ðåàëèçîâàííûõ ñõåìîé Σ0 âìåñòî (âñåõ èëè÷àñòè) âõîäíûõ ïåðåìåííûõ ñõåìû Σ00 .  ñëó÷àå ñòûêîâêè, íàïðèìåð, ýòî îçíà÷àåò, ÷òî ñõåìà Σ ðåàëèçóåò íàáîðôóíêöèé âèäà F00 (F0 ), ãäå F00 è F0 íàáîðû ôóíêöèé, ðåàëèçîâàííûå ñõåìàìè Σ00 è Σ0 ñîîòâåòñòâåííî.
ÑóïåðïîçèöèÿΣ = Σ00 (Σ0 ) ñ÷èòàåòñÿ, åñëè ñõåìà Σ îáëàäàåòóêàçàííûì ñâîéñòâîì, è, åñëè, êðîìå òîãî, â ëþáîé âåðøèíå Σ, êîòîðàÿ ñîîòâåòñòâóåò âûõîäíîé âåðøèíå Σ0 ,ðåàëèçóåòñÿ òà æå ñàìàÿ ôóíêöèÿ, ÷òî è â Σ0 . Çàìåòèì, ÷òîïðàâèëüíàÿ ñóïåðïîçèöèÿ âèäà Σ00 (Σ0 ) àâòîìàòè÷åñêè ÿâëÿåòñÿ êîððåêòíîé, åñëè êðàòíîñòü ëþáîé âûõîäíîé âåðøèíûΣ0 áîëüøå ÷èñëà ïðèñîåäèíÿåìûõ ê íåé âõîäîâ Σ00 . Çàìåòèìòàêæå, ÷òî ñ ñîäåðæàòåëüíîé òî÷êè çðåíèÿ êîððåêòíîñòü ñóïåðïîçèöèè âèäà Σ00 (Σ0 ) ïîçâîëÿåò îäíîâðåìåííî èñïîëüçîâàòü âûõîäû Σ0 â äðóãèõ ñóïåðïîçèöèÿõ.Çàìåòèì òàêæå, ÷òî ëþáàÿ ÑÔÝ ìîæåò áûòü ïîëó÷åíà âðåçóëüòàòå ìíîãîêðàòíîãî ïðèìåíåíèÿ îïåðàöèè ñóïåðïîçèöèè, íà êàæäîì øàãå êîòîðîé ïðîèñõîäèò äóáëèðîâàíèå âûõîäà èëè ïðèñîåäèíåíèå îäíîãî ÔÝ, ê ÑÔÝ, ïåðâîíà÷àëüíîñîñòîÿùåé èç òîæäåñòâåííûõ âåðøèí.Íà ðèñ.
9.1a ïîêàçàíà ÑÔÝ Σ⊕2 , èìåþùàÿ ñëîæíîñòü 4 èðåàëèçóþùàÿ ÔÀË x1 ⊕ x2 , à íà ðèñ. 9.1b ÑÔÝ Σ⊕q , q > 3,êîòîðàÿ ÿâëÿåòñÿ ðåçóëüòàòîì ¾ïîñëåäîâàòåëüíîé¿ ñóïåðïîçèöèè (q − 1) ñõåì Σ⊕2 è ðåàëèçóåò ÔÀË `q (x1 , . . . , xq ) ñîñëîæíîñòüþ 4q − 4.Ðàññìîòðèì òåïåðü âîïðîñû, ñâÿçàííûå ñ íàõîæäåíèåìôóíêöèîíèðîâàíèÿ äëÿ ñóïåðïîçèöèé ñåòåé èëè ÊÑ.
Èç ñîîáðàæåíèé óäîáñòâà áóäåì äîïóñêàòü íàëè÷èå â ÊÑ âåíòèëåé è íåîðèåíòèðîâàííûõ ðåáåð áåç ïîìåòîê, êîòîðûå ïðî-ïðàâèëüíîéêîððåêòíîé80Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìx/1x2•/•/x1x2•&••w•'¬Σ⊕2x3--∨••z1 &•Σ⊕22222...xq,,,,•Σ⊕2z1a)b)Ðèñ. 9.1: ïðèìåð ñóïåðïîçèöèè ÑÔÝâîäÿò ïðè ëþáûõ çíà÷åíèÿõ óïðàâëÿþùèõ âõîäíûõ ÁÏ èíàçûâàþòñÿ. Ýòî ïîçâîëÿåò ñ÷èòàòü, ÷òî ñåòèÿâëÿþòñÿ ÷àñòíûì ñëó÷àåì ÊÑ è ðåàëèçóþò ñâîè ìàòðèöûäîñòèæèìîñòè, ñîñòîÿùèå èç êîíñòàíòíûõ ÔÀË.Îïåðàöèÿ ñóïåðïîçèöèè ÊÑ è âñå åå ÷àñòíûå ñëó÷àè îïðåäåëÿþòñÿ îáû÷íûì îáðàçîì. Ïðè ýòîì ïîìåòêàìè âõîäîâ èâûõîäîâ ÊÑ, â îòëè÷èå îò ÑÔÝ, íå îáÿçàòåëüíî ÿâëÿþòñÿïåðåìåííûå, à ÁÏ, óïðàâëÿþùèå ïðîâîäèìîñòüþ êîíòàêòîâÊÑ, íèêàê íå ñâÿçàíû ñ åå âõîäàìè.Ëåãêî âèäåòü, ÷òî ïåðåñòàíîâêà âõîäîâ(âûõîäîâ) ÊÑ ïîðîæäàåò â ðåàëèçóåìîé åþ ìàòðèöå òàêóþ æå ïåðåñòàíîâêóñâÿçàííûõ ñ íèìè ñòðîê (ñîîòâåòñòâåííî ñòîëáöîâ), à ñíÿòèå(äóáëèðîâàíèå) âûõîäîâ ýòîé ÊÑ óäàëåíèå (ñîîòâåòñòâåííî äîáàâëåíèå) ñâÿçàíûõ ñ íèìè ñòîëáöîâ.
Çàìåòèì òàêæå,÷òî ÊÑ Σ, êîòîðàÿ ÿâëÿåòñÿ îáúåäèíåíèåì ÊÑ Σ0 è Σ00 , ðåàëèçóþùèõ ìàòðèöû F 0 è F 00 ñîîòâåòñòâåííî, ðåàëèçóåò ìàò-ïðîâîäíèêàìè9.Îïåðàöèÿ ñóïåðïîçèöèè. Ëåììà Øåííîíà81ðèöó F âèäà1 :F =F0 00 F 00Îáðàòèìñÿ, äàëåå, ê îñîáåííîñòÿì ôóíêöèîíèðîâàíèÿ ÊÑ,ïîëó÷àþùèõñÿ â ðåçóëüòàòå ïðèìåíåíèÿ îïåðàöèé ñóïåðïîçèöèè îáùåãî âèäà. Íàïîìíèì, ÷òî ñóïåðïîçèöèÿ îáùåãî âèäà ñâîäèòñÿ ê ïîñëåäîâàòåëüíîìó âûïîëíåíèþ îïåðàöèé ïåðåèìåíîâàíèÿ âûõîäîâ, äîáàâëåíèÿ òîæäåñòâåííûõ âåðøèíè ñòûêîâêè.
Ïðè ýòîì ñòûêîâêà, â ñâîþ î÷åðåäü, ñâîäèòñÿê ñíÿòèþ âûõîäîâ, îòîæäåñòâëåíèþ âõîäîâ è áåñïîâòîðíîéñòûêîâêå.Çàìåòèì, ÷òî ðåçóëüòàò îòîæäåñòâëåíèÿ ïåðâûõ p âõîäîâ ÊÑ Σ ýêâèâàëåíòåí ðåçóëüòàòó ñòûêîâêè âèäà Σ (Σ0 ),à ðåçóëüòàò p-êðàòíîãî äóáëèðîâàíèÿ ïåðâîãî âûõîäà ÊÑΣ ðåçóëüòàòó ñòûêîâêè Σ00 (Σ), ãäå ÊÑ Σ0 , Σ00 ñîñòîÿò èç(1, p)-ïðîâîäÿùåé çâåçäû (ñì.
ðèñ. 9.2a, a âõîä) è òîæäåb ,ñòâåííûõ âåðøèí. Çàìåòèì òàêæå, ÷òî ñòûêîâêà âèäà Σ(Σ)b ñîñòîèò èç (p, 1)-ïðîâîäÿùåé çâåçäû (ñì. ðèñ. 9.2b,ãäå ÊÑ Σa âûõîä) è òîæäåñòâåííûõ âåðøèí, ñîîòâåòñòâóåò îòîæäåñòâëåíèþ ïåðâûõ p âûõîäîâ ÊÑ Σ. ñîîòâåòñòâèè ñ îáùèìè ïðàâèëàìè ñòûêîâêà (ñóïåðïîçèöèÿ) ÊÑ âèäà Σ = Σ00 (Σ0 ) íàçûâàåòñÿ2, åñëè000000äëÿ ìàòðèö F , F è F , ðåàëèçóåìûõ ÊÑ Σ, Σ è Σ ñîîòâåòñòâåííî, âûïîëíÿåòñÿ ðàâåíñòâîïðàâèëüíîéF = F 0 · F 00 .1(9.1)Ïðåäïîëàãàåòñÿ, ÷òî íîìåð ëþáîãî âõîäà (âûõîäà) ÊÑ Σ0 ìåíüøåíîìåðà ëþáîãî âõîäà (ñîîòâåòñòâåííî âûõîäà) ÊÑ Σ00 â ÊÑ Σ, à âíóòðåííÿÿ óïîðÿäî÷åííîñòü ïîëþñîâ ÊÑ Σ0 è Σ00 â ÊÑ Σ ñîõðàíÿåòñÿ. îñòàëüíûõ ñëó÷àÿõ ïðîèñõîäèò íåîáõîäèìàÿ ïåðåñòàíîâêà âõîäîâ èâûõîäîâ ÊÑ Σ.2Ýòî îïðåäåëåíèå ñîîòâåòñòâóåò ¾îáû÷íîìó¿ îïðåäåëåíèþ êîððåêòíîé ñóïåðïîçèöèè â ðàìêàõ ìîäåëè òàê íàçûâàåìûõ ïðåîáðàçóþùèõÊÑ.82Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåì? ????? .
. . ????? . . . ?'. . . ??'?? ''?? ' . . . ?? '' ??' a1aa1 a2apapa2aa)b)?'. . . ??'?? ''?? '?? '' ??' y1ypy2z1c)Ðèñ. 9.2: ïðîâîäÿùèå è âåíòèëüíàÿ çâåçäû ïîðÿäêà pêîððåêòíîéÓêàçàííàÿ ñóïåðïîçèöèÿ ñ÷èòàåòñÿ, åñëè, êðîìå òîãî, â âûõîäíûõ âåðøèíàõ ïîäñõåìû Σ00 ñõåìû Σ ðåàëèçóþòñÿ òå æå ñàìûå ñòîëáöû ÔÀË, ÷òî è â ñàìîé ñõåìåΣ. Àíàëîãè÷íûì îáðàçîì îïðåäåëÿåòñÿ ïðàâèëüíîñòü è êîððåêòíîñòü ñóïåðïîçèöèè ÊÑ íà çàäàííîì íàáîðå çíà÷åíèéóïðàâëÿþùèõ ÁÏ.Çàìåòèì, ÷òî ïðè ïðàâèëüíîé ñòûêîâêå (1, p)-ÊÑ è (p,1)ÊÑ, ðåàëèçóþùèõñòðîêó è ñòîëáåö èç ÔÀË f10 , .
. . , fp0 è0000f1 , . . . , fp ñîîòâåòñòâåííî, ïîëó÷àåòñÿ (1, 1)-ÊÑ, ðåàëèçóþùàÿ ÔÀË f10 f100 ∨· · ·∨fp0 fp00 , ïðè ïðàâèëüíîì îòîæäåñòâëåíèèâõîäîâ (âûõîäîâ) ÊÑ â ðåàëèçóåìîé åþ ìàòðèöå ïðîèñõîäèòïîðàçðÿäíàÿ äèçúþíêöèÿ òåõ ñòðîê (ñîîòâåòñòâåííî ñòîëáöîâ), êîòîðûå ñîîòâåòñòâóþò îòîæäåñòâëåííûì âõîäàì (ñîîòâåòñòâåííî âûõîäàì) è ò. ï.9.Îïåðàöèÿ ñóïåðïîçèöèè. Ëåììà Øåííîíà83Ëåãêî âèäåòü, ÷òî îïåðàöèÿ ïåðåèìåíîâàíèÿ âõîäîâ (âûõîäîâ) ÊÑ áåç îòîæäåñòâëåíèÿ, îïåðàöèÿ îáúåäèíåíèÿ ÊÑ,à òàêæå îïåðàöèÿ ïîñëåäîâàòåëüíîãî ñîåäèíåíèÿ (1, 1)-ÊÑ(ñì. 6) êîððåêòíû â ëþáîì ñëó÷àå.  òî æå âðåìÿ ïàðàëëåëüíîå ñîåäèíåíèå (1, 1)-ÊÑ, ïðè êîòîðîì ñíà÷àëà îòîæäåñòâëÿþòñÿ âõîäû, à çàòåì âûõîäû ñîåäèíÿåìûõ ÊÑ, íåÿâëÿåòñÿ, â îáùåì ñëó÷àå, êîððåêòíîé îïåðàöèåé ñóïåðïîçèöèè, õîòÿ ÿâëÿåòñÿ ïðè ýòîì ïðàâèëüíîé ñóïåðïîçèöèåé,òàê êàê ïîëó÷åííàÿ ÊÑ ðåàëèçóåò äèçúþíêöèþ ÔÀË, ðåàëèçóåìûõ èñõîäíûìè ÊÑ.
Çàìåòèì, ÷òî êîððåêòíîå äèçúþíêòèðîâàíèå âûõîäíûõ ÔÀË ìîæíî îñóùåñòâèòü ñ ïîìîùüþñòûêîâêè èñõîäíîé ÊÑ ñ âåíòèëüíîé çâåçäîé (ñì. ðèñ. 9.2c).Ñõåìà íàçûâàåòñÿ(),åñëè ÔÀË ïðîâîäèìîñòè ìåæäó ëþáûìè åå ðàçëè÷íûìè âõîäàìè (ñîîòâåòñòâåííî âûõîäàìè) ðàâíà 0. Òàê (p, 1)-ñõåìàΣ00 = Σ00 (y1 , .
. . , yp ; z1 ), ïîêàçàííàÿ íà ðèñóíêå 9.2c, ÿâëÿåòñÿ ðàçäåëèòåëüíîé ïî âõîäàì ñõåìîé, êîòîðàÿ íàçûâàåòñÿp. Ïðèìåðîì ðàçäåëèòåëüíîéïî âûõîäàì (âõîäàì) ÊÑ ìîæåò ñëóæèòü (1, 2n ) (ñîîòâåòñòâåííî (2n , 1)) êîíòàêòíîå äåðåâî ïîðÿäêà n (ñì. ðèñ. 6.4).Áóäåì ãîâîðèòü, ÷òî ÊÑ Σ îò ÁÏ x1 , . . . , xnα = (α1 , . . . , αn ) çíà÷åíèé ýòèõ ÁÏ, åñëè ñîîòâåòñòâóþùåé ðàçäåëèòåëüíîñòüþ îáëàäàåò ñåòü Σ|α . Ñëåäóþùåå óòâåðæäåíèå ÿâëÿåòñÿ îáîáùåíèåì èçâåñòíîé ëåììûØåííîíà (ñì. [31, 14]).ðàçäåëèòåëüíîé ïî âõîäàì âûõîäàìâåíòèëüíîé çâåçäîé ïîðÿäêàðàçäåëèòåëüíàíà íàáîðåÏóñòü ÊÑ Σ ÿâëÿåòñÿ ðåçóëüòàòîì ñòûêîâêè âèäà Σ = Σ00 (Σ0), à F , F 0 è F 00 ìàòðèöû, ðåàëèçóåìûåÊÑ Σ, Σ0 è Σ00 ñîîòâåòñòâåííî. ÒîãäàËåììà 9.1.F > F 0 · F 00è F = F 0 · F 00,(9.2)åñëè ÊÑ Σ00 ðàçäåëèòåëüíà ïî âõîäàì èëè ÊÑ Σ0 ðàçäåëèòåëüíà ïî âûõîäàì.84Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìÄîêàçàòåëüñòâî.
Ïóñòü ÊÑ Σ ÿâëÿåòñÿ ñíà÷àëà ðåçóëüòà-òîì áåñïîâòîðíîé ñòûêîâêè (p, q)-ÊÑ Σ0 è (q, s)-ÊÑ Σ00 îò ÁÏx1 , . . . , xn . Ïóñòü, êðîìå òîãî, v 0 (v 00 ) ïðîèçâîëüíàÿ âåðøèíà ÊÑ Σ0 (ñîîòâåòñòâåííî Σ00 ), à ÔÀË fj0 (ñîîòâåòñòâåííî fj00 ),j ∈ [1, q], ÔÀË ïðîâîäèìîñòè îò âåðøèíû v 0 ê j -ìó âûõîäó â ÊÑ Σ0 (ñîîòâåòñòâåííî îò j -ãî âõîäà ê âåðøèíå v 00 âÊÑ Σ00 ). Äîêàæåì, ÷òî äëÿ ÔÀË f ÔÀË ïðîâîäèìîñòè îòâåðøèíû v 0 ê âåðøèíå v 00 â ÊÑ Σ, ñïðàâåäëèâî íåðàâåíñòâîf (x1 , .
. . , xn ) > f10 · f100 ∨ · · · ∨ fq0 · fq00 ,(9.3)êîòîðîå ïåðåõîäèò â ðàâåíñòâîf (x1 , . . . , xn ) = f10 · f100 ∨ · · · ∨ fq0 · fq00 ,(9.4)åñëè ÊÑ Σ0 ðàçäåëèòåëüíà ïî âûõîäàì èëè ÊÑ Σ00 ðàçäåëèòåëüíà ïî âõîäàì.Äåéñòâèòåëüíî, ïóñòü aj , j ∈ [1, q], âåðøèíà ÊÑ Σ,êîòîðàÿ ïîëó÷àåòñÿ â ðåçóëüòàòå ïðèñîåäèíåíèÿ j -ãî âõîäà ÊÑ Σ00 ê j -ìó âûõîäó ÊÑ Σ0 (ñì.
ðèñ. 9.3a). Ñïðàâåäëèâîñòü íåðàâåíñòâà (9.3) ñëåäóåò èç òîãî, ÷òî åãî ïðàâàÿ÷àñòü îïèñûâàåò ¾ñóììàðíóþ¿ ïðîâîäèìîñòü òåõ (v 0 − v 00 )öåïåé ÊÑ Σ, êîòîðûå ïðîõîäÿò ÷åðåç âåðøèíû a1 , . . . , aq ðîâíî îäèí ðàç (ñì. ðèñ. 9.3a). Ëþáàÿ äðóãàÿ (v 0 − v 00 )-öåïü ÊÑΣ ïðîõîäèò ÷åðåç óêàçàííûå âåðøèíû íå ìåíüøå òðåõ ðàç(ñì. ðèñ. 9.3b) è â ñëó÷àå ðàçäåëèòåëüíîñòè ÊÑ Σ0 ïî âûõîäàì èëè ðàçäåëèòåëüíîñòè ÊÑ Σ00 ïî âõîäàì èìååò íóëåâóþïðîâîäèìîñòü.Èç (9.3) è (9.4) íåïîñðåäñòâåííî âûòåêàåò (9.2) ñ ó÷åòîì òîãî, ÷òî ïðè v 0 = a0i è v 00 = a00j , ãäå i ∈ [1, p] è j ∈[1, s], ëåâàÿ(ïðàâàÿ) ÷àñòü ýòèõ ñîîòíîøåíèé ðàâíà ýëåìåíòó ìàòðèöû F (ñîîòâåòñòâåííî F 0 · F 00 ), ðàñïîëîæåííîìó âi-é ñòðîêå è j -ì ñòîëáöå.Ïóñòü òåïåðü ÊÑ Σ ïîëó÷àåòñÿ èç ÊÑ Σ00 â ðåçóëüòàòåïðèìåíåíèÿ îïåðàöèè îòîæäåñòâëåíèÿ âõîäîâ, òî åñòü Σ ýêâèâàëåíòíà áåñïîâòîðíîé ñòûêîâêå âèäà Σ00 (Σ0 ), ãäå ÊÑ Σ09.85Îïåðàöèÿ ñóïåðïîçèöèè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
