OK_metodichka_part_3 (1132798), страница 4
Текст из файла (страница 4)
4§32n,nLC (n) . 82n.nРегулярные разбиения единичного куба и моделирование функций переменными. Асимптотика сложности контактного дешифратораПостроенное в §4 для синтеза СФЭ ДУМ G будем использовать и далее (см. §5–§7), хотя прямая реализация представления (4.1) в других классах схем не всегда возможна. Так, при синтезе формул (КС) все ФАЛ (соответственночасть ФАЛ) множества G должны быть «промоделированы» переменными или их отрицаниями. Для реализации такого моделирования в данном параграфе строятся специальные разбиения единичного куба, а затем рассматриваютсясвязанные с ними разложения ФАЛ, на основе которых синтезируются формулы в базисе {&, ∨, ¬}, являющиеся асимптотически оптимальными и по сложности, и по глубине дляпочти всех функций.Множество δ, δ ⊆ B q , называется m-регулярным множеством наборов куба B q , если m < q, |δ| = 2m и всепрефиксы1 длины m наборов из δ различны.
Заметим, чтоm-регулярному множеству δ, δ ⊆ B q , можно взаимнооднозначно сопоставить систему ФАЛ ψ = (ψ1 , . . . , ψq−m ) изP2q−m (m) так, что набор α = (β, γ), где β ∈ B m и γ ∈ B q−m ,принадлежит δ тогда и только тогда, когда ψ (β) = γ. Заметим также, что любая ФАЛ g, g ∈ P2 (q), совпадает наm-регулярном множестве наборов δ, δ ⊆ B q , с некоторойФАЛ из P2 (m), если рассматривать P2 (m) как множество1Для слова (набора) α вида α = βγ слово β (γ) считается его префиксом (соответственно суффиксом).§3. Регулярные разбиения единичного куба27всех ФАЛ из 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 ), то множество наборов δ ⊕ α будет соответствовать системе ФАЛ(g1 ⊕ γ1 , . . . , gq−m ⊕ γq−m ), получающейся из системы g инвертированием некоторых ФАЛ.Лемма 3.1. Для любых натуральных m, λ и q = m + λ идля любой системы ФАЛ g = (g1 , . . . , gλ ) из P2λ (m) существует m-регулярное разбиение ∆ = (δ1 , . . . , δ2q−m ) куба B qтакое, что любая ФАЛ gi на любой компоненте δj совпадает либо с одной из БП xm+1 , .
. . , xq , либо с её отрицанием.Доказательство. Пусть δ = δ1 — m-регулярное множество,соответствующее системе ФАЛ g = (g1 , . . . , gλ ), и пусть δi =δ1 ⊕ α, где ν(α) = i − 1, для всех i, i = 1, . . . , 2q−m . Из построения системы множеств ∆ = (δ1 , . . . , δ2q−m ) следует, чтокаждое из них обладает требуемым свойствами, связаннымис можелированием ФАЛ из g с помощью БП.Покажем теперь, что ∆ — покрытие куба B q . Для этоговозьмем произвольный набор из B q вида (β, γ), где β ∈ B m28Глава 3. Синтез и сложность управляющих системи γ ∈ B q−m , а по нему найдем в множестве δ набор вида(β, γb), который имеется в δ в силу m-регулярности этогомножества.
Следовательно,(β, γ) = (β, γb) ⊕ (0, . . . , 0, γb ⊕ γ) = (β, γb) ⊕ α,| {z }mгде ν (α) < 2q−m . Таким образом, система ∆ образует покрытие куба B m .С другой стороны, из m-регулярности δ следует m-регулярность любого из множеств δi , i = 1, . . . , 2q−m , и поэтомуq−m2X|δi | = 2m 2q−m = 2q .i=1Следовательно, система ∆ образует разбиение куба B q .Лемма доказана.→−Лемма 3.2 (ср. [14]). Для системы ФАЛ Q n при n = 1, 2, 3, .
. .выполняется неравенство n→ 2nК −Qn 6 2 + OL(3.1)nДоказательство. Выберем параметры m, q и λ так, чтоλ = 2n ,q = m + λ и q 6 n,(3.2)а затем рассмотрим m-регулярное множество наборов δ1 куба B q от БП x0 = (x1 , . . . , xq ), связанное с системой ФАЛ→−Q m (x1 , . . . , xm ), которая состоит из всех ЭК вида xσ1 1 · · · xσmm ,где ν(σ1 , .
. . , σm ) = j − 1, j ∈ [1, λ]. Построим для этойсистемы по лемме ?? разбиение ∆ = (δ1 , . . . , δ2q−m ) кубаσB q и заметим, что любая ЭК K(x0 ) = xσ1 1 · · · xq q , где σ 0 =(σ1 , . . . , σq ) ∈ δi , совпадает на множестве δi с одной из ЭК§3. Регулярные разбиения единичного куба29→−α 0системы Q m , то есть совпадет на нем с буквой xj σ0 , гдеσm + 1 6 jσ0 6 q, ασ0 ∈ B.Пусть, далее (1, 2λ )-КС Σ0 реализует столбец из ФАЛχ1 , . . . , χ2λ , где χi (x0 ) — характеристическая ФАЛ множества δi , i ∈ 1, 2λ и получается из (1, 2q )-КД от БП x0 в результате соответствующего отождествления выходов (см. рис. ??).Заметим, что в силу указанных выше свойств разбиения ∆любая ЭК K = xσ1 1 · · · xσnn , где σ 0 = (σ1 , . . .
, σq ) ∈ δi , 1 6 i 62λ , может быть представлена в видеαK = χi (x0 ) · xj σ0 · Kσ00 (x00 ),0σ(3.3)где x00 = (xq + 1, . . . , xn ), σ 00 = (σq+1 , . . . , σn ).→−(&)Искомая (1, 2n )-КС Σn реализует каждую ЭК из Q m всоответствии с (3.3) и имеет вид, показанный на рис. ??.Пологаяm = blog (n − 3 log n)cполучим, чтоλ = 2m 6 n − 3 log n,2mq = m + λ 6 n − 2 log n,n − 3 log n>,2(&)то сложность построенной (1, 2n )-КС Σn , являющейся контактным дешифратором порядка n, удовлетворяет неравенствам: n2(&)n−mn−m+1q+1nL Σn6 λ2+2+262 +O,nиз которых вытекает неравенство 3.1.Лемма доказана.Замечание.
Если систему характеристических ФАЛ (χ1 , . . . , χ2λ )(&)реализовать по методу каскадов, то полученная КС Σ̃n будет каскадной [12], сложность которой удовлетворяет 3.1.30Глава 3. Синтез и сложность управляющих систем•appp 0ppffkk •pfNpNfpfff • a1~kkkkNNxNm+2 ..~kkkN .k~~ NNNN xk~kxm+p NN•YYYYYNYNYN k1 kkkk~~.00~kSe..eeeepepepp•SSSSS КД(x )~~~SSSxm+1 ppp•~~SSSpppp~SSSSpNfpfpxffff•~~Nfp•S~SNNNm+2 ..~~N .~xm+p NN~~•.~..@@a •~КД(x0 )@@xm+1 ppp•@@ppfff•@@kkfNpNfpNfxfm+2@@kk•pkkk@@NNN ...NNNkk@@kkkxm+p NNNkkN@@•YYYYYYNYN kkk..@@eeepSk•SКД(x00 ).@@ eeepepppx SSSSSSxm+1 ppp•SSS@@ pp2pppfff•SSS@@SSS •pfNpNfpfxfm+2SNNN ..N .{z}|xm+p NN a• p·2n−m −1xm+1b 00ΣРис.
3.1: к доказательству леммы 3.2Следствие 1. Оценки леммы 3.2 и следствия из леммы1.5 дают асимптотическое равенствоLК (Qn ) ∼ 2nСледствие 2.nπ (µn ) 6 2 · 2 + O2nnЛемма 3.3. Для любого n, n > 5 существуют бесповторные по БП y0 , . . . , y2n −1 формулы ∩Fn (x1 , . . . , xn , y0 , . . . , y2n −1 )и F̂n (x1 , . . . , xn , y0 , . . . , y2n −1 ) с поднятыми отрицаниями, которые реализуют µn и для которыхL (∩Fn ) 6 9 · 2n ,D (∩Fn ) 6 n + 9,(3.4)§4.
Нижние мощностные оценки функций Шеннона n 2L&, ∨ F̂n 6 2n+1 + On31(3.5)Доказательство. Используя представление (3.3) построимдля ФАЛ µn формулу F̃n следующим образомF̃n (x1 , . . . , xn , y0 , . . . , y2n −1 ) =λ___α 0=Ai x0 Kσ00 (x00 ) · xj σ0 yν(σ0 ,σ00 ) i=1σ 00 ∈B n−qσ 0 ∈δiσ(3.6)где Ai — совершенная ДНФ ФАЛ χi , i = 1, . . .
, λ. Легковидеть, что F̃n реализует мультиплексорную ФАЛ µn , бесповторна по БП y0 , . . . , y2n −1 и что Alt (F̃n ) 6 5.Пусть, далее, формула ∩Fn получается в результате оптимизации формулы ∩Fn по глубине. Тогда, при значенияхпараметров из предыдущего утверждения сложность и глубина ∩Fn будет удовлетворять (3.4).Формула F̂n строится на основе представления (3.6), вкотором разложение по БП x00 реализуется на базе контактного дерева так, как это было сделано при доказательствелеммы 3.23.2. При этом сложность формулы F̂n будет удовлетворять (3.5), если m = dlog (n − 4 log n)e.Лемма доказана.Следствие 3.LС (µn ) 6 2n+1 + O§42nnНижние мощностные оценкифункций ШеннонаУстановим ряд нижних оценок для введенных в §1 функций Шеннона.
Все эти оценки получены с помощью мощ-32Глава 3. Синтез и сложность управляющих системностного метода, предложенного Шенноном [32, 14], который основан на том, что число ФАЛ от БП x1 , . . . , xn неможет быть меньше числа тех попарно не эквивалентныхсхем, сложность которых не превосходит значения соответствующей функции Шеннона от аргумента n.Пусть U — один из рассмотренных в главе 2 классов схем,Ψ — введенный там функционал сложности, а Ψ (n) — функция Шеннона для класса U относительно Ψ.
Обозначим через U (Ψ, n) множество тех схем Σ, Σ ∈ U, которые реализуют одну ФАЛ из P2 (n) и для которых Ψ (Σ) 6 Ψ. Следующее «мощностное» равенство вытекает непосредственно изопределений:nkU (Ψ (n) , n)k = 22 .(4.1)Заметим также, что если для некоторого натурального n иb δ, где 0 < δ < 1, выполняется неравендействительных Ψ,ство nbbΨ,n(4.2)U 6 δ · 22 , то Ψ(f ) > Ψnдля не менее чем (1 − δ) · 22 ФАЛ f из P2 (n).Верхние оценки величины kU(Ψ, n)k, установленные вглаве 2 для различных классов схем и функционалов сложности, а также соотношения (4.1)–(4.2) служат основой дляполучения нижних мощностных оценок соответствующих функций Шеннона и сложности почти всех ФАЛ.
Напомним, что(см. леммы 2.3, 2.4, 6.2, 6.3 из главы 2) для любых натуральных n и L справедливы неравенства: CU (L, n) 6 (8 (L + n))L+1 , ΦU (L, n) 6 (8n)L+1 , KU (L, n) 6 (8nL)L ,πL|U (L, n)| 6 (16n) .(4.3)(4.4)(4.5)(4.6)§4. Нижние мощностные оценки функций Шеннона33Лемма 4.1. Для положительных действительных чиселa, y, q из неравенств(ay)y > q,a log q > 1,(4.7)следует неравенствоlog qy>log (a log q)log log (a log q)1+log (ae log q),(4.8)где e — основание натуральных логарифмов, а из неравенствa > 1, ay > q — неравенствоy>log q.log a(4.9)Доказательство. Рассмотрим сначала случай, когда a = 1и log q > 1. В этом случае неравенство (4.8) следует из того,что левая часть (4.7) монотонно возрастает по y, и дляy 0 = (1 + ε)log q,log log qгдеlog log log q,log (e log q)справедливы соотношенияε=y 0 log y 0 =log q(log log q − log log log q + log e ln (1 + ε)) 6log log qε log elog log log q+=6 log q (1 + ε) 1 −log log qlog log q= log q (1 + ε) (1 − ε) = log q 1 − ε2 6 log q.= (1 + ε)Заметим, что в случае a > 0 неравенство (4.7) эквивалентнонеравенству(ay)ay > q a ,34Глава 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
