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

Московский государственный университет имениМ. В. ЛомоносоваФакультет вычислительной математики и кибернетикиС. А. ЛожкинДополнительные главыкибернетики и теорииуправляющих системМосква 2008Оглавление1 Асимпотические оценки высокой степени точности3§1 Некоторые модификации КС, ИКС. Верхние оценки числа схемконтактного типа, нижние мощностные оценки функции Шеннона .3§2 Универсальные системы ФАЛ и их построение на основе селекторныхразбиений БП .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9§3 Мультиплексорные ФАЛ и обощенное разложение. Оптимальная позадержке реализация мультиплексорных ФАЛ в произвольном базисе 12§4 Задача синтеза схем для функций из специальных классов, примерыеё решения и мощностные нижние оценки. Инвариантные классыС. В. Яблонского, теорема о числе инвариантных классов . .

. . . . . 13§5 Принцип локального кодирования и примеры его применения. Синтезсхем для не всюду определённых ФАЛ . . . . . . . . . . . . . . . . . . 182 Синтез схем для индивидуальных функций и оценки ихсложности§1 Средняя проводимость схемы.Асимптотика контактной сложности дешифраторов и универсальныхсистем функций . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .§2 Незабиваемые множества функций.Асимптотика сложности мультиплексора в некоторых классах схем .§3 Сложность линейной функции в классе схем из функциональныхэлементов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . .§4 Сферические функции. Сложность линейной и других функций вклассе контактных схем . . . . . . . . . . . . . . . . . . . . . . . . . .§5 Теорема Храпченко. Сложность линейной функции в классе π–схем .Литература212123273033372Глава 1Асимпотические оценки высокой степени точности§1Некоторые модификации КС, ИКС. Верхние оценки числасхем контактного типа, нижние мощностные оценки функцииШеннонаРассмотрим одну модификацию КС, которая является, по существу, частным случаем т. н.

релейно-контактных схем (см., например, [?]) и связана с операциейприсоединения управляющих БП (входов) КС к ее выходам.Для КС Σ = Σ (x1 , . . . , xn ; 1; z1 , . . . , zm ) определим обычным образом операциюприсоединения ее управляющей БП xi к выходу zj , которая применима, если БП xiвходит в Σ без отрицаний, а ее контакты не лежат на простых проводящих цепях,соединяющих вход 1 с выходом zj . Заметим, что при этом ФАЛ fj , реализуемая навыходе zj КС Σ, не зависит от xi .

В результате выполнения указанной операциив графе КС Σ происходит снятие БП zj , сопоставление связанной с ней вершиневнутренней БП y и замена всех пометок xi на пометку y.Аналогично определяется операция (одновременного) присоединения нескольких управляющих БП КС Σ к ее выходам, при выполнении которой каждой участвующей в присоединениях выходной вершине Σ сопоставляется только одна внутренняя БП, причем разным вершинам сопоставляются разные БП. Любая из полученных таким образом схем называется итеративной контактной схемой (ИКС)на базе КС Σ. Под сложностью L (Σ0 ) ИКС Σ0 на базе КС Σ понимается сложностьL (Σ).Функционированние ИКС Σ (x1 , .

. . , xn ; z1 , . . . , zm ) на базе КС видаΣ̂ (x1 , . . . , xn , y10 , . . . , yl0 ; 1; y100 , . . . , yl00 , z1 , . . . , zm )свнутреннимиБПyi = yi0 = yi00 , i = 1, . . . , l, рассматривается в дискретные моменты времени.Для любого входного набора (α1 , . . . , αn ) ∈ B n при t = 0, 1, . . . происxодит последовательное установление в различных вершинах 1 за счет образования цепейиз проводящих к данному моменту контактов и 0 за счет образования разрезовиз непроводящих к данному моменту контактов. Вершина ui , связанная с БПyi , 1 6 i 6 l, в которой установилось значение σ, начинает в слудующий моментуправлять проводимостью контактов yi и т.д.

Считается, что в тех вершинах, вкоторых значение 0 и 1 не установились, имеется неопределенное значение 2. Этотпроцесс завершается, когда в каждой вершине окончательно устанавливается значение 0, 1 или 2. При этом ИКС Σ называется комбинационной схемой (схемой34Глава 1. Асимпотические оценки высокой степени точности1j•/TTjjjj /// TTTTyT1TTjjjTTT/' jjj x1 //y2•/•j//// ''/'/ x3TTTT '••tTTTT ///''ttx2 tTx3 TTT/ x2 t''tt • tttt x'' 2 x2z1 = x 1 ⊕ x 2 ⊕ x 3'' t•t'y1'x1•y2Рис.

1.1: Пример ИКС1?• ?????x2x1 ?????••y2y1y1••y2Рис. 1.2: Пример некомбинационной ИКСбез памяти), если для любого входного набора (α1 , . . . , αn ) ∈ B n её функционирование завершается определенными значениями во всех выходных вершинахz1 , . . . , zm , которые определяют значения ФАЛ f1 , . . . , fm , реализуемых Σ.Пусть БП y1 = y10 = y100 , . . . , yl = yl0 = yl00 ИКС Σ (x1 , . . .

, xn ; z1 , . . . , zm ) на базеКС Σ̂ (x1 , . . . , xn , y10 , . . . , yl0 ; 1; y100 , . . . , yl00 , z1 , . . . , zm ) — упорядочены, и ФАЛ проводимости от 1 к yi может существенно зависеть только от БП x1 , . . . , xn , y1 , . . . , yi−1 ,тогда ИКС Σ будет комбинационной.Обозначим, как обычно, через UИКС класс всех комбинационных ИКС из неориентированных контактов, а через UИКС (L, n) — множество ИКС от БП X (n),которые ИКС имеют один выход, приведенную базу и сложность не более L.

ТогдаU(L, n) —, как обычно, число попарно неэквивалентных ИКС из UИКС (L, n).Лемма 1.1. Число попарно неизоморфных связных графов с параллельными ребра 2 q−p+13pми, содержащих p вершин и q ребер, q > p − 1, не больше, чем 4p−1 q−p+1,еслиp (p + 1)q6− 2,(1.1)2§1. Некоторые модификации КС, ИКС. Нижние оценки функции Шеннона5и не более, чем 4p−1 · 6q−p+1 в остальных случаях.Доказательство. Подсчет указанных графов можно организовать следующим образом: сначала выбирается остовное дерево, а потом оставшиеся ребра распределяются по всевозможным парам вершин с возможными повторениями. Остовноедерево можно выбрать 4p−1 способами, а число возможных распределений оставшихся ребер по парам вершин можно оценить сверху числом сочетаний с повторениями, при условии, что число пар вершин равно p(p−1). Так как число сочетаний с 2 n+k−1n+k−1повторениями из n элементов по k равно n−1 =, то, используя известkное неравенство m3m n6,nnполучим следующую цепочку неравенств:4p−1 · p(p−1)+q−p2q−p+16 4p−1 ·Если выполняется неравенство (1.1), тогдапродолжить следующим образом:p−14·p(p−1)2−13 1+q−p+1!!q−p+1p(p−1)2−13 1+q−p+1p(p−1)−12q−p+1!!q−p+1.> 1 и цепочку (1.2) можноp2p2+642 (q − p + 1) 2 (q − p + 1)q−p+13p2p−164·.q−p+1p−1(1.2) · 3q−p+1В противном случае, неравенства (1.2) можно продолжить следующим образом:4p−1 ·p(p−1)2−13 1+q−p+1!!q−p+16 4p−1 · (3 (1 + 1))q−p+1 6 6q−p+1 ,что завершает доказательство.Лемма доказана.Следствие 1.

В случае ориентированных графов, оценки леммы умножаются на2q .Следствие 2. Число попарно неизоморфных связанных неориентированных графов на p вершинах, содержащих не более q ребер, не превосходитq4 · max16p6q+13p2q−p+1q−p+1.66Глава 1. Асимпотические оценки высокой степени точностиЛемма 1.2. Пусть a, m, τ, α - действительные параметры такие, чтоa > 2, m > 1, τ > 1, α > 0,Тогда выполняется неравенствоm−ymay τmaxy αm 6 βtmα (log t)−α−τ ,06y6m m − yгде β = β (α, τ ) , t = amτ −1 .Доказательство. Введем обозначения:m−yay τy αm ,F (y) =m−yf (y) = ln F (y) = (m − y) lnay τm−y+ αm ln y.Далее через β1 , β2 , .

. . будем обозначать некоторые функции величин α и τ . Пустьy = z · m, m ∈ [0, 1]. Тогда, дифференцируя f (y), получимm (τ + α)ay τ0f (y) =− ln−τ +1=ym−y τ τ +αz=− ln− τ + 1 − ln amτ −1 .z1−z| {z }{z}|>0δ(z)Заметим, что δ (z) → −∞ при z → 1, и существует β1 < 1 такое, что f 0 (y) < 0при y > β1 m. Пусть ξ является точкой максимума функции f , тогда f 0 (ξ) = 0 иξ 6 β1 m. Если обе части последнего неравенства умножить на −1, прибавить m,разделить на (1 − β1 ), и возвести в степень τ1 , то получим неравенство11m τ 6 β2 (m − ξ) τ .(1.3)Распишем условие f 0 (ξ) = 0:m (τ + α)− τ lnξ11e(1− τ ) a τ ξ1!= 0.(m − ξ) τ1Обозначив e1− τ через β3 , из (1.4) и (1.3) получаем!111aτ ξaτ ξm(τ + α)aτ ξln β3· β3· β311 =1 =ξτ(m − ξ) τ(m − ξ) τ(m − ξ) τ1τ +αma τ1− τ1 τ1= β3·a ,1 6 β4 mτ(m − ξ) τ| {z }1>m τ /β2(1.4)§1.

Некоторые модификации КС, ИКС. Нижние оценки функции Шеннона1111− ττ, u = β3где β4 = β2 β3 τ +ατ . Обозначим w = β4 a m7aτ ξ1(m−ξ) τ. Тогда, как показановыше, w > u ln u, откуда u 6 r lnww для некоторой константы r (можно положитьr = 2). Отсюда, положив β5 = rβ4−1 , имеем1aτ ξ1(m − ξ) τ1τ1− τ16 β5 a m1τ· ln β4 a m1− τ1−11β5β tτ(amτ −1 )1/τ 6 6 , (1.5)=·1/ττ−1τ ln β4 (am )log tгде t = amτ −1 .

Из последнего неравенства следует, что(m − ξ)1/τ β6 t1/τβ6 m·ξ6=·1/τlog tlog tam−ξm1/τ6β7 m.log t(1.6)Пользуясь неравенствами (1.5) и (1.6), получаем!τ m1maτ ξξ αm 6 βtmα (log t)−α−τ .max F (y) = F (ξ) 6106y6m(m − y) τЛемма доказана.Теорема 1.1. Для любых натуральных n, L выполняются неравенства KU (L, n) 6c1 nLlog2 LL,(1.7) − c nL L →2K,U (L, n) 6log2 L(1.8) ИКСU(L, n) 6c3 (n + L)2log3 (n + L)!L+2n,(1.9)где c1 , c2 и c3 - некоторые положительные константы.Доказательство. Число попарно неэквивалентных КС из неориентированных(ориентированных) контактов можно оценить сверху числом попарно неизоморфных связанных неориентированных (ориентированных) графов, умноженных начисло возможных распределений пометок ребер. Для этого воспользуемся следствием 2 леммы 1.1 и результатами леммы 1.2.

Пустьa = 3, m = q + 1, τ = 2, α = 0, y = p,тогда верны следующие неравенства:q4 · max06p6q+13p2q−p+1q−p+16c1 qlog2 qq.(1.10)8Глава 1. Асимпотические оценки высокой степени точностиВ случае ориентированных КС по следствию 1 леммы 1.1 последнее неравенствоумножается на 2q , что повлияет только на константу в знаменателе дроби, котораястанет равна 2c1 . Остается заметить, что число возможных пометок КС с q ребрамиравно (2n)q и что число ребер совпадает со сложностью КС. В итоге умножаянеравенство 1.10 на nq и заменяя q на L, получаем неравенства 1.7 и 1.8.Так как число возможных распределений пометок ребер для ИКС с q контактами равно (2n + p)q , то верны следующие неравенства:q−p+1 ИКС3p2U(L, n) 6 4q · max(2n + p)q .(1.11)06p6q+1 q − p + 1Воспользуемся леммой 1.2.

Пустьa = 3, m = q + 2n + 1, τ = 2, α = 1, y = p + 2n,тогда неравенства 1.11 можно продолжить следующим образом:4q · max06p6q+13p2q−p+1q−p+1q(2n + p) 6c3 (n + q)2log3 (n + q)!q+2n.В итоге, заменяя q на L, получим справедливость неравенства 1.9.Теорема доказана.Теорема 1.2. Для любого натурального n выполняются неравенства2 log n − o (1)2nK1+,L (n) >nn−→2n2 log n − o (1)KL (n) >1+,nn!5n−1logn−o(1)2LИКС (n) >1+ 2,nnДоказательство.Для доказательства теоремы воспользуемся "мощностным"nтождеством UP (L, n) = 22 , которое вытекает непосредственно из определений,а так же результатами теоремы 1.1 и известной верхней асимптотической оценкойnдля КС и ориентированных КС вида 2n .

В случае ИКС справедливость этой оценки вытекает из того, что КС являются частным случаем ИКС. Таким образом вслучае КС, используя неравенство 1.7, получаем следующие неравенства:2n26c1 nLK (n)log2 LK (n)LK (n).Логарифмируя неравенство, получим2n 6 LK (n) c01 + n − 2 log n + O (n) .§2. Универсальные системы ФАЛ9В итоге получаем оценку2n2n− O (n) >L (n) >0n − 2 log n + c1nK2 log n − o (1)1+nДоказательство верхней оценки в случае ориентированных КС повторяет доказательство для неориентированных КС, а в случае ИКС необходимо произвестианалогичные выкладки, но с использованием неравенства 1.9.