Ответы к экзамену 2010 (1133259), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Для любого q существует 3-однородное дерево с q висячимивершинами, и число внутренних вершин bq/2c23Вопрос 22. Реализация подфункций f (x1, ..., xk , σk+1, ..., σn)с полностью однородных схемОпр.Полузвезда - совокупность ребер, исходящих из внутренней вершины.Сопоставим дереву D функцию H(z1 , ..., zq ), считая, что каждой полузвездепорядка 3 соответствует функция h(u, v, w), полузвезде h(u, v, 0), концевым вершинам1, ..., q - переменные z1 , ..., zqЛемма f (x1 , ..., xk , σk+1 , ..., σn ) = H(G1σk+1 ,...,σn (x1 , ..., xk ), ..., Gqσk+1 ,...,σn (x1 , ..., xk ))Д-воПусть x1 = σ1 , ..., xk = σk .

Найдем значения G1σk+1 ,...,σn (x1 , ..., xk ), ..., Gqσk+1 ,...,σn (x1 , ..., xk )Пусть (σ1 , ..., σk ) лежит в i-й полосе (Πi ). Тогдаf (σ1 , ..., σn ), если ν = i;νGσk+1 ,...,σn (σ1 , ..., σk ) = 0,если ν 6= i; i ∈/ Πi ;1,если ν 6= i; i ∈ Πi .В последнем выражении условия i ∈ Πi , i ∈/ Πi эквивалентны ν ∈ Di , ν ∈/ Di ⇒при x1 = σ1 , ..., xk = σk H(G1σk+1 ,...,σn (x1 , ..., xk ), ..., Gqσk+1 ,...,σn (x1 , ..., xk )) = H(γ1 , ..., γq ),где γ1 , ..., γq - набор на входах, соответствующих концевым вершинам из D\Di , дает0, на входах дерева Di дает всюду 1, кроме выхода под номером i, на к-рый поступаетf (σ1 , ..., σk )Опускаясь по дереву, голосование дает на выходе значение f (σ1 , ..., σk ), то естьH(γ1 , ..., γq ) = f (σ1 , ..., σk )24Билет 23.

Верхняя оценка сложности реализациипроизвольной булевой функции схемами в базисе{H, &, ∨, 6}Пусть Σ - схема из ФЭ в базисе BПусть L6,B&,∨ (Σ) и LhB (Σ) - соответственно число элементов F6 , F& , F∨ и Fh в схемеΣ.Теорема Для ∀m ∈ N , где m = m(n) = o(nlog n), существует алгоритм, которыйдля каждой булевой функции f (x1 , ..., xn ) строит схему Σf (x1 ,...,xn ) над базисом B так,что Lb (Σf (x1 ,...,xn ) ) .

122n nL6,&,∨ (f(x1 ,...,xn ) )Lh (Σf (x1 ,...,xn ) ) = o(1nm )Д-воПостроим исходную схему Σf из блоков A, B, C, C 0 , D, E, F (Рис.16)q - число полос, s - i-я полоса• Блок A реализует все конъюнкции xσ1 1 , ..., xσk k ; LB (A) ≤ k + k ∗ 2k26Рис. 16: Схемаσk+1• Блок B реализует все конъюнкции xk+1, ..., xσnn ; LB (B) ≤ (n − k) + (n − k) ∗ 2n−k• Блок C реализует в виде совершенной ДНФ все короткие столбцы и функцииψj ; LB (C) ≤ sq ∗ 2s• Блок C’ реализует с помощью дизъюнкторов все удлинненные“ столбцы.”LB (C 0 ) ≤ 2s ∗ q s/2• Блок D реализует все функции f (x1 , ..., xk , σk+1 , ..., σn ), исходя из формулH(G1σk+1 ,...,σn (x1 , ..., xk ), ..., Gqσk+1 ,...,σn (x1 , ..., xk )). Для этого требуется [q/2] элементовFh на каждую формулу и, может быть, нужно реализовать 0 (требует 2элемента).

LB (D) = [q/2]2n − k + ∆; ∆ равно 0 или 2.σk+1• Блок Е реализует функции вида xk+1, ..., xσnn f (x1 , ..., xk , σk+1 , ..., σn ); LB (E) ≤2n−k• Блок F реализует функцию f (x1 , ..., xn ); LB (F ) ≤ 2n−kПусть k = [(m + 3) log2 n], s = [n − (3m + 6) log2 n]ТогдаLB (A) . 2n ∗ 2O(n) nm+1 2n = o(2n nm+1 )LB (B) . 2n ∗ 2n nm+3 = o(2n nm+1 )LB (C) . 2s+k 2n n2m+3 = o(2n nmОтсюда LB (n) ≤ LB (Σf (x1 ,...,xn ) )и2n2nL6,&,∨ (Σf (x1 ,...,xn ) )1= o( m )hL (Σf (x1 ,...,xn ) )nНижняя оценка для LB (n): LB (n) &2n,2n27значит, LB (n)2n2n25Билет 24. Теорема о сколь угодно надежнойреализации произвольной БФ схемой в базисе{H, &, ∨, 6}Рассмотрим СФЭ в базисе Bp = B1 ∪ B2 , где B1 = {Fh }, B2 = {F6 , F& , F∨ }p = max{P (F6 ), P (F& ), P (F∨ )} ∈ (0, 0.5)Пусть > 0 - некоторое число, γ - класс всех схем Σ в базисе Bp : P (Σ) < .γ содержит все схемы, реализующие любые булевские функции. Пусть LBp (f, ) =minΣ LBp (Σ); LBp (n, ) = maxf ∈P2n LBp (f, Σ), где Σ реализует f так, что P (Σ) < LBp (n, ) - функция Шеннона, характеризующая сложность реализации булевскихфункций от n переменных в классе γ Теорема Существует алгоритм, который для каждой булевой функции f (x1 , ..., xn )строит схему Σf (x1 ,...,xn ) из γ такую, что• LBp (Σf (x1 ,...,xn ) ) ≤2n2n• Для любого > 0 существует N () такое, что при n > N () P (Σf (x1 ,...,xn ) ) < )Д-во1) Пусть m=2.

Построим последовательность {Σ0f (x1 ,...,xn ) } схем над базисом В,2nдля которой LB (Σ0f (x1 ,...,xn ) ) 2nL6,&,∨ (Σ0f (x1 ,...,xn ) )Lh (Σ0f (x1 ,...,xn ) )= o(1)n2e6 = F (l) , Ff& = F (l) , Ff∨ = F∨(l) из элементов базиса Bp так,2) Построим элементы F6&e6 ), P (Ff& ), P (Ff∨ )} < 1/6.чтобы max{P (Fe6 ), LBp (Ff& ), LBp (Ff∨ )}Пусть c = max{LBp (F(l)3) Для каждой схемы F рассмотрим схему (Рис.17) ΣF , содержащую l ярусовэлементов голосования, где l =] log2 n[Схема в исправном состоянии реализует ту же функцию, что и F. взяв в качествеef& ), P (Ff∨ , получаем схемы Σ6 , Σ& , Σ∨ . В этом случае LBp ≤ 3(c + 1)n2F - F6 ), P (FРис.

17: Схема28Заменив в схеме Σ0f (x1 ,...,xn ) элементы F6 , F& , F∨ на Σ6 , Σ& , Σ∨ , получаем схемуΣf (x1 ,...,xn ) над Bp .2nLBp (Σp ) ≤ LhB (Σ0f ) + L6,B&,∨ (Σ0f ) ∗ max{LBp (Σ6 ), LBp (Σ& ), LBp (Σ∨ )} . 2nP (Σf ) ≤ L6,B&,∨ (Σ0f ) ∗ max{P (Σ6 ), P (Σ& ), P (Σ∨ )} = o( n13 . Т.к. l ≥ log2 n, o( 212l ) =o( 21n ), то п. 2 вывода теоремы верен2nСледствие LBp (n, ) 2nИз св-в нижней оценки и данной асимптотики вытекает также, что прификсированном > 0 для почти всех булевских функций минимальная -надежная2n, т.е. сложность минимальнойсхема имеет сложность, асимптотически равную 2nсхемы без требования надежности.

Для указанного класса ф-й удается достичьнадежной реализации без существенного усложнения схемыСписок литературы29.

Характеристики

Список файлов ответов (шпаргалок)