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

. , ψp óïðàâëÿþò ïðîâîäè-42Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåììîñòüþ ñîîòâåòñòâóþùèõ êîíòàêòîâ. Àñèìïòîòè÷åñêè íàèëó÷øèé ìåòîä ñèíòåçà ÊÑ ñâÿçàí ñ ¾ìîäåëèðîâàíèåì¿ ýòîéñóïåðïîçèöèè è ïðåäñòàâëåíèÿ (6.1) íà êîìïîíåíòàõ ïîäõîäÿùåãî m-ðåãóëÿðíîãî ðàçáèåíèÿ êóáà B m+p .Ïóñòü δ̌ m-ðåãóëÿðíîå ìíîæåñòâî íàáîðîâ êóáà B m+p ,−→ñîîòâåòñòâóþùåå ñèñòåìå ÔÀË ψ = (ψ1 , . .

. , ψp ) (ñì. ðèñ. 6.2a),à ∆ = (δ1 , . . . , δ2p ) ïîñòðîåííîå äëÿ íåå ïî ëåììå 4.1 ðàçáèåíèå êóáà B m+p . Çàìåòèì, ÷òî ëþáàÿ ÔÀË g, g ∈ P2 (m + p),íà ëþáîé êîìïîíåíòå ýòîãî ðàçáèåíèÿ âèäà δ̌ ⊕ α, ãäåα = (0, . . . , 0, αm+1 , . . . , αm+p ),| {z }mñîâïàäàåò ñ ÔÀËααm+pm+1ǧ = xm+1· g1 ∨ . . . ∨ xm+p· gp ,(6.2)ãäå gi = gψi ∈ G(i) , i = 1, . . . , p. Ïðè ýòîì ÔÀË ǧ ìîæåò áûòü ðåàëèçîâàíà â ðåçóëüòàòå îïåðàöèè ïðèñîåäèíåαm+pαm+1, . . .

, xm+pê âûõîäàìíèÿ çâåçäû èç êîíòàêòîâ âèäà xm+1−→(1, λ)-ÊÑ ΣG , ðåàëèçóþùåé ñèñòåìó ÔÀË G , òàê, êàê ýòîïîêàçàíî íà ðèñ. 6.2b. Çàìåòèì òàêæå, ÷òî óêàçàííàÿ îïåðàöèÿ ñóïåðïîçèöèè ÿâëÿåòñÿ êîððåêòíîé íà ìíîæåñòâå íàáîðîâ δ̌ ⊕α â ñèëó ðàçäåëèòåëüíîñòè ïðèñîåäèíÿåìîé (p, 1)-ÊÑíà ýòîì ìíîæåñòâå.Òåîðåìà 6.1 (ñð.

[14]). Äëÿ ëþáîé ÔÀË f , f ∈ P2 (n), ñóùåñòâóåò ðåàëèçóþùàÿ åå ÊÑ Σf òàêàÿ, ÷òî2nL (Σf ) 6nµµ¶¶11+O √n(6.3)Äîêàçàòåëüñòâî. Ïóñòü q = m + p, à ∆ = (δ1 , . . . , δ2p ) îïèñàííîå âûøå ðàçáèåíèå êóáà B q , ñ ïîìîùüþ êîòîðîãîŸ6. Àñèìïòîòè÷åñêè íàèëó÷øèé ìåòîä ñèíòåçà ÊÑ. . . xm−1 xm ψ1 x1 0 ... 010... 0101.....π1....1...0...0.....π2....0.........0...0.....πp....1110ψ200...011...1.... . . ψp00... ...000... ...0... ...00.. . . ..011...1δ̌a)qq g1qqqq•MMM xαm+1qMMm+1qqqMMMqqqMº³¹´¸·µ¶..qΣG1 º³¹´¸·Mqµ¶ MMMq.qMMMqq ǧMMMqqqαm+pqqx•MMMm+pMM gpb)Ðèñ. 6.2: m-ðåãóëÿðíîå ìíîæåñòâî δ̌ è ñâÿçàííàÿ ñ íèìñóïåðïîçèöèÿ ÊÑ4344Ãëàâà 3.

Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìÔÀË f ìîæíî ïðåäñòàâèòü â âèäåp2¡¢ _¡ 0¢f x0 , x00 =xxi=1i_¡ ¢σq+1xq+1· · · xσnn ǧσ00 ,i x0 ,σ 00 =(σq+1 ,...,σn )(6.4)ãäå x õàðàêòåðèñòè÷åñêàÿ ÔÀË δi , à â êà÷åñòâå ÔÀË fσ00 ,iiïðè âñåõ σ 00 ,σ 00 ∈ B n−q , è i, i ∈ [1, 2p ], áåðåòñÿ ÔÀË ǧσ00 ,i âèäà(6.2), ñîâïàäàþùàÿ ñ ÔÀË fσ00 (x0 ) íà êîìïîíåíòå δi = δ̌ ⊕ α.Ïóñòü ΣG (1, λ)-ÊÑ, êîòîðàÿ ðåàëèçóåò ñèñòåìó ÔÀË−→G ïî èõ ñîâåðøåííûì ÄÍÔ íà îñíîâå êîíòàêòíîãî äåðåâà(ñì. ëåììó 1.2 è îöåíêó (1.2)). Äëÿ êàæäîãî i, i = 1, . . . , 2p ,ïîñòðîèì (1, 2n−q )-ÊÑ Σ0i (ñì.

ðèñ. 6.3a), êîòîðàÿ ñîäåðæèòÊÑ ΣG â êà÷åñòâå ïîäñõåìû è ðåàëèçóåò êàæäóþ ÔÀË ǧσ00 ,iâèäà (6.2) ñ ïîìîùüþ êîððåêòíîé íà ìíîæåñòâå íàáîðîâδi ñóïåðïîçèöèè, ïîêàçàííîé íà ðèñóíêå 6.2b. Ïóñòü, äàëåå (1, 2n−m )-ÊÑ Σ0 ïîëó÷àåòñÿ â ðåçóëüòàòå îòîæäåñòâëåíèÿ âõîäîâ ó ïîñòðîåííûõ âûøå ÊÑ Σ0i , i ∈ [1, 2p ], è ðåàëèçóåò ñèñòåìó èç âñåõ ÔÀË âèäà ǧσ00 ,i , ãäå σ 00 ∈ B n−q , i ∈ [1, 2p ].Çàìåòèì, ÷òî ïðè ýòîì âûïîëíÿþòñÿ íåðàâåíñòâàL (ΣG ) 6 λ2m+1 ,¡ ¢L Σ0i 6 L (ΣG ) + p2n−q ,¡ ¢L Σ0 6 p2n−m + λ2q+1 .(6.5)Ïîñòðîèì, íàêîíåö, ðàçäåëèòåëüíóþ ïî âõîäàì (2n−m , 1)ÊÑ Σ00 , êîòîðàÿ ðåàëèçóåò ñòîëáåö èç âñåõ ÔÀË âèäà x (x0 )·σiq+1xq+1· · · xnσn , ãäå i ∈ [1, 2p ] è σ 00 = (σq+1 , .

. . , σn ) ∈ B n−q .Ýòà ÊÑ ïîëó÷àåòñÿ â ðåçóëüòàòå îáúåäèíåíèÿ 2p ñõåì òèïà (2n−q , 1)-ÊÄ îò ÁÏ x00 , ê âûõîäàì êîòîðûõ ïðèñîåäèíåíû âõîäû (2p , 1)-ÊÑ, ðåàëèçóþùåé ñòîëáåö èç ÔÀË x ,ii ∈ [1, 2p ], è ïîëó÷àþùåéñÿ èç (2q , 1)-ÊÄ îò ÁÏ x0 â ðåçóëüòàòå ñîîòâåòñòâóþùåãî îòîæäåñòâëåíèÿ âõîäîâ (ñì. ðèñ. 6.3b).Ÿ6. Àñèìïòîòè÷åñêè íàèëó÷øèé ìåòîä ñèíòåçà ÊÑ~~OO~~ ZdZdZdOZdOo• ǧe~ooo 0,i~~..~~~~.~OOZOO~~ZZZ@~d1 • @@ ΣG dododoo• ǧσ00 ,i@@..@@.@@OO@@ ZZZOZO@@ dddodo• ǧe1,i@@oo|{zΣ0i}.........|45@@VVVVx@VVVV 1 ooo @@@@VVVdZOodZododdd00hÊÄ(x ) hhh • OZ@@OZOZOZhhh@@Ohhhh@@..@@.VVVVx@@VVVVodooioV@dVh•dZOodZoOdZdZ0)ÊÄ(x00 ) hhhVZÊÄ(x~•ZOOh~hOhO~~hhhh..~~.VVVVx~~VVVV 2p ooo~VVVZdoOZdododdd~~• OZÊÄ(x00 ) hhhhOZOZOZ ~~~hhhO ~~hhhh~~{zΣ00a)}b)Ðèñ.

6.3: ê äîêàçàòåëüñòâó òåîðåìû 6.1Ëåãêî âèäåòü, ÷òî ïðè ýòîì¡ ¢L Σ00 6 2q+1 + 2n−m+1 .(6.6)Èñêîìàÿ ÊÑ Σf ÿâëÿåòñÿ ðåçóëüòàòîì êîððåêòíîé ñòûêîâêè âèäà Σf = Σ00 (Σ0 ), ïîëó÷åííîé â ðåçóëüòàòå ïðèñîåäèíåíèÿ âõîäîâ ÊÑ Σ00 ê âûõîäàì ÊÑ Σ0 â ñîîòâåòñòâèè ñïðåäñòàâëåíèåì (6.4), ñëîæíîñòü êîòîðîé, â ñèëó (6.5)(6.6),óäîâëåòâîðÿåò íåðàâåíñòâóL (Σf ) 6 (p + 2)2n−m + (λ + 1)2q+1 .Èç ýòîãî íåðàâåíñòâà ïð躹§√ ¨3log n è s = n − 2 n ,m=2ïðè êîòîðûõ âûïîëíåíû óñëîâèÿ» m¼2mè q = m + p 6 n,s62 , p=s46Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìâûòåêàåò íåðàâåíñòâî (6.3) äëÿ ñëîæíîñòè Σf , òàê êàên−m(p + 2)2µµ¶¶1√1+O,n22m+s+p+36 p2s · 2m+p+2 66sµ¶√322n√6 2n− n+3 log n = o.sn n2n2n6+ 3 · 2n−m =sn(λ + 1)2q+1Òåîðåìà äîêàçàíà.Ñëåäñòâèå.

Èç (6.3) ñ ó÷åòîì íèæíåé îöåíêè (2.15) âûòåêàåò, ÷òîLK (n) ∼2n.nÇàìå÷àíèå. Ïîñòðîåííóþ ÊÑ Σf ìîæíî ðàçáèòü íà íå áîëåå,÷åìµ n ¶2pn−m+1q+1√λp · 2 + 2+ (λ + 1)2=On n¾çâåçä¿, êàæäàÿ èç êîòîðûõ ñîñòîèò èç êîíòàêòîâ îäíîãîè òîãî æå òèïà. Äëÿ ýòîãî äîñòàòî÷íî êîíòàêòû âñåõ çâåçä,ïîêàçàííûõ íà ðèñ. 6.2b, ïåðåðàñïðåäåëèòü â çâåçäû èç îäíîòèïíûõ êîíòàêòîâ, ¾öåíòðàìè¿ êîòîðûõ ÿâëÿþòñÿ âûõîäûïîäñõåì ΣG ñõåì Σ0i , i = 1, . . . , 2q−m , à ëþáîé èç îñòàëüíûõêîíòàêòîâ ÊÑ Σf ñ÷èòàòü îòäåëüíîé çâåçäîé.Ÿ7 Àñèìïòîòè÷åñêè íàèëó÷øèé ìåòîä ñèíòåçàôîðìóë â áàçèñå {&, ∨, ¬}. Ïîâåäåíèå ôóíêöèè Øåííîíà äëÿ ãëóáèíû ÔÀË.Ïðèìåíèì òåõíèêó ìîäåëèðîâàíèÿ ÔÀË èç ÄÓÌ ïåðåìåííûìè äëÿ ñèíòåçà ôîðìóë â ñòàíäàðòíîì áàçèñå.Ÿ7.

Àñèìïòîòè÷åñêè íàèëó÷øèé ìåòîä ñèíòåçà ôîðìóë 47Òåîðåìà 7.1 (ñð. [14]). Äëÿ ëþáîé ÔÀË f , f ∈ P2 (n), â UΦñóùåñòâóåò ðåàëèçóþùàÿ åå ôîðìóëà Ff , äëÿ êîòîðî鵶2n2 log log n + O (1)L (Ff ) 61+,(7.1)log nlog nD (Ff ) 6 n − log log n + 8 + o (1) .(7.2)Äîêàçàòåëüñòâî. Ïóñòü ïàðàìåòðû m, s è p óäîâëåòâîðÿþòñîîòíîøåíèÿì» m¼2ms62 , p=, p · 2s 6 n,sà G ñòàíäàðòíîå ÄÓÌ ïîðÿäêà m è âûñîòû s, äëÿ êîòîðîãî |G| = λ 6 p · 2s (ñì. Ÿ5).

Ïóñòü äàëåå q = m + λ, à∆ = (δ1 , . . . , δ2λ ) ðàçáèåíèå êóáà B q , ïîëó÷åííîå ïî ëåì−→ìå 4.1 äëÿ ñèñòåìû ÔÀË G . Äëÿ ÔÀË f (x) èç P2 (n), ãäåx = (x1 , . . . , xn ), x00 = (xq+1 , . . . , xn ) ðàññìîòðèì åå ïðåäñòàâëåíèå â âèäåf (x) =_=σ 00 =(σ=i=1i_¡ 0¢x xi=1q+1 ,...,σn )2q−m_xσq+1xq+1· · · xσnn 2q−m_i¡ 0¢¡ 0¢x fσ00,i x  =¡ ¢σq+1xq+1· · · xσnn fσ00,i x0 , (7.3)σ 00 =(σq+1 ,...,σn )ãäå x (x0 ) õàðàêòåðèñòè÷åñêàÿ ÔÀË ìíîæåñòâà δi , i = 1, . .

. , 2q−m ,iè fσ00,i (x0 ) ïðîèçâîëüíàÿ ÔÀË, ñîâïàäàþùàÿ íà δi ñ ÔÀËfσ00 (x0 ) = f (x0 , σ 00 ).e f ñ ïîäÏîñòðîèì äëÿ ÔÀË f íà îñíîâå (7.3) ôîðìóëó Fíÿòûìè îòðèöàíèÿìè, êîòîðàÿ èìååò âèäλef =F2_i=1³´b n−q x00 , Je , . . . , Je ,Ai (x0 )F0,i1,i48Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìb n−q (x00 , y0 , . .

. , y2n−q −1 ) áåñïîâòîðíàÿ ïî èíôîðìàöèãäå Fîííûì ÁÏ ôîðìóëà èç ëåììû 4.3, ðåàëèçóþùàÿ ÔÀË µn−q ,Ai , i ∈ [1, 2λ ], ñîâåðøåííàÿ ÄÍÔ ÔÀË x , à ÝÄ Jσ00,i ðàíiãà p îò ÁÏ xm+1 , . . . , xq íà êîìïîíåíòå δi ìîäåëèðóåò ÔÀËfσ00,i , ãäå σ 00 ∈ B n−q è i ∈ [1, 2λ ].b f ïîëó÷àåòñÿ èç ôîðìóëû FefÏóñòü, äàëåå, ôîðìóëà Fîïòèìèçàöèåé ïî ãëóáèíå (ñì.

Ÿ2 ãë. 2), à ôîðìóëà Ff îïòèìèçàöèåé ÝÄ ïî ÷èñëó îòðèöàíèé, òî åñòü çàìåíîé êàæäîéÝÄ Jσ00 ,i âèäà xj1 ∨. . .∨xjt ∨xjt+1 ∨. . .∨xjp , ãäå t 6 p, ôîðìóëîéJbσ00 ,i âèäà xj1 ∨ . . . ∨ xjt ∨ xjt+1 · · · xjp , êîòîðàÿ óâåëè÷èâàåò ãëóáèíó íå áîëüøå, ÷åì íà 1. Çàìåòèì, ÷òî ÷èñëî ÔÝ ¬âî âñåõ ôîðìóëàõ Ai , i ∈ [1, 2λ ], ðàâíî ïîëîâèíå èõ ñóììàðíîãî ðàíãà, ÷òî â êàæäîé ôîðìóëå âèäà Jbσ00 ,i èìååòñÿb n−q ) 6 3,îäèí ÔÝ ¬, è íàïîìíèì (ñì.

ëåììó 4.3), ÷òî Alt (Fn−qn−qb n−q ) 6 5 · 2b n−q ) 6 2 · 2 . Ñëåäîâàòåëüíî, âR(Fè L¬ (Fñèëó ëåììû 2.1 ãëàâû 2,¡¢L&,∨ (Ff ) 6 2q−m q · 2m + (p − 1)2n−q + 5 · 2n−q , (7.4)L¬ (Ff ) 6 q · 2q + 3 · 2n−m .(7.5)Âûáèðàÿ çíà÷åíèÿ ïàðàìåòðîâ m è s òàê, ÷òîm = b3 log log nc − 1,s = blog n − 2 log log nc − 1,è ïîäñòàâëÿÿ ýòè çíà÷åíèÿ â (7.4), (7.5), ïîëó÷èì íåðàâåíñòâîµ n ¶22n+O,L (Ff ) 6log n − 2 log log nlog2 nèç êîòîðîãî äëÿ ñëîæíîñòè ôîðìóëû Ff ñëåäóåò îöåíêà (7.1).Ïðè ýòîì èç (7.1), ó÷èòûâàÿ òî, ÷òî³ ´b f ) 6 2L(Ff ), D(Ff ) 6 D(Fb f ) + 1 è Alt Fb f 6 6,L(Fñ ïîìîùüþ òåîðåìû 2.1 èç Ÿ2 ãëàâû 2 íåïîñðåäñòâåííî âûâîäèòñÿ íåðàâåíñòâî (7.2).Òåîðåìà äîêàçàíà.Ÿ8. Ñèíòåç ñõåì äëÿ ÔÀË èç ñïåöèàëüíûõ êëàññîâ49Ñëåäñòâèå.

Èç (7.1) è (7.2), ñ ó÷åòîì íèæíèõ îöåíîê (2.14)è (2.20), âûòåêàåò, ÷òîLΦ (n) ∼2n,log nD (n) = n − log log n ± O (1) .Ÿ8 Ñèíòåç ñõåì äëÿ ÔÀË èç ñïåöèàëüíûõêëàññîâ. Îöåíêè ñëîæíîñòè èíäèâèäóàëüíûõÔÀË, ìèíèìàëüíîñòü íåêîòîðûõ ñõåì.Ìîùíîñòíûå ñîîáðàæåíèÿ ìîæíî èñïîëüçîâàòü ïðè ïîëó÷åíèè íèæíèõ îöåíîê äëÿ ôóíêöèé Øåííîíà, ñâÿçàííûõ ñ ðåàëèçàöèåé ÔÀË èç êëàññà Q, Q = Q (1) , Q (2) , .

. .. . . , Q (n) , . . . , ãäåQ ⊆ P2 è Q (n) = Q ∩ P2 (n) ,n = 1, 2, . . . .Ïóñòü U îäèí èç ðàññìîòðåííûõ â ãëàâå 2 êëàññîâ ñõåì,Ψ ââåäåííûé òàì ôóíêöèîíàë ñëîæíîñòè, à Ψ (Q (n)) ôóíêöèÿ Øåííîíà (äëÿ êëàññà ñõåì U îòíîñèòåëüíî ôóíêöèîíàëà ñëîæíîñòè Ψ), ñâÿçàííàÿ ñ êëàññîì ÔÀË Q, òî åñòüΨ (Q (n)) = max Ψ (f ) .f ∈Q(n)Ñëåäóþùåå ¾ìîùíîñòíîå¿ íåðàâåíñòâî îáîáùàåò ðàâåíñòâî (2.4)è âûòåêàåò íåïîñðåäñòâåííî èç îïðåäåëåíèé:kU (Ψ (Q (n)) , n)k > |Q (n)| .(8.1)Îíî ïîçâîëÿåò ïîëó÷èòü íèæíþþ îöåíêó ôóíêöèè Øåííîíà Ψ (Q (n)) íà îñíîâå èçâåñòíîé âåðõíåé îöåíêè âåëè÷èíûkU (Ψ, n)k.Ðàññìîòðèì, â ÷àñòíîñòè, íèæíèå ìîùíîñòíûå îöåíêèäëÿ ôóíêöèé LC (Q (n)) è LK (Q (n)), òî åñòü ôóíêöèé Øåííîíà äëÿ ñëîæíîñòè ðåàëèçàöèè ÔÀË èç êëàññà Q ñõåìàìè50Ãëàâà 3.

Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìèç êëàññîâ UC è UK ñîîòâåòñòâåííî. Íà îñíîâå ìîùíîñòíûõñîîáðàæåíèé (ñì. (8.1)) àíàëîãè÷íî òîìó, êàê ýòî áûëî ñäåëàíî â òåîðåìå 2.1 äëÿ ñëó÷àÿ Q = P2 , äîêàçûâàåòñÿ ñëåäóþùåå óòâåðæäåíèå.Ëåììà8.1. ´Äëÿ êëàññà ÔÀË Q òàêîãî, ÷òî n =³= o loglog|Q(n)|log|Q(n)| (log n = o (log log |Q(n)|)), âûïîëíÿþòñÿ ñëåäóþùèå àñèìïòîòè÷åñêèå íåðàâåíñòâàLC (Q (n)) &log |Q (n)|,log log |Q(n)|(ñîîòâåòñòâåííî LK (Q (n)) &(8.2)log |Q (n)|).log log |Q(n)|(8.3)Ïóñòü, íàïðèìåð, êëàññ Q ñîñòîèò èç âñåõ ÔÀË, ñèììåòðè÷íûõ ïî ïåðâûì äâóì ÁÏ. Ëåãêî âèäåòü, ÷òî ïðè ýòîì3 n|Q (n)| = 2 4 2 , òàê êàê f ∈ Q(n) òîãäà è òîëüêî òîãäà, êîãäàâòîðàÿ è òðåòüÿ ÷åòâåðòè ñòîëáöà çíà÷åíèé αef ñîâïàäàþò.Ñëåäîâàòåëüíî, â ñèëó ëåììû 8.1, îòñþäà âûòåêàåò, ÷òîLC (Q(n)) &3 2n· ,4 nLK (Q (n)) &3 2n· .4 n(8.4)Îïèñàííûå âûøå àñèìïòîòè÷åñêè íàèëó÷øèå ìåòîäû ñèíòåçà ñõåì îðèåíòèðîâàíû, âîîáùå ãîâîðÿ, íà ïðîèçâîëüíóþèëè ñàìóþ ¾ñëîæíóþ¿ ÔÀË.

Òåì íå ìåíåå, âî ìíîãèõ ñëó÷àÿõ îíè ñëóæàò îñíîâîé àñèìïòîòè÷åñêè íàèëó÷øåãî ìåòîäàñèíòåçà ÑÔÝ èëè ÊÑ äëÿ ÔÀË èç çàäàííîãî ñïåöèàëüíîãîêëàññà Q è ïîçâîëÿþò óñòàíîâèòü äëÿ ýòîãî êëàññà ¾ñòàíäàðòíóþ¿ (ñì. (8.2) è (8.3)) àñèìïòîòèêó âèäàLC (Q(n)) ∼log log |Q(n)|,log |Q(n)|(8.5)LK (Q(n)) ∼log log |Q(n)|.log |Q(n)|(8.6)Ÿ8. Ñèíòåç ñõåì äëÿ ÔÀË èç ñïåöèàëüíûõ êëàññîâ51Çàìåòèì, ÷òî àñèìïòîòèêà (8.5) óñòàíàâëèâàåòñÿ, êàê ïðàâèëî, ïóòåì ñâåäåíèÿ çàäà÷è ñèíòåçà ÑÔÝ äëÿ ëþáîé ÔÀËèç Q(n) ê çàäà÷å ñèíòåçà ÑÔÝ äëÿ ñèñòåìû èç îäíîé èëèíåñêîëüêèõ ïðîèçâîëüíûõ ÔÀË îò ìåíüøåãî ÷èñëà ÁÏ. Ïðèýòîì òðåáóåòñÿ, ÷òîáû äâîè÷íûé ëîãàðèôì ÷èñëà òåõ ñèñòåì ÔÀË, ê ðåàëèçàöèè êîòîðûõ ñâîäèòñÿ ðåàëèçàöèÿ ÔÀËèç Q(n), áûë àñèìïòîòè÷åñêè ðàâåí log |Q(n)|, à ñëîæíîñòüâñïîìîãàòåëüíûõ ÔÀË, îáåñïå÷èâàþùèõ äàííîå ñâåäåíèå,áûëà áû ñóùåñòâåííî ìåíüøå ïðàâîé ÷àñòè (8.5).

Àíàëîãè÷íûì îáðàçîì îáñòîèò äåëî ñ êëàññîì ÊÑ.Âîçüìåì â êà÷åñòâå ïðèìåðà ââåäåííûé âûøå êëàññ ÔÀËQ, ñîñòîÿùèé èç âñåõ ÔÀË, ñèììåòðè÷íûõ ïî ïåðâûì äâóìÁÏ, è äîêàæåì, ÷òîLC (Q (n)) .3 2n· ,4 nòî åñòü, ñ ó÷åòîì (8.3), óñòàíîâèì äëÿ íåãî àñèìïòîòèêó (8.5)âèäà3 2nLC (Q (n)) ∼ · .4 nÄåéñòâèòåëüíî, ðàçëàãàÿ ÔÀË f (x1 , . . . , xn ) èç Q (n) ïî ÁÏx1 , x2 , ïîëó÷èì_¡¢¡ ¢f x1 , x2 , x0 =xσ1 1 xσ2 2 fσ1 ,σ2 x0 ,(8.7)(σ1 ,σ2 )∈B 2ãäå x0 = (x3 , . . .

, xn ) è fσ1 ,σ2 (x0 ) = fσ1 ,σ2 (σ1 , σ2 , x0 ), ïðè÷åìf01 = f10 â ñèëó ñèììåòðè÷íîñòè ÔÀË f ïî ÁÏ x1 , x2 . Èñêîìàÿ ÑÔÝ Σf ðåàëèçóåò ÔÀË f â ñîîòâåòñòâèè ñ (8.7) è èìååòâèä Σf = Σ00 (Σ0 ), ãäå Σ00 ìóëüòèïëåêñîðíàÿ ÑÔÝ ïîðÿäêà 2 îò àäðåñíûõ ÁÏ x1 , x2 , à ÑÔÝ Σ0 îò ÁÏ x0 ðåàëèçóåòàñèìïòîòè÷åñêè íàèëó÷øèì ñïîñîáîì ÔÀË f00 , f01 = f10è f11 îò ÁÏ x0 .