Материалы для подготовки к экзамену (2012-2013 учебный год), страница 11

. . , 0), F (0, . . . , 0, 1), F (0, . . . , 0, 1, 1), . . . , F (1, . . . , 1) ), разбитый на(n + 1) непересекающихся кусков длины λ = m. При этом «координатами» i-го,i ∈ [0, n], куска кода πi = F ( (0, . . . , 0, 1, . . . , 1) ) будем считать набор νt−1 (i), где| {z }it = dlog(n + 1)e .(2)Следовательно, оператор декодирования An является тождественным опера(1)тором, а оператор кодирования An представляет собой счётчик числа единиц,который набор α = (α1 , .

. . , αn ) ∈ B n переводит в набор β, β ∈ B t , такой, чтоν(β) = α1 + · · · + αn , и имеет сложность [1]LC A(1)6 9n.nЗаметим, что основной оператор On может быть при этом выбран из множества P2m (t, n + 1), а его сложность в силу леммы 8.2 удовлетворяет неравенству t·mLC On .+ O(n).log tТаким образом, СФЭ Σ, реализующая оператор F и построенная на основеописанного выше локального кодирования, имеет сложностьm·n+ O(n),L(Σ) .log nкоторая асимптотически совпадает с нижней оценкой (9.7).Лемма доказана.§10. Синтез схем для не всюду определённых функций53Лемма 9.3. Для постоянной последовательности m = m(n) > 2, n = 1, 2, .

. . ,класс операторов Q, для которого множество Q(n) состоит из всех (n, m)операторов F = (f1 , . . . , fm ) таких, что fi (β) = f1 (α) при любом i, i ∈ [2, m],любом α, α ∈ B n , и ν(β) − ν(α) ≡ i − 1 (mod 2n ), является стандартным относительно функционала сложности схем из UC классом.nДоказательство. Так как |Q(n)| = 22 и, следовательно, J(Q(n)) = 2n /n, тоn = o(J(Q(n))) и Q — невырожденный класс операторов, а из леммы 8.1 непосредственно вытекает необходимая нижняя оценка 2nLC Q(n) &.nДля получения аналогичной верхней оценки возьмём произвольное натуральное n и натуральное q, q 6 n, а затем обычным образом разобьём набор БП x =(x1 , .

. . , xn ) на поднаборы x0 = (x1 , . . . , xq ) и x00 = (xq+1 , . . . , xn ). Выберем из Q(n)произвольный оператор F = (f1 , . . . , fm ) и положим f = f1 .Рассмотрим кодирование Π = Πn , которое сопоставляет оператору F = Fnнабор π длины d = 2n + (m − 1), получающийся удлинением столбца значений α̃fФАЛ f первыми (m − 1) разрядами этого же столбца. Выделим в этом наборе 2n−qкусков πσ00 , σ 00 ∈ B n−q , длины λ = 2q +(m−1), где кусок πσ00 получается удлинениемтой части столбца α̃f , которая соответствует ФАЛ f (x0 , σ 00 ), на (m − 1) следующийза ней разряд.Легко видеть, что построенное кодирование обладает свойством локальностии что координатами куска кода πσ00 можно считать индексирующий его набор σ 00 ,(1)σ 00 ∈ B n−q . При этом оператор кодирования An является оператором выбора под(2)набора x00 из набора x, а оператор декодирования An и основной операторOn1mλпринадлежат множествам P2 (q + λ) и P2 (n − q) соответственно.

При q = 2 log nдля сложности указанных операторов будут выполняться соотношения 2n 2q+λLC A(2).m·=o,nq+λn 2n−q2n∼,On . 2q + (m − 1) ·n−qnLC A(1)= 0,nLCиз которых следует, что 2nLC Fn ..nЛемма доказана.§10Синтез схем для не всюду определённых функцийВ заключение части I рассмотрим задачу синтеза схем для не всюду определённыхфункций, которая близка к задаче синтеза схем для ФАЛ из специальных классов.54Глава 1.fОтображение f : B n 7→ [0, 2] будем называть не всюду определённой ФАЛ от nБП, а множество f −1 ({0, 1}) будем считать её областью определённости и обозначать через δ(f ). При этом доопределением указанной функции f считается любаяФАЛ из P2 (n), совпадающая с f на множестве δ(f ), а под сложностью LC (f ) реализации функции f в классе UC понимается наименьшая из соответствующихсложностей её доопределений.Обозначим через Pb2 (n) множество всех не всюду определённых ФАЛ отБП X(n) = {x1 , .

. . , xn } и для любого t, t ∈ [0, 2n ], введём его подкласс Pb2 (n, t),состоящий из всех тех функций f , f ∈ Pb2 (n), для которых |δ(f )| = t.Функция Шеннона для этого класса определяется стандартным образом:LC Pb2 (n, t) =max LC (f ),f ∈Pb2 (n,t)причём считается, как обычно, что t = t(n), n = 1, 2, . . . .Лемма 10.1. Если n log n = o(t(n)), тоLC Pb2 (n, t(n)) &t(n).log t(n)(10.1)Доказательство.

Для n = 1, 2, . . . рассмотрим множествоP̌2 (n, t) = {f ∈ Pb2 (n, t) | δ(f ) = [0, t)},для каждой из 2t его функций выберем одно доопределение с минимальной сложностью, и множество этих доопределений обозначим через Q(n) = Q. Так какразличные функции из P̌2 (n, t) не могут иметь общих доопределений, то|P̌2 (n, t)| = |Q| = 2t ,J(Q) =t.log tИз последнего равенства и условий леммы следует, что n = o J(|Q(n)|) , то естькласс ФАЛ Q(1), .

. . , Q(n), является невырожденным. Из этой невырожденности,леммы 8.1 и очевидных соотношенийLC Q(n) = LC P̌2 (n, t) 6 LC Pb2 (n, t)вытекает оценка (10.1).Лемма доказана.Рассмотрим, далее, несколько утверждений, позволяющих установить для исследуемой функции Шеннона верхнюю оценку вида правой части (10.1) при последовательно ослабляемых ограничениях на рост функции t = t(n).§10.

Синтез схем для не всюду определённых функций55Лемма 10.2. Если t = t(n) ∼ n, тоLC Pb2 (n, t) .t(n).log t(n)(10.2)Доказательство. Для произвольного натурального n и натурального q, 1 6 q < n,разобъём, как обычно, набор БП x = (x1 , . . . , xn ) на поднаборы x0 = (x1 , . . .

, xq )и x00 = (xq+1 , . . . , xn ). Выберем натуральный параметр µ, µ 6 2q , и для любого s, s 62q , построим такое множество наборов As куба B s , которое «протыкает» (см. [3]) всеграни ранга не больше чем µ, этого куба и состоит не более, чем из s · 2µ наборов.Для каждого отрезка I куба B q от БП x0 рассмотрим множество GI , состоящееиз тех равных 0 вне I ФАЛ P2 (x0 ), «проекции» столбцов значений которых на Iпринадлежат множеству As , где s = |I|.Определим множество ФАЛ G как объединение множеств GI по всем отрезкамкуба B q (x0 ) и заметим, что→−|G| 6 2µ+3q ,LC G 6 2µ+4q .(10.3)Заметим также, что любая ФАЛ gb из Pb2 (q, t0 ), где t0 6 µ, равная 0 вне отрезка Iкуба B q от БП x0 , имеет в GI доопределение.Возьмём произвольную функцию f , f ∈ Pb2 (n, t), и разложим её по БП x00 :_f (x0 , x00 ) =Kσ00 (x00 )fσ00 (x0 ),(10.4)σ 00 ∈B n−qгде при любом σ 00 , σ 00 ∈ B n−q , функция fσ00 (x0 ) принадлежит множеству Pb2 (x0 , tσ00 ),причём Σσ00 tσ00 = t.Для каждого набора σ 00 , σ 00 ∈ B n−q , положим pσ00 = dtσ00 /µe и розобьём куб B qот БП x0 на последовательные отрезки I1 , .

. . , Ipσ00 так, чтобы при любом i, i ∈[1, pσ00 ], та часть столбца значений функции fσ00 (x0 ), которая связана с отрезком Iiсодержала µ (соответственно не больше, чем µ) булевских значений, если i < pσ00(i)(соответственно i = pσ00 ).

Пусть, далее, функция fσ00 (x0 ), i = 1, 2, . . . , pσ00 , совпадает(i)с функцией fσ00 на отрезке Ii и равна 0 вне его, а ФАЛ gσ00 из GIi является еёдоопределением. Отсюда следует, что функция fσ00 может быть представлена ввиде(p 00 )(1)fσ00 = fσ00 ∨ · · · ∨ fσ00σ(10.5)и поэтому её доопределением является ФАЛ(p(1)00 )gσ00 = gσ00 ∨ · · · ∨ gσ00σ .Из (10.3)–(10.6) следует, что ФАЛ g(x) вида p_σ 00_(i) 0g(x) =Kσ00gσ00 (x ) ,σ 00 ∈B n−qi=1(10.6)(10.7)56Глава 1.(i)где gσ00 ∈ G при любых σ 00 , σ 00 ∈ B n−q , и i, i ∈ [1, pσ00 ], является доопределениемФАЛ f и что на основе (10.7) можно построить СФЭ Σ, которая реализует ФАЛ gсо сложностьюL(Σ) 6 24q+µ + t/µ + O(2n−q ).Из последнего неравенства приq = dn − log t + 2 log ne ,µ = dlog t − 4q − 2 log neполучаем требуемую оценкуLC (g) .t.log tЛемма доказана.Замечание.

Из леммы 10.2 вытекает что, при построении оптимальной схемы дляне всюду определённой функции f , f ∈ Pb2 (n, t), в общем случае невыгодно доопределять её нулями на множестве B n \ δ(f ). Действительно, полагая t = d2n /3e идоопределяя функции из Pb2 (n, t) нулями, получим множество Q(n) всюду определённых функций, для которого2233d2n /3en log 3log |Q(n)| ∼ log C2n∼2> 2n · .+ log= 2n · log √333234В силу леммы 8.1 отсюда следует, что 2 2nLC Q(n) & · ,3 nв то время как 1LC Pb2 (n, d2n /3e) ∼ · 2n .3Введём некоторые понятия и рассмотрим связанные с ними конструкции, позволяющие ослабить условия леммы 10.2.Пусть n и s, s 6 n, — натуральные числа, а A — произвольное множество наборов куба B n и |A| 6 2s .

Будем говорить, что (n, s)– оператор ψ, ψ ∈ P2s (n),является оператором разделения или, иначе, оператором хэширования для A, если ψ(α) 6= ψ(β) для любых различных наборов α и β из A. Обозначим через Λкласс линейных ФАЛ с нулевым свободным членом и будем выбирать нужные намоператоры разделения из множества Λs (n).Лемма 10.3. Для любого множества A, A ⊆ B n , и любого s, s 6 n, существуетоператор ψ, ψ ∈ Λs (n), разделяющий некоторое множество A0 , A0 ⊆ A, такое,чтоt(t − 1)|A0 | > t − s+1 ,2где t = |A|.§10. Синтез схем для не всюду определённых функций57Доказательство. Рассмотрим множество Λs (n) как вероятностное пространство,в котором вероятность выбора любого из 2ns операторов равна 2−ns .

В этой модели для любых различных наборов α и β из B n вероятность того, что случайный оператор из Λs (n) их не разделит, равна 2−s . Действительно, для наборов α = (α1 , . . . , αn ) 6= β = (β1 , . . . , βn ) число не разделяющих их линейных ФАЛвида γ1 x1 ⊕ · · · ⊕ γn xn равно числу тех наборов γ = (γ1 , . . . , γn ) из B n , для которых γ1 (α1 ⊕ β1 ) ⊕ · · · ⊕ γn (αn ⊕ βn ) = 0, то есть равно 2n−1 , а значит число техоператоров из Λs (n), которое не разделяют α и β, равно 2s(n−1) .Отсюда следует, что математическое ожидание числа не разделённых случайным оператором из Λs (n) неупорядоченных пар различных наборов из A равна t(t − 1)/2s+1 . Это означает, что найдётся такой оператор ψ, ψ ∈ Λs (n), длякоторого множество R, состоящее из не разделённых им пар наборов указанноговида имеет мощность r, где r 6 t(t − 1)/2.Индукцией по r легко показать, что мощность минимального по включениюподмножества A00 множества A, которое «протыкает» все пары из R, то есть имеетс каждой из них непустое пересечение, не больше, чем r.