Материалы для подготовки к экзамену (2012-2013 учебный год), страница 5

, Yd ), множества Y называется величинаdX|Yi ||Yi |H(D) = −log.|Y ||Y |i=1§4.23Заметим, что энтропия вырожденного разбиения, при котором d = 1, равнанулю, а энтропия тривиального разбиения, при котором d = p, равна log p. Можно показать, что 0 6 H(D) 6 log d для любого разбиения D множества Y на dкомпонент.Отметим также, что энтропия разбиения D из замечания 2 к лемме 3.1 равнаtXlog(2t)i=12t+log 2log t=+ 1.22Теорема 3.1. Если D = (Y1 , . . . , Yd ) — селекторное разбиение БП ФАЛ ϕ(y1 , .

. . , yp ),и s > log p, а p(s − H(D)) > 2m , то найдётся ϕ–УМ G порядка m такое, что1) |G| 6 2s+2 ;→−2) LA ( G ) 6 eA · |G| + O(d · 2m+s/2 ), где A ∈ {К, C}.Доказательство. Выберем для каждого i, 1 6 i 6 d, чётное число si такое, чтоs + logpipi6 si 6 s + log + 2,ppгде pi = |Yi |, и убедимся в том, что выполнено неравенство s1 p1 + · · · + sd pd > 2m .Действительно,pipipisi pi > pi (s + log ) = pi s + p · logpppи, следовательно,dXi=1si pi >dXi=1pi s + p ·dXpii=1plogpi= p(s − H(D)) > 2m .pОсталось воспользоваться леммой 3.1 и построить ϕ–УМ G, удовлетворяющее неравенствам (3.4) и (3.5), из которых следует, что|G| 6 2s1 + · · · + 2sp 6 2s+2dXpii=1p= 2s+2→−и что сложность LA ( G ) удовлетворяет второму условию теоремы.Теорема доказана.§4Асимптотические оценки высокой степени точности для сложности итеративных контактных схем и контактных схем из ориентированных контактовИспользуем приведённые в §3 ϕ–УМ и схемы, которые их реализуют, для синтезаИКС и КС из ориентированных контактов.24Глава 1.Рис.

4.1: Реализация ФАЛ ϕ(y1 , . . . , yp ) с помощью ИКС и КС из ориентированныхконтактовТеорема 4.1. Для любой ФАЛ f , f ∈ P2 (n), существует реализующая её ИКС Σfтакая, что!5logn+O(1)2n−11+ 2.(4.1)L(Σf ) 6nnДоказательство. Выберем натуральный параметр q, q < n, выделим из набораБП x = (x1 , . . . , xn ) поднаборы x0 = (x1 , . . .

, xq ), x00 = (xq+1 , . . . , xn ) и рассмотримразложение ФАЛ f (x) по БП x00 (разложение Шеннона)_f (x) =Kσ00 (x00 ) · fσ00 (x0 ),(4.2)σ 00 ∈B n−qгде fσ00 (x0 ) = f (x0 , σ 00 ) для любого набора σ 00 из B n−q .Положим p = 2t и рассмотрим введённую в §3 ФАЛ ϕ(y1 , . . .

, yp ) = y1 yt+1 ∨ . . . ∨∨ yt y2t с селекторным разбиением D = ({y1 }, . . . , {yt }, {yt+1 , . . . y2t }) её БП, энтропия которого равна 1 + (log t)/2. Выберем, далее, параметры s и t такие, чтоlog t2t s −− 1 > 2q ,(4.3)2и по теореме 3.1 построим на основе разбиения D ϕ–УМ G = G(1) ∪ · · · ∪ G(t+1)порядка q такое, что|G| 6 2s+2 ,→−LК G 6 2|G| + O t · 2q+s/2(4.4)и что любые две ФАЛ из различных множеств G(j) , j = 1, . . . , t, ортогональны.Пусть (1, |G|)–КС ΣG реализует систему ФАЛ G со сложностью, удовлетвоb t, Σbt =ряющей (4.4). Для реализации ФАЛ ϕ будем использовать (t, 1)–КС ΣbΣt (y1 , .

. . , yt ; yt+1 , . . . , y2t ; z) с «управляющими» итеративными входами y1 , . . . , yt ,«проводящими» входами yt+1 , . . . , y2t и выходом z, которая представляет собой«звезду» из t контактов, где контакт с номером j, j = 1, . . . , t, соединяет вход yt+jс выходом z и управляется входной БП yj (см. рис. 4.1а).В силу ϕ–универсальности множества ФАЛ G и особенностей его структурыдля любой ФАЛ g(x0 ) справедливо представлениеg x0 = ϕ g (1) , . . .

, g (p)(4.5)§4.25где g (j) ∈ G(j) для всех j, j = 1, . . . , t, и g (j) ∈ G(t+1) , если j > t + 1. Заметим, чтоb t присодля реализации данного представления достаточно входы y1 , . . . , yp КС Σединить к выходам КС ΣG в соответствии с (4.5) и что указанная реализация является корректной суперпозицией соответствующих схем в силу ортогональностиФАЛ из различных множеств G(j) , j = 1, . . . , t.Пусть ИКС Σ0 от БП x0 содержит в качестве подсхемы КС ΣG и реализуеткаждую ФАЛ fσ00 (x0 ), σ 00 ∈ B n−q , на одном из своих 2n−q выходов согласно (4.5),b t , входы которой присоединены к выходам ΣG соотиспользуя для этого схему Σветствующим образом.Искомая ИКС Σf , содержит ИКС Σ0 в качестве подсхемы и представляет собой результат корректной суперпозиции вида Σf = Σ00 (Σ0 ), где Σ00 — (2n−q , 1)–контактное дерево от БП x00 входы (листья) которого присоединены к выходам Σ0в соответствии с (4.2).Сложности ИКС Σ0 и КС Σ00 удовлетворяют неравенствамL Σ0 6 L(ΣG ) + 2n−q · t,L Σ00 6 2n−q+1и, следовательно, в силу (4.4)L Σf 6 2n−q · t + O 2n−q + O 2s + t · 2q+s/2 .Оценка (4.1) получается из последнего неравенства при следующих значенияхпараметров&'2q−1q = d2 log ne , s = dn − 2 log ne , t =,s − log2 n − 1при которых, начиная с достаточно большого n, выполнены все необходимые соотношения и, в частности, неравенство (4.3).Теорема доказана.Следствие.

Из (4.1) с учётом нижней оценки (1.19) вытекает соотношение!52n−1ИКС2 log n ± O(1)L(n) =1+nnНапомним, далее, что (см., например, [ ]) множество δ, δ ⊆ B q называется mрегулярным множеством наборов куба B q , если m < q, |δ| = 2m и все префиксы1 длины m наборов из δ различны. Заметим, что m-регулярному множеству δ,δ ⊆ B q , можно взаимнооднозначно сопоставить систему ФАЛ ψ = (ψ1 , . . . , ψq−m ) изP2q−m (m) так, что набор α = (β, γ), где β ∈ B m и γ ∈ B q−m , принадлежит δ тогда1Для слова (набора) α вида α = βγ слово β (γ) считается его префиксом (соответственносуффиксом).26Глава 1.и только тогда, когда ψ(β) = γ. Заметим также, что любая ФАЛ g, g ∈ P2 (q), совпадает на m-регулярном множестве наборов δ, δ ⊆ B q , с некоторой ФАЛ из P2 (m),если рассматривать P2 (m) как множество всех ФАЛ из P2 (q) с несущественнымиБП xm+1 , .

. . , xq . При этом любая ФАЛ из связанной с δ системы функций совпадает на δ с соответствующей БП куба B q .Для наборов β = (β1 , . . . , βq ) и α = (α1 , . . . , αq ) через β ⊕ α будем обозначатьнабор вида (β1 ⊕ α1 , . . . , βq ⊕ αq ). Для множества δ, δ ⊆ B q , и набора α, α ∈ B q ,определим множество δ ⊕ α как множество различных наборов вида β ⊕ α, гдеβ ∈ δ, то есть множество, получающееся из δ сдвигом (параллельным переносом) нанабор α. Заметим, что для m-регулярного множества δ, δ ⊆ B q , и любого набора α,α ∈ B q , множество δ⊕α также является m-регулярным.

Если при этом ν(α) < 2q−m ,то естьα = (0, . . . , 0, γ),| {z }mгде γ = (γ1 , . . . , γq−m ) и ν(γ) = ν(α), а множество наборов δ соответствует системеФАЛ g = (g1 , . . . , gq−m ), то множество наборов δ ⊕ α будет соответствовать системеФАЛ g ⊕ γ = (g1 ⊕ γ1 , . . . , gq−m ⊕ γq−m ), получающейся из системы g инвертированием некоторых ФАЛ.Напомним (см. [ ]), что для любой системы ФАЛ g = (g1 , . . . , gλ ), g ∈ P2 (m),и q = m + λ система ∆ = (δ1 , . . . , δ2λ ) подмножеств единичного куба B q , где прилюбом i, i ∈ [1, 2λ ], и γ = ν −1 (i − 1) множество δi соответствует системе ФАЛ g ⊕ γ,является разбиением данного куба.

При этом, очевидно, ФАЛ g, j = 1, . . . , λ, наαjкомноненте δi , 1 6 i = ν −1 (α1 , . . . , αλ ) + 1 6 2λ , совпадает с буквой xm+j.Теорема 4.2. Для любой ФАЛ f , f ∈ P2 (n), существует реализующая её КС Σfиз ориентированных контактов такая, что2n2 log n + O(1)L(Σf ) 61+.(4.6)nnДоказательство. Выберем натуральные параметры m, t, q и чётное число s так,что m2s 6 2m ,t=,q =m+t6n(4.7)sДля p = 2t и указанной в доказательстве теоремы 4.1 ФАЛ ϕ(y1 , . . . , yp ) с селекторным разбиением D = ({y1 }, .

. . , {yt }, {yt+1 , . . . , y2t }) её БП построим по лемме 3.1,где s1 = · · · = st = 0 и st+1 = s, ϕ–УМ G = G(1) ∪ · · · ∪ G(t) ∪ G(t+1) порядка m.Из замечания 1 к лемме 3.1 следует, что множество G(j) , j = 1, . . . , t, состоитиз единственной ФАЛ ψj , а для множества ФАЛ H = G(t+1) в силу (3.4), (3.5)→−существует (1, λ)–КС ΣH , где λ = |H| 6 2s , которая реализует систему ФАЛ H идля которойL(ΣH ) 6 2s+1 + O(t · 2m+s/2 ).(4.8)§4.27При этом в силу ϕ–универсальности множества ФАЛ G для любой ФАЛ g из P2 (m)справедливо представлениеg = ϕ ψ1 , . . .

, ψt , , h(t+1) , . . . , h(2t) ,(4.9)где ФАЛ h(t+1) , . . . , h(2t) берутся из H.Пусть, по-прежнему, x0 = (x1 , . . . , xq ), а ∆ = (δ1 , . . . , δ2t ) — разбиение куба B q отБП x0 , связанное с «моделированием» системы ФАЛ ψ = (ψ1 , . . . , ψt ), для которогопри любом i, 1 6 i = ν −1 (α1 , .

. . , αt ) + 1 6 2t , и любом j, 1 6 j 6 t, ФАЛ ψjαjсовпадает на δi с буквой xm+j. Следовательно, любоая ФАЛ g(x0 ) в силу (4.9) и всилу m–регулярности при любом i, 1 6 i 6 ν−1(α1 , . . . , αt ) + 1 6 2t , компоненты δiсовпадает на ней с ФАЛ(t+1)(2t) t1, . . . , xαm+t, hi, . .

. , hi,(4.10)gi x0 = ϕ xαm+1(t+1)(2t)где все ФАЛ hi, . . . , hi принадлежат множеству H.Полагая, как и раньше, x00 = (xq+1 , . . . , xn ), продолжим разложение (4.3)ФАЛ f (x0 , x00 ) следующим образомt000f (x , x ) =2_i=1x (x0 )i_Kσ00 (x00 ) · fσ00 ,i (x0 ) ,(4.11)σ 00 ∈B n−qгде x (x0 ) — характеристическая ФАЛ компоненты δi , i = 1, . . . , 2t , а ФАЛ fσ00 ,i (x0 ),iσ 00 ∈ B n−q , имеет вид правой части равенства (4.10) для ФАЛ fσ00 (x0 ).Пусть (1, 2t+n−q )–КС Σ0 от БП x0 содержит в качестве подсхемы КС ΣH и реализует каждую ФАЛ fσ00 ,i на одном из своих выходов согласно (4.10), используядля этого ориентированную КС Σ̌t (см.

рис. 4.1б), контакты которой управляют1tся буквами xαm+1, . . . , xαm+t, а проводящие входы yt+1 , . . . , y2t присоединены к соответствующим входам КС ΣH . Заметим, что правильность и корректность всехуказанных суперпозиций КС обеспечивается разделительностью КС Σ̌t по входам.e получается из (2q , 1)–КД от БП x0 отождествлениемПусть, далее, (2t , 1)–КС Σдля каждого i, i = 1, .

. . , 2t , тех его листьев, которые соответствуют конъюнкциямσвида xσ1 1 · · · · · xq q , где (σ1 , . . . , σq ) ∈ δi . Построим, наконец, (2t+n−q , 1)–КС Σ00 , котоe выхода (корня)рая получается в результате присоединения к каждому входу КС Σn−q00(2 , 1)–контактного дерева от БП x . Заметим, что все операции суперпозиции,использованные при построении КС Σ00 , являются корректными и поэтому Σ00 разделительна по входам, а система ФАЛ проводимости между её входами и выходомсостоит из всех ФАЛ вида x (x0 ) · Kσ00 (x00 ), где i ∈ [1, 2t ] и σ 00 ∈ B n−q .iИскомая КС Σf содержит КС Σ0 в качестве подсхемы и представляет собойрезультат суперпозиции вида Σf = Σ00 (Σ0 ), при выполнении которой входы Σ00присоединяются к выходам Σ0 в соответствии с (4.11).