О.Б. Лупанов - Элементы математической кибернетики (1161667), страница 5
Текст из файла (страница 5)
. . , xn ) = f (x1 , . . . , xn )}. Затем G1 образован всевозможными различными функциями из g0,1 (0, x2 , . . . , xn ) иg0,1 (1, x2 , . . . , xn ). Будем обозначать их g1,1 , g1,2 и т. д. При таком порядке переменных класс Gn−1 всегда будет подмножеством {0, 1, xn , xn }.Построение контактной схемы сводится к следующему. Сначалаконтактами xn и xn , выходящими из полюса a, реализуются функцииодной переменной из Gn−1 . Затем для каждой gn−2,i ∈ Gn−2 , согласноразложению gn−2,i (xn−1 , xn ) = xn−1 gn−2,i (1, xn ) ∨ xn−1 gn−2,i(0, xn ), добавим контакты xn−1 и xn−1 к соответствующим выходам уже построенной схемы и соединим их. Аналогично для Gn−3 и т. д.Рассмотрим пример. Пустьf (x1 , . .
. , xn ) = ln (x1 , . . . , xn ) = x1 ⊕ · · · ⊕ xn .Тогда G0 = {g0,1}, гдеg0,1 (x1 , . . . , xn ) = x1 ⊕ · · · ⊕ xn ;G1 = {g1,1 , g1,2 }, гдеg1,1 (x2 , . . . , xn ) = x2 ⊕ · · · ⊕ xn ,g1,2 (x2 , . . . , xn ) = x2 ⊕ · · · ⊕ xn ⊕ 1;G2 = {g2,1 , g2,2 }, гдеg2,1 (x3 , . . . , xn ) = x3 ⊕ · · · ⊕ xn ,g2,2 (x3 , . . . , xn ) = x3 ⊕ · · · ⊕ xn ⊕ 1и т. д.
Наконец, Gn−1 = {xn , xn }. Реализующая контактная схема Sизображена на рис. 11. Ее сложностьLK (S) = 2 · 2 + (n − 2) · 4 = 4n − 4.23a❡xn✟ ❍ xn❍❍rr✟✟❍❍xn−1 ✟✟❍✟xn−1 ✟✟❍❍ xn−1r✟xn−1❍r...Sr❍r❍x2✟✟❍✟x2 ✟✟❍❍ x2x2 ❍rr✟❍❍✟✟x1 ❍ ❡✟ x1bРис. 11Обозначим Ai = |Gi|. Тогда A0 = 1, и кроме того справедлива оценка Ai+1 6 2Ai . Но вместе с тем видно, что An−1 6 4 и An−2 6 16, т. е.jв общем случае An−j 6 22 = p2 (j). В методе каскадов на каждом шагетратится по два контакта, поэтомуLK (S) 6 2A0 + · · · + 2An−1 < 4 + 2n−1XAi .i=1Обозначим i0 = ⌈n − log2 n + 1⌉. Тогдаn − log2 n + 1 < i0 6 n − log2 n + 2.Разобьем сумму надвое:LK (S) < 4 + 2n−1XAi = 4 + 2i=16 4+i0Xi=1i2·2 +n−1Xi=i0 +1i0XAi + 2i=1n−i2 · 226 4+8n−1XAi 6i=i0 +12n2n+ o(2n ) .
8 .nnУтверждение 6. Невозможно построить разделительную схемуменее сложной, чем разделительное контактное дерево.Доказательство. Пусть дана разделительнаяKn = {xσ1 1 · · · xσnn }. Покажем, что L(S) > 2n+1 − 2.24схемаSдляПусть схема имеет 2n выходов. Докажем, что внутренних вершинне менее 2n −1. Это будет означать, что всего вершин не менее 2n+1 −1,и в силу связности, схема будет содержать не менее 2n+1 − 2 контактов.Рассмотрим таблицу, в которой строки соответствуют наборамα̃1 , . .
. , α̃2n длины n, а столбцы — внутренним вершинам b1 , . . . , bn . Занумеруем выходы схемы как D1 , . . . , D2n . Возьмем j–ю строку и i–йстолбец и рассмотрим цепи от вершины bi ко всем возможным выходам. Если соответствующие этим цепям конъюнкции единичны нанаборе α̃j , то в силу разделительности схемы, выходов, соединенныхпроводящей цепью с bi , может быть не более одного. Если такой выходDh найдется, отметим его на пересечении j–й строки и i–го столбцатаблицы.Цепь, соединяющая полюс–вход схемы с выходом Dh , должна иметьдлину не менее n, и в ней должны встречаться все переменные.
Возьмем на этой цепи некоторую внутреннюю вершину, отстоящую от Dhна 1, и обозначим ее bs1 . Проводящий контакт между ней и Dh обозначим xσi11 . Всего этим контактом будет проводиться 2n−1 наборов вида (α1 , . . . , αi1 −1 , σ1 , αi1 +1 , . . . , αn ). Значит, в s1 –м столбце таблицы Dhвстречается 2n−1 раз.Сдвинемся еще на один контакт от выхода Dh к некоторой внутренней вершине bs2 . По тем же причинам s2 –й столбец таблицы будетсодержать по меньшей мере 2n−2 записей Dh .
В итоге в sn –м столбцеDh встречается 20 = 1 раз. Всего название одного выхода встречаетсяне менее 2n−1 + 2n−2 + · · · + 20 = 2n − 1 раз, а соответственно, всех выходов — не менее (2n + 1)2n раз. По сути дела, это значит, что площадьтаблицы не менее (2n + 1)2n . Но число строк таблицы известно и равно 2n , поэтому столбцов должно быть не менее 2n − 1. Утверждениедоказано.§ 2.7.
Нижние оценки сложности. ПринципнемонотонностиПусть контакная схема S реализует функцию f (x1 , . . . , xn ), причем,схема S такова, что по некоторой переменной xi она содержит толькозамыкающие контакты (т. е. в схеме нет контактов xi ).
Тогда для наборовσ̃0 = (σ1 , . . . , σn−1 , 0, σn+1 , . . . , σn ),σ̃1 = (σ1 , . . . , σn−1 , 1, σn+1 , . . . , σn )справедливо f (σ̃0 ) 6 f (σ̃1 ). Другими словами, если схема S по переменной xi содержит только контакты вида xi , то функция f не убывает по25переменной xi . Следовательно, если функция, реализуемая схемой Sне является неубывающей по переменной xi , то схема S содержит хотябы один размыкающий контакт xi .Аналогично, если функция, реализуемая схемой S, не являетсяневозрастающей по переменной xi , то схема S содержит хотя бы одинзамыкающий контакт xi . Если функция является одновременно невозрастающей и неубывающей по переменной xi , то схема S должна содержать и замыкающий xi , и размыкающий xi контакты хотя бы одинраз.Рассмотрим пример.
Пусть Sn1 (x1 , . . . , xn ) — функция, принимающая единичное значение только на n наборах с ровно одной единицей.Покажем, что LK (Sn1 ) = 3n − 2.В самом деле, функция Sn1 реализуется всевозможными конъюнкциями вида x1 · · · xi−1 xi xi+1 · · · xn . Контакная схема сложности 3n − 2представлена на рис. 12.
Справедлива верхняя оценка LK (Sn1 ) 6 3n − 2.Получим нижнюю оценку. Докажем, что LK (S31 ) > 7. Предположимобратное: для реализации функции S31 схемой достаточно шести контактов. Это означает, что по каждой из переменных x1 , x2 , x3 долженбыть как размыкающий так и замыкающий контакт. Рассмотрим дваслучая.1) К некоторому полюсу примыкают два размыкающих контакта,например x1 и x2 .
Функция должна принимать единичное значение нанаборе (0, 0, 1), значит должна быть цепь x1 x2 x3 , чего в данной ситуации быть не может.2) К каждому полюсу примыкает не более одного размыкающего контакта. Значит, существует размыкающий контакт, например x3 ,не примыкающий ни к одному из полюсов. Функция должна принимать единичное значение на наборе (1, 0, 0), значит должна быть цепьx1 x2 x3 . Но с другой стороны, в схеме из шести контактов должна бытьцепь x1 x2 x3 , соответствующая набору (0, 1, 0). Однако, тогда функцияне будет единичной на наборе (0, 0, 1). Полученное противоречие показывает недостаточность шести контактов.Докажем еще один факт, относящийся к функции Sn1 : по всем переменным кроме, быть может, двух схема, реализующая Sn1 , имеет триконтакта.
Допустим, что, наоборот, существует три переменные, обозначим их xi , xj , xk , по каждой из которых схема имеет два контакта.Подставив вместо остальных переменных функции Sn1 нули, получимфункцию S31 (xi , xj , xk ). В схеме при замене контакта единицей будутотождествлены концы ребра, а при замене нулем — просто удаленосоответствующее ребро. Таким образом, получим для S31 схему слож26α❡◗ x1◗x1◗r◗r◗◗ x2◗x2◗ x2◗rr◗◗ x2◗x3◗ x3◗r...Sr◗◗xn−1 ◗◗ xn−1r xn−1 ◗r◗◗xnx◗n◗❡βРис. 12ности 6. Противоречие.Покажем теперь, чтоLK (ln ) > 4n − 4,(8)где, напомним, ln = x1 ⊕ · · · ⊕ xn .Введем обозначения: mi (S) — число контактов (нагрузка) по переменной xi (xi или xi ) в схеме S, т.
е.LK (S) =nXmi (S)i=1для функции f (x1 , . . . , xn ). Пустьm(S) = max mi (S),m(f ) = min m(S).S=S(f )i=1,nВ данном случае будем обозначать также µ(n) = m(ln ) и λ(n) = LK (ln ).Заметим сначала, что LK (ln ) = LK (ln + 1). Чтобы убедиться в этом,достаточно заменить в контактной схеме каждую переменную ее отрицанием.Отметим некоторые свойства µ(n).1◦ .µ(n + 1) > µ(n).27Действительно, рассмотрим схему S для ln+1 , на которой достигается минимум µ(n + 1): µ(n + 1) = m(S), следовательно mn+1 (S) > mi (S)для всех i = 1, n. Подставим в S вместо xn+1 некоторую константу,например нуль. Получим некоторую схему S ′ для функции ln .
ТогдаLK (S ′ ) = m1 (S) + · · · + mn (S), поскольку mi (S) = mi (S ′ ) для i 6= n + 1.Отсюда получаем, чтоm(S ′ ) = max mi (S) 6 mn+1 (S) = µ(n + 1),i=1,nт. е. требуемое неравенство.2◦ .λ(n) > µ(n) + λ(n − 1).Пусть S — минимальная схема для ln :λ(n) = LK (S) = m1 (S) + · · · + mn (S).Выберем наиболее нагруженную переменную: пустьmn (S) = max mi (S).i=1,nПодставим теперь в S вместо xn некоторую константу — получим схемуS ′ для ln−1 .
АналогичноLK (S ′ ) = m1 (S) + · · · + mn−1 (S) > λ(n − 1).По предположению m(S) = mn (S), и кроме того mn (S) > µ(n). Окончательно получаем требуемоеLK (S) = mn (S) + LK (S ′ ) > µ(n) + λ(n − 1).Для l2 известно, что λ(2) = 4 и µ(2) = 2. Однако для n = 3 существует схема Ŝ (см. рис. 13), имеющая по каждой переменной нагрузку 3, значит µ(3) = 3 (если бы µ(3) = 4, то неравенство λ(n) > 4n − 4далее можно было доказать по индукции).
Схема имеет цепи x1 x2 x3 ,x1 x2 x3 , x1 x2 x3 , x1 x2 x3 и реализует функцию x1 ⊕ x2 ⊕ x3 ⊕ 1.Покажем, что с тем же распределением контактов, что и в Ŝ, однородную функцию реализовать нельзя. Предположим, что это не так, исхемой типа Ŝ реализуется функция x1 ⊕ x2 ⊕ x3 . Цепи x1 x2 x3 , x1 x2 x3 ,x1 x2 x3 , x1 x2 x3 будут также использовать по два замыкающих и по дваразмыкающих контакта по каждой переменной. Но ни к одному изполюсов не может примыкать два размыкающих контакта, поскольку в противном случае не будет реализована цепь, содержащая эти28r✑◗ xx2✑✑◗ 3◗✑x◗ ❡β1r✑x1✑✑◗◗ x2✑◗✑✑◗✑x3x3❡✑◗✑r✑✑α ◗◗✑✑ x2x1◗◗r✑ŜРис.
13контакты. Поэтому существует размыкающий контакт, например x3 ,который не примыкает ни к одному из полюсов. Он содержится какв цепи x1 x3 x2 , так и в цепи x1 x3 x2 . Но тогда не остается вариантовдля такого размещения цепи x1 x2 x3 , чтобы ни к одному из полюсов непримыкало более одного размыкающего контакта. Противоречие.Докажем, что µ(4) > 4. Предположим, что µ(4) 6 3, т. е. распределение контактов следующее: xi , xi , xαi i для i = 1, 4, и реализуется в этомслучае функция x1 ⊕ · · · ⊕ x4 ⊕ ε. Подставив вместо переменной x4 константу ε, придем к схеме типа Ŝ, реализующей функцию x1 ⊕ x3 ⊕ x3 ,что по ранее доказанному, неверно. Аналогично докажем, что λ(3) > 8.Предположим, что λ(3) 6 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
