Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Материалы для подготовки к экзамену (2012-2013 учебный год)

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

Описание файла

PDF-файл из архива "Материалы для подготовки к экзамену (2012-2013 учебный год)", который расположен в категории "к экзамену/зачёту". Всё это находится в предмете "дополнительные главы кибернетики и теории управляющих систем" из седьмого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 11 страницы из PDF

. . , 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.

Свежие статьи
Популярно сейчас