Материалы для подготовки к экзамену прошлых лет (1156404), страница 4
Текст из файла (страница 4)
Специальные классы функций17Рассмотрим симметрические функции ŝ{0,m} , определяемые при m > 1 следующим образом:ŝ{0,m} (x1 , . . . , xm ) = x1 · . . . · xm ∨ x1 · . . . · xm .000Заметим, что при ŝ{0,m } 6∈ {ŝ{0,m } }c при m0 6= m00 . Отсюда следует, что для различных множеств J ⊆ N \ {1} соответствующие множества функций QJ = {ŝ{0,m} |m ∈ J}c будут различны. Каждое из таких множеств будет инвариантным классом. Из того, что класс Ŝ содержит в качестве подмножества каждое из множествQJ и имеет характеристику 0 будет следовать, что сами классы QJ имеют характеристику 0.
Классов QJ будет столько же, сколько подмножеств множества N \ {1},то есть континуум.Множество F называется базовым множеством инвариантного класса Q, еслиFc = Q. Базовое множество класса Q называется базой, если любое его собственноеподмножество уже не является базовым множеством для Q. Существуют инвариантные классы, не имеющие базы. Например, класс, состоящий из констант 0, 1 ивсех монотонных элементарных дизъюнкций (функций вида xi1 ∨ . . . ∨ xis ), имеетсчётное базовое множество, но не имеет базы.Для задания всякого инвариантного класса достаточно задать, таким образом,его базовое множество. Существует и другой способ задания инвариантных классов. Пусть Q — нетривиальный инвариантный класс. Функция g ∈ P2 называетсяпорождающим элементом класса Q тогда и только тогда, когда g 6∈ Q, а все собственные подфункции g принадлежат Q (под собственной подфункцией функцииg понимается произвольная подфункция g, не совпадающая g).
Из определенияследует, что порождающий элемент нетривиального инвариантного класса является существенной функцией, и никакие два различных порождающих элементане являются квазиподфункциями друг друга. Приведём примеры порождающихэлементов. Для класса M монотонных ФАЛ порождающий элемент единственный — это функция x1 . Множество порождающих элементов класса, состоящегоиз констант и монотонных элементарных дизъюнкций, суть x1 , x1 x2 .
Для инвариантного класса Q порождающим множеством называется всякое максимальноепо включению множество попарно не конгруэнтных порождающих элементов Q.Непосредственно из определений вытекает следующее утверждение.Утверждение 7. Пусть Q — инвариантный класс, G — его порождающее множество. Тогда Q = P2 \ (Ge ).Следствие. Пусть множество G состоит из ФАЛ, не являющихся квазиподфункциями друг друга. Тогда P2 \ (Ge ) — инвариантный класс с порождающиммножеством G.18Глава 1.
Асимпотические оценки высокой степени точности§5Принцип локального кодирования и примеры его применения.Синтез схем для не всюду определённых ФАЛ.Утверждение 8. Для всякого инвариантного класса Qn1. LC (Q(n)) ∼ σQ 2n при σQ > 0,n2. LC (Q(n)) = o(σQ 2n ) при σQ = 0.Доказательство. Рассмотрим случай σQ > 0. Докажем сначала нижнюю оценку.ИмеемσQ (n) · 2nlog |Q(n)|2nJ(Q(n)) ==∼σ,Qlog log |Q(n)|log(σQ (n) · 2n )nnоткуда по утверждению 3 следует оценка LC (Q(n)) & σQ 2n .Перейдём к верхней оценке. Пусть f (x1 , . . .
, xn ) ∈ Q(n), и q — натуральноечисло, q 6 n. Для всякого набора σ 00 ∈ B q подфункция fσ00 (x0 ) = f (x0 , σ 00 ) принадлежит множеству Q(q). Положим λ = dlog |Q(q)|e и пусть π — произвольное инъективное отображение (“кодирование”) множества Q(q) во множество B λ . Представимфункцию f в виде f (σ 0 , σ 00 ) = h(σ 0 , π(fσ00 (x0 ))). Схема для функции f строится вдва этапа: сначала по набору σ 00 строится код подфункции fσ00 (x0 ), а затем по этому коду и набору σ 0 однозначно восстанавливается значение f на наборе (σ 0 σ 00 ).Кодирование π — это система из λ булевых функций, каждая из которых представляет один бит кода и зависит от n − q переменных.
Систему функций π можнореализовать по асимптотически наилучшему методу синтеза схемой Σπ со сложноn−qстью . λ 2n−q . Функция h зависит от q + λ переменных, и её можно реализоватьпо асимптотически наилучшему методу синтеза схемой Σh со сложностью .Полагая q = dlog ne, и учитывая, что λ 6 σQ (q)2q + 1 . σQ 2q , получаем n22n−q2nL(Σπ ) = o, L(Σh ) . σQ 2q. σQ .nn−qn2q+λq+λ .В случае σQ > 0 отсюда, с учётом нижней оценки, следует первая часть доказываемого утверждения.
При σQ = 0 последовательность σQ (q) стремится к нулю,nоткуда L(Σh ) = o( 2n ), что доказывает вторую часть утвеждения.При доказательстве верхней оценки утверждения 8 мы фактически использовали приём, называемый принципом локального кодирования, предложенныйО. Б. Лупановым. Принцип локального кодирования состоит в следующем. ПустьQ — класс операторов, и пусть для каждого n определено кодирование π, ставящее в соответствие оператору F ∈ Q(n) двоичный набор (код) длины d = d(n),разбитый на “куски” длины 6 λ = λ(n). Пусть кодирование обладает свойством“локальности”: для вычисления значения оператора F на произвольном фиксированном наборе σ достаточно знать лишь один кусок кода, задаваемый своими координатами (например, позицией в коде и длиной). Пусть также кодирование и§5. Принцип локального кодирования19декодирование “просты”: по набору σ можно эффективно определять кусок кода,требущийся для вычисления F (σ), и производить это вычисление.
Тогда можноэффективно реализовать оператор F .В доказательстве утверждения 8 кодом функции мы считали совокупность кодов подфункций f (x0 , σ 00 ), а координатой куска кода служил набор σ 00 .Утверждение 9. Если выполнены следующие условия:1) общая длина кода асимптотически равна log |Q(n)|, то есть кодированиеасимптотически неизбыточно,2) сложность получения координат куска кода по набору σ равна o(J(Q(n))),3) сложность вычисления куска кода по его координатам не превосходитасимптотически J(Q(n)),4) сложность вычисления оператора F ∈ Q(n) по куску кода и набору σ равнаo(J(Q(n))),то L(Q(n)) ∼ J(Q(n)).Не всюду определённой ФАЛ называется отображение f : B n → {0, 1, ∗}. Приэтом если f (α) = ∗, то говорят, что функция f не определена на наборе α.
Множество {α ∈ B n | f (α) ∈ {0, 1}} называется областью определённости функции f иобозначается δ(f ). Множество всех не всюду определённых ФАЛ от n переменныхобозначается P̂2 (n). Доопределением функции f ∈ P̂2 (n) называется всякая функция g ∈ P2 (n), совпадающая с f на множестве δ(f ). Под сложностью не всюдуопределённой ФАЛ понимается наименьшая из сложностей её доопределений:LC (f ) =ming− доопред. fLC (g).Введём класс не всюду определённых ФАЛ с фиксированной мощностью областиопределённости:P̂2 (n, t) = {f ∈ P̂2 (n) | |δ(f )| = t}.Функция Шеннона для этого класса определяется стандартным образом:LC (P̂2 (n, t)) =max LC (f ).f ∈P^2 (n,t)(t = t(n))Утверждение 10.
Пусть t(n) n log n. Тогда LC (P̂2 (n, t(n))) ∼t(n)log t(n) .Доказательство. Нижняя оценка. Рассмотрим множество P̌2 (n, t) = {f ∈P̂2 (n, t) | δ(f ) = [0, t)}. Для каждой из 2t функций из P̌2 (n, t) выберем одно доопределение с минимальной сложностью, и множество этих доопределений обозначимQ (|Q| = 2t ).
Пользуясь стандартным мощностным методом получения нижних20Глава 1. Асимпотические оценки высокой степени точностиоценок можно показать, что найдётся хотя бы одна ФАЛ из Q сложности &значитt(n).LC (P̂ (n, t)) > LC (P̌2 (n, t)) &log t(n)tlog t ,аВерхняя оценка.
Пусть f ∈ P̂2 (n, t). Разложим f по БП x00 = (xq+1 , . . . , xn ):_Kσ00 (x00 )fσ00 (x0 ),f (x0 , x00 ) =σ 00 ∈B n−qгде x0 = (x1 , . . . , xq ). В указанном разложении fσ00 (x0 ) ∈ P̂2 (x0 , tσ00 ), причёмP0σ 00 tσ 00 = t. Пусть G ⊆ P2 (x ) — множество ФАЛ, являющихся доопределениями0функций из P̂2 (x ), которые равны нулю вне некоторого отрезка B q и обращаются в{0, 1} на µ наборах этого отрезка, построенное проектированием множества Am,µ навсевозможные отрезки длины m, m = µ, µ + 1, .
. .. Тогда |G| 6 22q 2q 2µ = 23q+µ , поэтому L(G) 6 24q+µ . Разобьём куб B q на отрезки I1 , . . . , Ip и представим ФАЛ(i)(p)(1)fσ00 (x0 ) в виде fσ00 ∨ . . . ∨ fσ00 , где fσ00 обращается в 0 вне отрезка Ii , причём(p)(i)|δ(fσ00 )| = µ при 1 6 i 6 p − 1 и |δ(fσ00 )| 6 µ, а p = pσ00 = d|δ(fσ00 )|/µe. Пусть, далее,W(p)(i)(1)(i)gσ00 из fσ00 из G и gσ00 = gσ00 ∨ . . . ∨ gσ00 — доопределение fσ00 .
Тогда g = σ00 Kσ00 gσ00— доопределение f , при этом L(g) 6 24q+µ + µt + O(2n−q ). При q = dn − log t + 2 log n,µ = dlog t − 4q − 2 log ne получаем L(g) . logt t , что и требовалось.Замечание. ПриρБ logt t . n выполнено асимптотическое равенство LCБ (P̂2 (n, t) ∼tlog tЗамечание. При построении оптимальной схемы для не всюду определённой функции f ∈ P̂2 (n, t) в общем случае невыгодно доопределять её нулём всюду на множестве B n \δ(f ). Для “типичной” ФАЛ из P̂2 (n) имеем |f −1 (0)| ∼ |f −1 (1)| ∼ |f −1 (∗)| ∼2n /3. Доопределяя функции из P̂2 (n, t) нулём, получим множество Q(n) всюдуопределённых функций, причём n 2log 3 2332log |Q(n)| ∼ log n∼ 2n (+ log ) = 2n · log √> 2n · ,32 /333234откуда LC (Q(n)) &23·2nn ,в то время как LC (P̂2 (n, d2n /3e)) ∼ 31 2n .Глава 2Синтез схем для индивидуальных функций и оценки ихсложности§1Средняя проводимость схемы.Асимптотика контактной сложности универсальных системфункцийИспользование так называемой средней проводимости контактов схемы позволяетв некоторых случаях получать более высокие по сравнению с леммой 2.3 [2, глава4] нижние оценки сложности реализации систем ФАЛ в классе UK .
Этот метод ужеприменялся, по существу, при доказательстве минимальности контактного деревав классе разделительных КС (см. лемму 2.5 [2, глава 4]).Будем называть множество δ, δ ⊆ B n , равномерным, если для каждого i, i ∈[1, n] число тех наборов α = (α1 , . . . , αn ) из δ, у которых αi = 1, равно |δ|2 . Заметим, что каждый контакт КС Σ = Σ (α1 , . . . , αn ) проводит (не проводит) ровнона половине всех наборов равномерного множества δ, δ ⊆ B n , и, следовательно, вобозначениях §§1,5 [2, глава 2] выполняются равенства11 X1 X|E (Σ|α )| =|E (Σ|α )| = L (Σ)(1.1)|δ||δ|2α∈δα∈δкоторые и задают "среднюю" проводимость (непроводимость) контактов Σ на наборах множества δ. В качестве множества δ мы, чаще всего, будем выбирать весьединичный куб B n , а для получения нижних оценок сумм (1.1) — использоватьнеравенства|E (Σ|α )| > |V (Σ)| − |c (Σ|α )|(1.2)|E (Σ|α )| > |c (Σ|α )| − |C (Σ)| ,(1.3)которые вытекают из неравенства (1.2) [2, глава 2].
Напомним, что в [2, глава 4]было доказано следующее утверждение.Лемма 1.1. Если система ФАЛ F = (f1 , . . . , fm ) состоит из попарно различныхи отличных от констант ФАЛ от БП X(n), тоK1−nL (F ) > 2mXNf .jj=12122Глава 2. Синтез схем для индивидуальных функцийСледствие 1. LK (Jn ) > 2n+1 − 2Следствие 2. Оценки следствия 1 и леммы 7.3 из [2, глава 4] дают асимптотическое равенство→−LK ( J n ) ∼ 2n+1Теорема 1.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
