Материалы для подготовки к экзамену прошлых лет, страница 2

Таким образом получаем следующие неравенства:2n26c3 n + LИКС (n)2 !LИКС (n)+2n.log3 (n + LИКС (n))Логарифмируя неравенство, получим2n 6 LИКС (n) c03 + 2n − 5 log n + O n2 .В итоге получаем оценкуLИКС 2n2n−12(n) >−On>nn − 52 log n + c031+52log n − o (1)n!Теорема доказана.§2Универсальные системы ФАЛ и их построение на основе селекторных разбиений БП.Напомним определение дизъюнктивно-универсального множества (ДУМ) ФАЛ.Множество ФАЛ G называется ДУМ порядка m и ранга p, тогда и только тогда, когда для любой ФАЛ g ∈ P2 (m) найдутся функции g1 , . .

. , gp такие, чтоg = g1 ∨ . . . ∨ gp . Для построения схем в произвольных базисах необходимо обобщить понятие ДУМ ФАЛ. Пусть φ(y1 , . . . , yp ) — ФАЛ, существенно зависящая отвсех своих переменных. Тогда множество функций G называется φ–универсальнойсистемой (множеством) ФАЛ порядка m, если и только если для всякой ФАЛ g ∈P2 (m) найдутся функции g1 , .

. . , gp ∈ G такие, что g = φ(g1 , . . . , gp ). ДУМ ФАЛможно построить следующим образом. Разобьём куб B m произвольным образом наp множеств S1 , . . . , Sp . Для каждого i, 1 6 i 6 p положим Gi = {g ∈ P2 (m) | g(x) ≡0 при x ∈/ Si }. Тогда G = G1 ∪ . . . ∪ Gp — ДУМ порядка m и ранга p. Теперь приведём похожий способ построения φ–УМ. Пусть функция φ(y1 , . . . , yp ) существеннозависит от всех своих переменных.

Тогда для всякого номера i, 1 6 i 6 p, найдутсяконстанты αi,1 , . . . , αi,p такие, что φ(αi,1 , . . . , αi,i−1 , yi , αi,i+1 , . . . , αi,p ) ≡ yi ⊕ αi,i .Разобьём куб B m на множества S1 , . . . , Sp , и определим множества G1 , . . .

, Gp :Gi = {g ∈ P2 (m) | g(β) = αi,j если β ∈ Sj , при j = 1, . . . , i − 1, i + 1, . . . , p}.10Глава 1. Асимпотические оценки высокой степени точностиТогда G = G1 ∪. . .∪Gp является φ–УМ порядка m и ранга p. Действительно, любуюфункцию f ∈ P2 (m) можно представить в виде f = φ(g1 , . . . , gp ), где gi ∈ Gi иgi (β) = f (β) ⊕ αi,i при β ∈ Si .Рассмотрим для p = 2t функцию φ(y1 , . . . , yp ) = y1 yt+1 ∨y2 yt+2 ∨. . .∨yt y2t . Приведём пример φ–УМ для данной функции φ.

Разобьём куб B m на полосы δ1 , . . . , δp .Каждая полоса δi представляет собой множество наборов, номера которых лежатв интервале [ni , ni+1 ), где 0 = n1 < n2 < . . . < np+1 = 2m . ПоложимG1 = {g(x1 , . . . , xm ) | g(α) = 1 при α ∈ δt+1 , g(α) = 0 при α 6∈ δ1 ∪ δt+1 }G2 = {g(x1 , . . . , xm ) | g(α) = 1 при α ∈ δt+2 , g(α) = 0 при α 6∈ δ2 ∪ δt+2 }...Gp = {g(x1 , . . . , xm ) | g(α) = 1 при α ∈ δ1 , g(α) = 0 при α 6∈ δ1 ∪ δt+1 }Множество G = G1 ∪ . . . ∪ Gp — “стандартное” (“диагональное”) φ–УМ. Рассмотревразбиение B m = δ1 ∪.

. .∪δp , в котором |δ1 | = . . . = |δt | = s0 и |δt+1 | = . . . = |δ2t | = s00 ,000получим φ–УМ G мощности t(2s + 2s ). Можно постороить и более компактное φ–УМ для рассматриваемой функции φ. Рассмотрим множество Ǧ ⊂ P2 функций,равных единице на множестве δ1 ∪ . . . ∪ δt и принимающих одинаковые значенияна наборах с одинаковыми номерами внутри компонент δt+1 , . . . , δ2t . Мощность00множества Ǧ будет равна 2s . Воспользуемся тем фактом, что при 1 6 i 6 t выполнено тождество φ(0, .

. . , 0, yi , 0, . . . , 0, yt+1 , yt+2 , . . . y2t ) ≡ yi . Отсюда следует,000что множество Ĝ = G1 ∪ . . . ∪ Gt ∪ Ǧ является φ–УМ мощности t · 2s + 2s .Определение. Пусть задана функция φ(y1 , . . . , yp ). Разбиение D = (Y1 , . . . , Yd )множества Y = {y1 , . . . , yp } называется селекторным разбиением БП функции φтогда и только тогда, когда для всякого i, i = 1, .

. . , d и для любой переменнойy ∈ Yi найдутся константы α1 , . . . , αi−1 , αi+1 , . . . , αd такие, что при подстановкеих вместо переменных из Y1 , . . . , Yi−1, Yi+1 , ..., Yd соответственно, выполняется равенство φ = y ⊕ αi .Отметим, что если φ существенно зависит от всех своих БП, то тривиальноеразбиение Yi = {yi }, i = 1, . . . , p является селекторным. Если функция φ симметрична по переменным yi , yj , то они не могут входить в одну и ту же компоненту селекторного разбиения (упражнение). Отсюда следует, что у функцииφ(y1 , . . . , yp ) = y1 ∨. . .∨yp нет нетривиальных селекторных разбиений БП.

У функции φ(y1 , . . . , yp ) = y1 yt+1 ∨ y2 yt+2 ∨ . . . ∨ yt y2t селекторным является, например,разбиение Y1 = {y1 }, . . . , Yt = {yt }, Yt+1 = {yt+1 , . . . , y2t }.Утверждение 1. Пусть D = (Y1 , . . . , Yd ) селекторное разбиение переменных Y ={y1 , . . . , yp } ФАЛ φ(y1 , . . . , yp ), где |Yi | = pi , i = 1, . . .

, p, и пусть s1 , . . . , sd —чётные числа, удовлетворяющие условию s1 p1 +. . .+sd pd > 2m . Тогда существуетφ–УМ G порядка m такое, что1. |G| 6 2s1 + . . . + 2sd ,~ 6 c|G| + O(d · 2m+s/2 ), где A ∈ {К, C} и s = max16i6d si .2. LA (G)§2. Универсальные системы ФАЛ11Доказательство. По определению селекторного разбиения, существует набор констант {αi,j,k } таких, что для всякого j, 1 6 j 6 d и любого k, 1 6 k 6 pj при подстановке в функцию φ констант αi,j,k , i = 1, . . . , j − 1, j + 1, . . . , d на места переменныхиз Y1 , .

. . , Yj−1 , Yj+1 , . . . , Yd соответственно, получается функция, существенно зависящая лишь от k–й переменной из компоненты Yj . Разобьём куб B m на последовательные полосы δ1,1 , . . . , δ1,p1 , δ2,1 , . . . , δ2,p2 , . . . , δd,1 , . . . , δd,pd . При этом ширина полосы δj,k равна sj при всех k, 1 6 k 6 pj . Cуммарная ширина полос равнаPmm будет полностью покрываться данными поj sj pj > 2 , следовательно куб Bлосами. Рассмотрим при каждом i, 1 6 i 6 d, множество Gi всех функций, принимающих значение αi,j,k на полосе δj,k при j 6= i, k = 1, . .

. , pj , и принимающих одинаковые значения на наборах с одинаковыми номерами из полос δi,1 , δi,2 , . . . , δi,pi .При этом |Gi | = si , i = 1, . . . , d. Покажем, что множество G = G1 ∪ . . . ∪ Gd будет φ–УМ. Пусть g ∈ P2 (m) — произвольная функция. Рассмотрим суперпозициюφ(g1 , . . . , gp ), в которой на место каждой переменной из Yi , 1 6 i 6 d подставленыфункции из множеств Gi соответственно. Пусть β ∈ B m — набор, принадлежащийполосе δj,k . Тогда по построению множеств G1 , . . .

, Gj−1 , Gj+1 , . . . , Gd , выполнено равенство φ(g1 (β), . . . , gp (β)) = gl (β) ⊕ c, где gl — функция, подставленная наместо k–й переменной из множества Yj , а c — константа, зависящая только от j, k.Выберем функцию gl ∈ Gj так, чтобы было выполнено равенство gl (β) = g(β) ⊕ cпри β ∈ δj,k . Тогда на множестве δj,k будет выполнено равенство φ(g1 , . . . , gp ) = g.Действуя подобным образом, можно выбрать функции из g1 , . . .

, gp так, чтобы суперпозиция φ(g1 , . . . , gp ) совпала с функцией g на всём кубе B m .Оценим сложность системы ФАЛ G. Реализуем систему G схемой ΣG , построенной по методу каскадов при следующем порядке переменных: xm , xm−1 , . . . , x1 .Подставив 0 вместо переменной xm в функции из множества Gi , мы получим мно(0)жество Gi , состоящее из 2si /2 6 2s/2 функций m − 1 переменных. Систему этихфункций можно реализовать со сложностью, не превосходящей 2s/2 · 2m−1 . Анало(1)гично оценивается сложность системы Gi ФАЛ, получающихся при подстановкеконстанты 1 на место переменной xm в функции из Gi .

Суммированием по i получаем неравенство L(G(0) ∪G(1) ) 6 d·2m+s/2 . Разложение функций из G по переменнойxm можно реализовать со сложностью 2|G|, что даёт окончательную оценкуL(ΣG ) 6 2|G| + d · 2m+s/2 .Замечание. В условии утверждения 1 допустимы равенства si = 0. При этом |Gi | =1, и Gi состоит из одной ФАЛ, принимающей на каждой из полос δi , i = 1, . . . , pпостоянные значения.Пусть D = (Y1 , . . . , Yd ) — разбиение множества Y, |Y | = p. Энтропией разбие-12Глава 1.

Асимпотические оценки высокой степени точностиния D называется величинаH(D) = −dX|Yi |i=1|Y |log|Yi ||Y |. Энтропия вырожденного разбиения равна нулю, а энтропия тривиального разбиения равна log p. Можно показать, что 0 6 H(D) 6 log d для любого разбиения D,содержащего d компонент.Утверждение 2. Пусть D = (Y1 , . . . , Yd ) — селекторное разбиение БП ФАЛφ(y1 , . . . , yp ), и пусть s > log p, p(1−H(D)) > 2m . Тогда найдётся φ–УМ G порядкаm такое, что1.

|G| 6 2s+2 ,~ 6 c · |G| + O(d · 2m+s/2 ), где A ∈ {К, C}.2. LA (G)Доказательство. Выберем для каждого i, 1 6 i 6 d чётное число si такое, чтоs + log ppi 6 si 6 s + log ppi + 2, где pi = |Yi |. Проверим, что выполнено неравенствоs1 p1 + . . . + sd pd > 2m . Заметим, что si pi > pi (s + log ppi ) = pi s + p · ppi log ppi , иследовательноdXi=1si pi >dXi=1pi s + p ·dXpii=1plogpi= p(s − H(D)) > 2m .pОсталось воспользоваться утверждением 1.§3Мультиплексорные ФАЛ и обощенное разложение. Оптимальная по задержке реализация мультиплексорных ФАЛ в произвольном базисеРассмотрим набор БП αe = (α1 , . .

. , αn ). Альтернированием набора αe назовем минимальной число отрезков постоянства, на которые распадается этот набор, и будемобозначать Alt (eα). Альтернирование произвольной ФАЛ g, g ∈ P2 (n) равно альтернированию столбца ее значений. Некоторую ФАЛ g будем называть ступенчатой тогда и только тогда, когда Alt (g) 6 1. Не трудно видеть, что произвольнаяступечантая ФАЛ является либо монотонной, либо антимонотонной.Лемма 3.1. Для любой ФАЛ g ∈ P2 (n) выполняется неравенство:D (g) 6 2 dlog ne + dlog (Alt (g))e + 2.Доказательство.(3.1)§4. Специальные классы функций13Лемма 3.2. Пусть ϕ — существенная ФАЛ от БП y1 , . . . , yp , а f1 , .

. . , fp — существеные ФАЛ от z (1) , . . . , z (p) , где z (1) , . . . , z (p) не имеют общих БП. Тогда дляf (z) = ϕ (f1 (z1 ) , . . . , fp (zp )) выпоняется неравентсво:alt 6 max alt (fj ) + alt (ϕ) .16j6p(3.2)Доказательство.Лемма 3.3. Для любой существенной ФАЛ ϕ (y1 , .