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

ðèñ. 6.4a èç Ÿ6 ãëàâû 2) â ðåçóëüòàòå ñíÿòèÿ òåõ åãîâûõîäîâ, ãäå ðåàëèçóþòñÿ ÝÊ, íå âõîäÿùèå â ñîâåðøåííóþÄÍÔ ÔÀË f , îòîæäåñòâëåíèÿ îñòàëüíûõ âûõîäîâ ÊÄ è ïåðåõîäà ê ñîîòâåòñòâóþùåé ïðèâåäåííîé ÊÑ. Òàê êàê ïðèóäàëåíèè âåðøèíû óäàëÿþòñÿ è âñå èíöèäåíòíûå åé êîíòàêòû, òîL (Σf ) 6 2 (2n − 1) − (2n − |Nf |) = 2n + |Nf | − 2.Ôîðìóëà Ff ïîëó÷àåòñÿ â ðåçóëüòàòå ìîäåëèðîâàíèÿ ïîñòðîåííîé π -ñõåìû Σf â êëàññå ôîðìóë ñ ïîäíÿòûìè îòðèöàíèÿìè (ñì. Ÿ2 ãë. 2), è ïîýòîìóR (Ff ) = L (Σf ) ,L (Ff ) = R (Ff ) + L− (Σf ) − 1,ãäå L− (Σf ) ÷èñëî ðàçìûêàþùèõ êîíòàêòîâ â ñõåìå Σ.Ñëåäîâàòåëüíî,L (Ff ) 6 L (Σf ) + 2n − 2 6 2n+1 + |Nf | − 4,òàê êàê ÷èñëî ðàçìûêàþùèõ êîíòàêòîâ â ÊÄ ïîðÿäêà n ðàâíî 2n − 1.Ëåììà äîêàçàíà.Ÿ1. Çàäà÷à ñèíòåçà11Ñëåäñòâèå.Lπ (n) 6 2n+1 − 2,(1.2)LΦ (n) 6 3 · 2n − 4.(1.3)Ê ñõåìàì, ïîëó÷åííûì íà îñíîâå ïðîñòåéøèõ ìåòîäîâñèíòåçà, ïîëåçíî ïðèìåíÿòü ñ öåëüþ óìåíüøåíèÿ èõ ñëîæíîñòè ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ è, â ÷àñòíîñòè, ñëåäóþùèå îïåðàöèè ïðèâåäåíèÿ.Ïóñòü âåðøèíà w ÑÔÝ Σ íå äîñòèæèìà èç åå âåðøèíû v ,à ÑÔÝ Σ0 ïîëó÷àåòñÿ èç ÑÔÝ Σ â ðåçóëüòàòå óäàëåíèÿ âåðøèíû v , îáúÿâëåíèÿ âåðøèíû w íà÷àëüíîé âåðøèíîé âñåõèñõîäèâøèõ èç v äóã è ïåðåíîñà â âåðøèíó w âñåõ âûõîäíûõ ÁÏ, ïðèïèñàííûõ âåðøèíå v .

Òîãäà ÑÔÝ Σ0 ñ÷èòàåòñÿðåçóëüòàòîì ïðèìåíåíèÿ ê ÑÔÝ Σ îïåðàöèè ïðèñîåäèíåíèÿâåðøèíû v ê âåðøèíå w. Çàìåòèì, ÷òî äëÿ ëþáûõ äâóõ âåðøèí ñõåìû îäíó èç íèõ âñåãäà ìîæíî ïðèñîåäèíèòü ê äðóãîé. Äâå âåðøèíû ÑÔÝ íàçûâàþòñÿ ýêâèâàëåíòíûìè, åñëèâ íèõ ðåàëèçóþòñÿ ðàâíûå ÔÀË. Ïðèìåíÿÿ ê ÑÔÝ Σ îïåðàöèþ ïðèñîåäèíåíèÿ îäíîé èç äâóõ ýêâèâàëåíòíûõ âåðøèíê äðóãîé, ìû ïîëó÷èì ÑÔÝ Σ0 , êîòîðàÿ, î÷åâèäíî, ýêâèâàëåíòíà Σ.Ïðèâåäåííàÿ ñõåìà íàçûâàåòñÿ ñòðîãî ïðèâåäåííîé, åñëè â íåé íåò ýêâèâàëåíòíûõ âåðøèí. Èç ëþáîé ÑÔÝ ìîæíîïîëó÷èòü ýêâèâàëåíòíóþ åé ñòðîãî ïðèâåäåííóþ ÑÔÝ ñ ïîìîùüþ îïåðàöèè ïðèñîåäèíåíèÿ ýêâèâàëåíòíûõ âåðøèí èîïåðàöèè óäàëåíèÿ âèñÿ÷èõ âåðøèí.Àíàëîãè÷íûì îáðàçîì îïðåäåëÿåòñÿ îïåðàöèÿ ïðèñîåäèíåíèÿ âåðøèí â ÊÑ, ñ òîé ëèøü ðàçíèöåé, ÷òî íà íåå íå íàêëàäûâàþòñÿ êàêèå-ëèáî îãðàíè÷åíèÿ, ñâÿçàííûå ñ äîñòèæèìîñòüþ âåðøèí.→−Äëÿ ìíîæåñòâà ÔÀË G, G ⊆ P2 (n), ÷åðåç G áóäåì îáîçíà÷àòü ñèñòåìó, ñîñòîÿùóþ èç âñåõ ðàçëè÷íûõ ÔÀË ìíîæåñòâà G, óïîðÿäî÷åííûõ â ñîîòâåòñòâèè ñ íîìåðàìè èõ ñòîëá-12Ãëàâà 3.

Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåì→−öîâ çíà÷åíèé. Ïðè ýòîì ñèñòåìó ÔÀË P 2 (n) áóäåì íàçûâàòü óíèâåðñàëüíîé ñèñòåìîé ïîðÿäêà n.Äîâîëüíî ÷àñòî çàäà÷ó ñèíòåçà ïðèõîäèòñÿ ðåøàòü äëÿñëåäóþùèõ ÔÀË è ñèñòåì ÔÀË:1. ëèíåéíîé ÔÀË ïîðÿäêà n, òî åñòü ÔÀË `n èëè ÔÀË `n ;2. ìóëüòèïëåêñîðíîé ÔÀË µn ïîðÿäêà n;→−−→3. äåøèôðàòîðà Q n (äèçúþíêòèâíîãî äåøèôðàòîðà J n )ïîðÿäêà n;−→4. óíèâåðñàëüíîé ñèñòåìû P 2 (n) ïîðÿäêà n.Ðàññìîòðèì íåêîòîðûå ñõåìíûå ðåàëèçàöèè è ñîîòâåòñòâóþùèå èì âåðõíèå îöåíêè ñëîæíîñòè äëÿ óêàçàííûõ ÔÀËè ñèñòåì ÔÀË. Áóäåì, êàê îáû÷íî, íàçûâàòü (ñõåìíûì) ìóëüòèïëåêñîðîì, äåøèôðàòîðîì, äèçúþíêòèâíûì äåøèôðàòîðîì è óíèâåðñàëüíûì ìíîãîïîëþñíèêîì ëþáóþ ñõåìó, êîòîðàÿ ðåàëèçóåò ñîîòâåòñòâóþùóþ ñèñòåìó ÔÀË.Ëåììà 1.3. Äëÿ êàæäîãî íàòóðàëüíîãî n â UCÁ ñóùåñòâó-åò óíèâåðñàëüíàÿ ÑÔÝ Un ïîðÿäêà n, ñëîæíîñòü êîòîðîénðàâíà 22 − n.Äîêàçàòåëüñòâî.

 ñèëó ïîëíîòû áàçèñà, â UCÁ ñóùåñòâóåò ñèñòåìà ôîðìóë Σ îò ÁÏ x1 , . . . , xn , êîòîðàÿ ðåàëèçó→−åò ñèñòåìó ÔÀË P 2 (n). Èñêîìàÿ ÑÔÝ Un ÿâëÿåòñÿ ñòðîãî ïðèâåäåííîé ÑÔÝ, êîòîðàÿ ýêâèâàëåíòíà Σ è ïîëó÷àåòñÿèç íåå â ðåçóëüòàòå ïðèìåíåíèÿ îïåðàöèé ïðèñîåäèíåíèÿ ýêâèâàëåíòíûõ âåðøèí, à òàêæå îïåðàöèé óäàëåíèÿ âèñÿ÷èõâåðøèí (ñì. Ÿ4 ãëàâû 2). Äåéñòâèòåëüíî, èç ïîñòðîåíèÿ ñëåäóåò, ÷òî ÷èñëî âñåõ âåðøèí ÑÔÝ Un , âêëþ÷àÿ n åå âõîäîâ,nðàâíî 22 è ïîýòîìónL (Un ) = 22 − n.Ëåììà äîêàçàíà.Ÿ1. Çàäà÷à ñèíòåçàÑëåäñòâèå.13³−´→2nLCÁ P 2 (n) 6 2 − n.Ëåììà 1.4. Äëÿ ëþáîãî íàòóðàëüíîãî n âûïîëíÿþòñÿ íåðàâåíñòâà:n−→LC ( Q n ) 6 2n + O(n · 2 2 ),πnL (µn ) 6 3 · 2 − 2,LC (`n ) 6 4n − 4,−→LK ( Q n ) 6 2n+1 − 2;Φn+2(1.4)(1.5)¹ º1.

(1.6)LC (`n ) 6 4n − 4 +nL (µn ) 6 2− 3;Äîêàçàòåëüñòâî. Â êëàññå UC ïîñòðîèì ñõåìíûé äåøèôðàòîð ïîðÿäêà n, óäîâëåòâîðÿþùèé ïåðâîìó íåðàâåíñòâó (1.4),ñëåäóþùèì îáðàçîì:1. ðàçîáüåì íàáîð ÁÏ X(n) íà ãðóïïû x0 == (x1 , . . . , xq ), x00 = (xq+1 , . . . , xn ), ãäå q = dn/2e;2.

âîçüìåì äåøèôðàòîðû Σ0 è Σ00 îò ÁÏ x0 è x00 ïîðÿäêàq è (n − q) ñîîòâåòñòâåííî, ðåàëèçóþùèå êàæäóþ ñâîþñèñòåìó ÝÊ ïî ëåììå 1.1;3. îáúåäèíèì ÑÔÝ Σ0 è Σ00 , ïîñëå ÷åãî êîíúþíêòèðóåìêàæäûé âûõîä Σ0 ñ êàæäûì âûõîäîì Σ00 , à âûõîäû âñåõèñïîëüçîâàííûõ äëÿ ýòîãî 2n ÔÝ & (è òîëüêî èõ) îáúÿâèì âûõîäàìè èñêîìîãî äåøèôðàòîðà.Èñêîìûì êîíòàêòíûì äåøèôðàòîðîì ïîðÿäêà n ÿâëÿåòñÿ(1, 2n )-êîíòàêòíîå äåðåâî, ïîêàçàííîå íà ðèñóíêå 6.4a Ÿ6 ãëàâû 2, à èñêîìûì êîíòàêòíûì ìóëüòèïëåêñîðîì ïîðÿäêà n π -ñõåìà, ïðèâåäåííàÿ òàì æå íà ðèñ. 6.6b. Çàìåòèì, ÷òîñëîæíîñòü ñõåì, ïîêàçàííûõ íà ðèñ. 6.4a è 6.6b, ðàâíà 2n+1 −2 è 3 · 2n − 2 ñîîòâåòñòâåííî, òî åñòü óäîâëåòâîðÿåò íåðàâåíñòâàì (1.4) è (1.5), ïðè÷åì ÷èñëî ðàçìûêàþùèõ êîíòàêòîââ êàæäîé èç íèõ ðàâíî 2n − 1.14Ãëàâà 3.

Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåì ðåçóëüòàòå ìîäåëèðîâàíèÿ óêàçàííîé π -ñõåìû ìîæíîïîñòðîèòü áåñïîâòîðíóþ ïî èíôîðìàöèîííûì ÁÏ ôîðìóëóFn (x1 , . . . , xn , y0 , . . . , y2n −1 ) =à Ã! !___=xσ1 1 xσ2 2 · · ·xσnn yν(σ1 ,...,σn ) · · ·  ,σ1 ∈Bσ2 ∈Bσn ∈Bêîòîðàÿ óäîâëåòâîðÿåò âòîðîìó íåðàâåíñòâó (1.5), òàê êàêðåàëèçóåò ÔÀË µn , èìååò ñëîæíîñòü 4 · 2n − 3 è àëüòåðíèðîâàíèå 2n − 1.Íåðàâåíñòâà (1.6) ïðè n = 1, î÷åâèäíî, âûïîëíÿþòñÿ.Èñêîìîé ÑÔÝ, ðåàëèçóþùåé ëèíåéíóþ ÔÀË `n , n > 2, ñîñëîæíîñòüþ (1.6), ÿâëÿåòñÿ ÑÔÝ Σ⊕n , ïîêàçàííàÿ íà ðèñ. 9.1bãëàâû 2.

Àíàëîãè÷íàÿ ÑÔÝ äëÿ ÔÀË `n ïîëó÷àåòñÿ â ðåçóëüòàòå çàìåíû ÔÝ & íà ÔÝ ∨ è ÔÝ ∨ íà ÔÝ & â ïåðâîé⊕ïîäñõåìå âèäà Σ⊕2 ñõåìû Σn (ñì. ðèñ. 9.1a ãëàâû 2).Ëåììà äîêàçàíà.Ÿ2 Ïðîñòåéøèå íèæíèå îöåíêè ñëîæíîñòè ÔÀË.Íèæíèå ìîùíîñòíûå îöåíêè ôóíêöèé Øåííîíà.Ðàññìîòðèì ñíà÷àëà íåêîòîðûå íèæíèå îöåíêè ñëîæíîñòèÔÀË è ïðèìåðû ìèíèìàëüíûõ ñõåì.Ëåììà 2.1. Åñëè ÔÀË f (x1 , .

. . , xn ) ñóùåñòâåííî çàâèñèòîò âñåõ ñâîèõ ÁÏ, òîLC (f ) > n − 1,LK (f ) > n.(2.1)Åñëè ïðè ýòîì ÔÀË f íå ÿâëÿåòñÿ ìîíîòîííîé ÔÀË (êàæäàÿ ÁÏ xi , i ∈ [1, k], íå ÿâëÿåòñÿ íè ìîíîòîííîé, íè èíìîíîòîííîé ÁÏ ÔÀË f ), òîLC (f ) > n(ñîîòâåòñòâåííî LK (f ) > n + k).(2.2)Ÿ2. Íèæíèå îöåíêè15Äîêàçàòåëüñòâî. Ïóñòü Σf ìèíèìàëüíàÿ ïî ñëîæíîñòèÑÔÝ èç UC , ðåàëèçóþùàÿ ÔÀË f .

Èç ñóùåñòâåííîé çàâèñèìîñòè ÔÀË f îò ÁÏ x1 , . . . , xn ñëåäóåò, ÷òî R (Σf ) > n, èïîýòîìó, â ñèëó ñîîòíîøåíèé (2.6) ãëàâû 2,LC (f ) > L&, ∨ (Σf ) > n − 1.Åñëè æå, êðîìå òîãî, ÔÀË f íå ÿâëÿåòñÿ ìîíîòîííîéÔÀË, òî ñõåìà Σf äîëæíà ñîäåðæàòü õîòÿ áû îäèí ÔÝ ¬ è,ñëåäîâàòåëüíî, â óêàçàííîì ñëó÷àåLC (f ) = L (Σf ) > n.Òàêèì îáðàçîì, ïåðâûå èç íåðàâåíñòâ (2.1) è (2.2) äîêàçàíû.Ïóñòü òåïåðü Σf ìèíèìàëüíàÿ ïî ñëîæíîñòè (1, 1)-ÊÑ,ðåàëèçóþùàÿ ÔÀË f .

Èç ñóùåñòâåííîé çàâèñèìîñòè ÔÀË fîò ÁÏ xi , i ∈ [1, n], ñëåäóåò, ÷òî ëèáî êîíòàêò âèäà xi , ëèáîêîíòàêò âèäà xi âñòðå÷àåòñÿ â ÊÑ Σf , è ïîýòîìóLK (f ) = L (Σf ) > n.Åñëè æå, êðîìå òîãî, ÁÏ xi , i ∈ [1, k], íå ÿâëÿåòñÿ íè ìîíîòîííîé, íè èíìîíîòîííîé ÁÏ ÔÀË f , òî êàê êîíòàêò âèäàxi , òàê è êîíòàêò âèäà xi âõîäÿò â Σf , è, ñëåäîâàòåëüíî, âäàííîì ñëó÷àåLK (f ) = L (Σf ) > n + k.Ëåììà äîêàçàíà.Ñëåäñòâèå.LC (`n ) > n,LK (`n ) > 2n,LC (µn ) > 2n + n,LK (µn ) > 2n + 2n.16Ãëàâà 3.

Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìËåììà 2.2. Äëÿ ñèñòåìû F = (f1 , . . . , fm ), ñîñòîÿùåé èçïîïàðíî ðàçëè÷íûõ ÔÀË îòëè÷íûõ îò êîíñòàíò (îò ïåðåìåííûõ), ñïðàâåäëèâî íåðàâåíñòâîLK (F ) > m(ñîîòâåòñòâåííî LCÁ (F ) > m).(2.3)Äîêàçàòåëüñòâî. Âòîðîå èç íåðàâåíñòâ (2.3) âûòåêàåò èçòîãî, ÷òî âñå ÔÀË fi , i = 1, . . . , m, ðåàëèçóþòñÿ íà ïîïàðíî ðàçëè÷íûõ âûõîäàõ ÑÔÝ, îòëè÷íûõ îò åå âõîäîâ.Ïóñòü òåïåðü ΣF ïðèâåäåííàÿ (1, m)-ÊÑ, ðåàëèçóþùàÿ ñèñòåìó ÔÀË F . Èç ïðèâåäåííîñòè ΣF è óñëîâèé ëåììû âûòåêàåò, ÷òî ΣF ñâÿçíûé ãðàô ñ íå ìåíåå ÷åì (m + 1)âåðøèíîé, è ïîýòîìó, â ñèëó íåðàâåíñòâà (1.2) ãëàâû 2,L (ΣF ) > |V (ΣF )| − 1 > m.Ëåììà äîêàçàíà.Ñëåäñòâèå.³−→ ´LC Q n > 2n ,³−→ ´LC J n > 2n ,³→´nC −LÁ P 2 (n) > 22 − n,³−→ ´LK Q n > 2n ,³−→ ´LK J n > 2n ,³−´nK →LP 2 (n) > 22 − 2.Çàìå÷àíèå.

 ñèëó ñëåäñòâèÿ óíèâåðñàëüíàÿ ÑÔÝ Un , ïîñòðîåííàÿ â ëåììå 1.3, ÿâëÿåòñÿ ìèíèìàëüíîé ïî ñëîæíîñòèÑÔÝ â êëàññå UCÁ.Óñòàíîâèì òåïåðü ðÿä íèæíèõ îöåíîê äëÿ ââåäåííûõ ⠟1ôóíêöèé Øåííîíà. Âñå ýòè îöåíêè ïîëó÷åíû ñ ïîìîùüþìîùíîñòíîãî ìåòîäà, ïðåäëîæåííîãî Øåííîíîì [32, 14], êîòîðûé îñíîâàí íà òîì, ÷òî ÷èñëî ÔÀË îò ÁÏ x1 , . . . , xn íåìîæåò áûòü ìåíüøå ÷èñëà òåõ ïîïàðíî íå ýêâèâàëåíòíûõñõåì, ñëîæíîñòü êîòîðûõ íå ïðåâîñõîäèò çíà÷åíèÿ ñîîòâåòñòâóþùåé ôóíêöèè Øåííîíà îò àðãóìåíòà n.Ÿ2. Íèæíèå îöåíêè17Ïóñòü U îäèí èç ðàññìîòðåííûõ â ãëàâå 2 êëàññîâ ñõåì,Ψ ââåäåííûé òàì ôóíêöèîíàë ñëîæíîñòè, à Ψ (n) ôóíêöèÿ Øåííîíà äëÿ êëàññà U îòíîñèòåëüíî Ψ. Îáîçíà÷èì ÷åðåç U (Ψ, n) ìíîæåñòâî òåõ ñõåì Σ, Σ ∈ U, êîòîðûå ðåàëèçóþò îäíó ÔÀË èç P2 (n) è äëÿ êîòîðûõ Ψ (Σ) 6 Ψ.

Ñëåäóþùåå ¾ìîùíîñòíîå¿ ðàâåíñòâî âûòåêàåò íåïîñðåäñòâåííî èçîïðåäåëåíèé:nkU (Ψ (n) , n)k = 22 .(2.4)Çàìåòèì òàêæå, ÷òî åñëè äëÿ íåêîòîðîãî íàòóðàëüíîãî n èb δ , ãäå 0 < δ < 1, âûïîëíÿåòñÿ íåðàâåíäåéñòâèòåëüíûõ Ψ,ñòâî° ³´°n°b n °b(2.5)°U Ψ,° 6 δ · 22 , òî Ψ(f ) > Ψnäëÿ íå ìåíåå ÷åì (1 − δ) · 22 ÔÀË f èç P2 (n).Âåðõíèå îöåíêè âåëè÷èíû kU(Ψ, n)k, óñòàíîâëåííûå âãëàâå 2 äëÿ ðàçëè÷íûõ êëàññîâ ñõåì è ôóíêöèîíàëîâ ñëîæíîñòè, à òàêæå ñîîòíîøåíèÿ (2.4)(2.5) ñëóæàò îñíîâîé äëÿïîëó÷åíèÿ íèæíèõ ìîùíîñòíûõ îöåíîê ñîîòâåòñòâóþùèõ ôóíêöèé Øåííîíà è ñëîæíîñòè ïî÷òè âñåõ ÔÀË. Íàïîìíèì, ÷òî(ñì.

ëåììû 4.3, 4.4, 6.2, 6.3 èç ãëàâû 2) äëÿ ëþáûõ íàòóðàëüíûõ n è L ñïðàâåäëèâû íåðàâåíñòâà:¯ C¯¯U (L, n)¯ 6 (8 (L + n))L+1 ,(2.6)¯ Φ¯L+1¯U (L, n)¯ 6 (8n),(2.7)¯ K¯¯U (L, n)¯ 6 (8nL)L ,(2.8)|Uπ (L, n)| 6 (12n)L .(2.9)Ëåììà 2.3. Äëÿ ïîëîæèòåëüíûõ äåéñòâèòåëüíûõ ÷èñåëa, y, q èç íåðàâåíñòâa log q > 1,ñëåäóåò íåðàâåíñòâîlog qy>log (a log q)(ay)y > q,µ¶log log (a log q)1+,log (ae log q)(2.10)(2.11)18Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìãäå e îñíîâàíèå íàòóðàëüíûõ ëîãàðèôìîâ, à èç íåðàâåíñòâa > 1, ay > q íåðàâåíñòâîy>log q.log a(2.12)Äîêàçàòåëüñòâî.