О.Б. Лупанов - Элементы математической кибернетики (1161667), страница 4
Текст из файла (страница 4)
. , αr−1 , 1),(α1 , α2 , . . . , αr−1 , 0).17Наборы из разных сфер имеют либо совпадающие первые r − 1 компонент, а последние — отличающиеся, либо наоборот, совпадающие последние, а первые r − 1 — отличающиеся. Но одновременно совпадатьпервые r − 1 компонент и последние не могут. Итак, общих точек усфер нет.2) Так как количество сфер 2r /r, а каждая сфера содержит r наборов, то всего 2r наборов размещено в сферах. Это в точности количество всех двоичных наборов длины r. Значит, каждый набор длины rнаходится в одной из сфер. Лемма доказана.Пусть (α1 , α2 , . .
. , αr ) — центр одной из сфер. Сфера содержит rнаборов(α1 , α2 , . . . , αr ), (α1 , α2 , . . . , αr ), . . . , (α1 , α2 , . . . , αr ).Рассмотрим характеристическую функцию сферы — функцию, принимающую единичное значение на указанных наборах, и нулевую востальных случаях:ϕ(x1 , . . . , xr ) = xα1 1 xα2 2 · · · xαr r ∨ xα1 1 xα2 2 · · · xαr r ∨ · · · ∨ xα1 1 xα2 2 · · · xαr r .Характеристическая функция сферы с центром (α1 , α2 , . . . , αr ) обладает следующими свойствами.αi−1 αi αi+1xi xi+1 · · · xαr r , i ∈ 1, r.1) ϕ(x1 , . . . , xr )xαi i = xα1 1 · · · xi−1α2) ϕ(x1 , .
. . , xr )xαi i xj j = 0, i 6= j.Функция ϕ(x1 , . . . , xr ) реализуется контактной схемой сложностиr 2 . На выходе этой схемы построим (1, 2q )–полюсное разделительноеконтактное дерево Sq по переменным (y1 , . . . , yq ). К каждому выходуSq навесим r контактов xα1 1 , . . . , xαr r (см. рис. 10).Всего у полученной схемы S будет r2q полюсов–выходов, и реализовывать она будет всевозможные конъюнкции видаααi−1 αii+1ϕ(x1 , . . . , xr ) · y1β1 · · · yqβq · xαi i = xα1 1 · · · xi−1xi xi+1· · · xαr r · y1β1 · · · yqβq .Используем (2) в оценке сложности S:LK (S) 6 r 2 + 2q+1 − 2 + r2q .(5)Схемы аналогичные S построим параллельно для каждой из 2r /rсфер.
Так будут покрыты все наборы длины r: при подстановке набораиз i–й сферы в функцию, реализованную j–й схемой, получится нуль,и только если подставить этот набор в функцию, реализованную i–й18❡ϕ1rαr1 ✁❆xα1 ✁ ❆xr···✁❆❡❡r❅❅❅❅Sq❅···q❅r2α1 ✁❆ αrx1 ✁ ❆xr✁ · · · ❆❡❡Рис. 10βсхемой, получится некоторая конъюнкция y1β1 · · · yq q . Из (5) следует,что сложность такой схемы будет оцениваться сверху величинойr 2 + 2q+1 − 2 + r2q 2r.rВыберем r = 2t , где t = ⌈log2 log2 n⌉, n = r + q. Тогда слагаемое r2q будет главной частью асимптотики сомножителя при r → ∞.Заметим, что сложность схемы S (асимптотически 2n ) меньшесложности разделительного контактного дерева, но вместе с тем, видно, что свойством разделительности S не обладает: в пределах одного пучка (xα1 1 , .
. . , xαr r ) функция проводимости между любыми двумяполюсами–выходами этого пучка ненулевая. Однако, можно считать,что схема S обладает свойством ослабленной разделительности. Этоозначает, что если разбить полюсы–выходы на попарно не пересекающиеся подмножества и объединить полюсы–выходы в каждом подмножестве (так, например, объединить полюсы–выходы xαi i из всех пучков), то полученная схема будет реализовывать дизъюнкции конъюнкций, относящихся к указанным подмножествам, и будет кроме тогообладать свойством разделительности (что следует из свойства 2 характеристической функции).§ 2.5. Асимптотически наилучший методРассмотрим произвольную функцию f (x1 , .
. . , xn ). Выделим средиее переменных r первых x1 , . . . , xr , где r = 2t для некоторого t, и kпоследних xn−k+1 , . . . , xn . Согласно лемме, множество наборов длины19xn−k+1 , . . . , xnα̃(1)0...0···α̃(1)1...1···α̃(r)0...0···α̃(r)1...1···σ1...σn−k···0, .
. . , 0...f (σ1 , . . . , σn )σn−k+1 , . . . , σn...1, . . . , 1Табл. 1r разбивается на попарно не пересекающиеся единичные сферы. Обозначим центры этих сфер через (α1 , . . . , αr ), а r наборов, в них содержащихся, черезα̃(1) = (α1 , . . . , αr ), .
. . , α̃(r) = (α1 , . . . , αr ).Зададим функцию f с помощью таблицы (см. табл. 1). В этой таблице по числу сфер 2r /r вертикальных полос, каждая из которых содержит значения, принимаемые функцией f на наборах вида(α̃(j) , σr+1 , . . . , σn−k , σn−k+1 , . . . , σn ), где α̃(j) — всевозможные наборы,содержащиеся в данной сфере, (σr+1 , . . . , σn−k ) = (0, . . . , 0), . .
. , (1, . . . , 1),а (σn−k+1 , . . . , σn ) фиксированы. Всего к каждой сфере будет относиться r2n−k−r наборов длины n − k.Выберем теперь параметр s и разделим таблицу на горизонтальныеполосы высоты s. Высота нижней полосы пусть будет s′ 6 s. Такихгоризонтальных полос в таблице окажется k22k6+ 1.p=ssРассмотрим клетку таблицы с координатами (i, j), где j — номер сферы, и построим функцию fij (x̃), которая совпадает с f на наборах клетки (i, j) и равна нулю в противном случае.
Следовательно_f (x̃) =fij (x̃).(i,j)20Клетка (i, j) размера s × r2n−k−r содержит максимум 2s различныхстолбцов. Зафиксируем некоторый столбец τ̃ клетки, и пусть, аналогично, fij τ̃ совпадает с fij на столбце τ̃ и равна нулю на других наборах.Тогда_fij (x̃) =fij τ̃ (x̃).τ̃Если τ̃ 6= τ̃ , то множества им соответствующих столбцов не пересекаются. Представим′(1)(2)fij τ̃ (x1 , . .
. , xn ) = fij τ̃ (xn−k+1 , . . . , xn )fij τ̃ (x1 , . . . , xn−k ),(1)(2)где функция fij τ̃ дает значение на наборе τ̃ , а функция fij τ̃ тождественно единична на столбцах, содержащих набор τ̃ .Пусть ϕ(x1 , . . . , xr ) — характеристическая функция сферы номерj.
Реализуем ее схемой, на выходе которой построим разделительноеконтактное дерево по переменным xr+1 , . . . , xn−k . Получим схему, аналогичную изображенной на рис. 10. Зафиксируем набор τ̃ и соединимвыходы полученной схемы, соответствующие набору τ̃ . Теперь схема(2)будет реализовывать функцию fij τ̃ . Для τ̃ ′ отличного от τ̃ поступимтак же. В итоге при фиксированных i и j получим реализацию всех(2)функций fij τ̃q одной и той же схемой, соответствующей j–й сфере. Условимся обозначать эту схему Sij . Из (5) следует, чтоLK (Sij ) 6 r 2 + 2n−k−r 2 + r2n−k−r .(6)(1)Функцию fij τ̃ реализуем схемой с помощью ДНФ сложности не более sk и соединим со схемой Sij .
Всего при фиксированных i и j слож(2)ность схемы Sij возрастет на sk2s , поскольку 2s — число функций fij τ̃ .Объединим теперь полученные схемы по всем i и j в схему S. В силу(6) r 2k22n−k−rn−k−rsLK (S) 6 r + 22 + r2+ ks2+1.(7)srПодберем параметры k, s и r = 2t с тем, чтобы главными частямиасимптотики правой части (7) при n → ∞ были r2n−k−r и 2k /s. Положим√1k = ⌈2 log2 n⌉ , r = 2⌈ 2 log2 n⌉ , s = 2⌈n−2 n⌉ .Сравним рост слагаемых первой скобки:ks2s(log2 n)n2n n2 2√≍√r2n−k−r22 n 2n n21√n→ 0,n → ∞.Действительно, главная часть асимптотики правой части (7) приn → ∞ есть2n2k 2rr2n−k−r= ,s rsследовательно2nLK (S) .
,nа значит, в классе контактных схем2n.nДля почти всех функций эту сложность уменьшить нельзя. Приведем неконструктивное доказательство этого факта. Обозначим черезN(n, h) число функций f (x1 , . . . , xn ), которые можно реализовать контактной схемой сложности не более h, а через N ′ (n, h) число функцийf (x1 , . . . , xn ), реализуемых контактной схемой сложности в точности h.Но тогда N(n, h) = N ′ (n, h), поскольку схемой большей сложности, чемданная, можно реализовать всегда.
Наконец, N ′′ (n, h) — число схемсложности в точности h, реализующих функцию f (x1 , . . . , xn ). Справедливо соотношениеLK (n) .N(n, h) = N ′ (n, h) 6 N ′′ (n, h).nЕсли для некоторого h0 выполнено N(n, h0 ) < 22 , то LK (n) > h0 .nПоэтому будем доказывать, что N ′′ (n, h0 ) < 22 . Оценим величинуN ′′ (n, h). Сложность h есть по сути дела число ребер графа с занумерованными вершинами. В таком случае вершин будет 2h + 2, в томчисле и полюсы — вершины с номерами 1 и 2.
Оценим количествоΓ(h) графов. Назовем пару вершин графа сортом ребер. Всего сортов2B = C2h+2= (h + 1)(2h + 1) = 2h2 + 3h + 1. ТогдаhhΓ(h) = HBh = CB+h−1= C2h2 +4h 6(6h2 )h(6h2 )h<= (6Ah)h .hh!(h/A)Следовательно, число схемh6 C6h2 <N ′′ (n, h) 6 Γ(h)(2n)h 6 (6Ah)h (2n)h = (12Anh)h ,где (2nh ) — варианты в зависимости от нагрузки (xi или xi ) ребер графа. Пусть ε — произвольное положительное число. Положимh0 = (1 − ε)2n /n и оценим ′′N (n, h0 )log2= log2 N ′′ (n, h0 ) − 2n 6 h0 log2 (12Anh0 ) − 2n =n22222n(log2 (12A) + log2 (1 − ε) + n) − 2n =n2n2n= C + (1 − ε)2n − 2n = C − ε2n .nnВеличина C2n /n − ε2n стремится к −∞ при n → ∞ для любого фиксированного ε.
Следовательно, для любого ε > 0 при достаточно большихnn выполнено N ′′ (n, h0 ) < 22 . Отсюда вытекает нижняя оценка сложности в классе контактных схем. В итоге имеем2nLK (n) ∼ .n= (1 − ε)§ 2.6. Метод каскадовЗафисируем порядок переменных в функции f (x1 , . . . , xn ). Введемклассы Gi . Пусть G0 = {g0,1(x1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
