Материалы для подготовки к экзамену (2012-2013 учебный год) (1156402), страница 2
Текст из файла (страница 2)
Так как число сочетаний с 2 n+k−1n+k−1повторениями из n элементов по k равно n−1 =, то, используя известkное неравенство n3m n6,nmполучим при условии q > p − 1 следующее неравенство:!!q−p+1 p(p−1)p(p−1)−1+q−pp−1p−12264· 3 1+.(1.3)4·q−p+1q−p+1§1.7Из неравенства (1.2) вытекает, чтоp(p−1)2−1>1q−p+1и поэтому неравенство (1.3) можно продолжить в случае (1.2) следующим образом:p−14·p(p−1)2−13 1+q−p+1!!q−p+1p2p264+2(q − p + 1) 2(q − p + 1)q−p+13p2p−164·.q−p+1p−1 · 3q−p+16В случае q = p − 1 рассматриваемые графы являются деревьями, число которыхне больше, чем 4p−1 = 4p−1 · 6q−p+1 . В остальных случаях, неравенство (1.3) можнопродолжить следующим образом:4p−1 ·p(p−1)2−13 1+q−p+1!!q−p+16 4p−1 · (3(1 + 1))q−p+1 6 4p−1 · 6q−p+1 ,что завершает доказательство.Лемма доказана.Следствие.
В случае ориентированных графов, оценки леммы умножаются на 2q .Лемма 1.2. Если a, m, τ, α — действительные параметры такие, чтоa > 2,m > 1,τ > 1,α > 0,то выполняется неравенствоmax06y6may τm−ym−yy αm 6 βtmα (log t)−α−τm,где β = β(α, τ ), t = amτ −1 .Доказательство. Введём обозначения:ay τm−ym−yy αm ,ay τf (y) = ln F (y) = (m − y) ln+ αm ln y.m−yF (y) =8Глава 1.Далее, через β1 , β2 , . .
. будем обозначать некоторые функции величин α и τ . Пустьy = z · m, где z ∈ [0, 1]. Тогда, дифференцируя f (y), получимm(τ + α)ay τ−τ +1=f 0 (y) =− lnym−y τ τ +αz=− τ + 1 − ln amτ −1 .− lnz1−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.4)В точке максимума выполняется условие f 0 (ξ) = 0, из которого следует, что!11e(1− τ ) a τ ξm(τ + α)= 0.(1.5)− τ ln1ξ(m − ξ) τ1Обозначив e1− τ через β3 , из (1.5) и (1.4) получаем!111aτ ξaτ ξm(τ + α)aτ ξ· β3· β3ln β311 =1 =ξτ(m − ξ) τ(m − ξ) τ(m − ξ) τ1τ +αma τ1− τ1 τ1= β3a ,·1 6 β4 mτ(m − ξ) τ| {z }1>m τ /β21111− ττгде β4 = β2 β3 τ +α, u = β3τ . Положим w = β4 a maτ ξ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(amτ −1 )1/τβ tτ 6 6 , (1.6)=·τ ln β4 (amτ −1 )1/τlog tгде t = amτ −1 . Из последнего неравенства следует, что(m − ξ)1/τ β6 t1/τβ6 mξ6·=·1/τlog tlog tam−ξm1/τ6β7 m.log t(1.7)§1.9Пользуясь неравенствами (1.6) и (1.7), получаем!τ m1max F (y) = F (ξ) 606y6maτ ξ(m − y)1τξ αm 6 βtmα (log t)−α−τm.Лемма доказана.Теорема 1.1. Для любых натуральных n и L выполняются неравенства1 КСU (L, n) 6e1 nLlog2 LL,(1.8) −→ e nL L КС2,U (L, n) 6log2 LL+2n ИКСe3 (n + L)2U(L, n) 6.log3 (n + L)(1.9)(1.10)Доказательство.
Введём сначала некоторые вспомогательные величины и установим для них верхние оценки на основе лемм 1.1, 1.2. Пусть N(q) — число попарноне изоморфных связных неориентированных графов с не более чем q (возможно,bпараллельными) ребрами, а N(q)— число аналогичных графов, в каждом из которых любое ребро помечено либо одним из s специальных символов, либо одной извершин данного графа.Заметим, чтоN(q) =q Xt+1Xt=1 p=1N(p, t),bи N(q)6q Xt+1XN(p, t) · (p + s)t ,(1.11)t=1 p=1где N(q, t) — число попарно неизоморфных связных неориентированных графовс p вершинами и t (возможно, параллельными) ребрами, которое оценивалось вb s)лемме 1.1. Для удобства работы с этими оценками введем функции Q(t) и Q(t,натуральных аргументов t и s вида(()t−p+1 )q−p+123p23ptb s) = maxQ(t) = max, Q(t,· (p + s) ,16p6t16p6tq−p+1q−p+1(1.12)где максимум берется по всем действительным значениям параметра p из отрезка [1, t].Из (1.12) следует, чтоb s) 6 Q(t) · (t + s)t ,Q(t,(1.13)1Буквой e с различными индексами обозначаются некоторые положительные константы.10Глава 1.b s) монотонно не убывают по t, так как при t0 > t ии что функции Q(t), Q(t,p0 = p + (t0 − t) выполняются неравенства3(p0 )2t0 − p0 + 1t0 −p0 +1>3p2t−p+1t−p+10(p0 + s)t > (p + s)t .иЗаметим также, чтоQ(t) > 3tиДействительно, в случае t > 4 и p =Q(t) >3t2+1t22 ! 2tt2b s) >Q(t,tt2 t3· (t + s)t .2+ 1 выполняются неравенстваb s) > 3t ·Q(t,>9 =3,(1.14)t+s+12t t3>· (t + s)t ,2а в случае 1 6 t 6 3 и p = t — неравенстваQ(t) > 3t2 > 3t ,b s) > 3t · (t + s)t ,Q(t,которые в совокупности доказывают (1.14).Опираясь на лемму 1.1, соотношения (1.11)–(1.14) и монотонность функцийb s) по t, докажем, чтоQ(t), Q(t,N(q) 6 5 · 4q · Q(q),b s) 6 5 · 4q · Q(q,b s)(q + s)q ,N(q,(1.15)Действительно, используя оценки леммы 1.1 и первые части соотношений (1.11), (1.12),получимN(q) =q Xt+1XN(p, t) 6t=1 p=1q Xt+1X4p−1 6t−p+1 +t=1 p=1=qXt=1q XtX4p−1 Q(t) =t=2 p=2 tqt+1 p−1XX24 −1t6+Q(t),33p=1t=2откуда в силу монотонности Q(t) и первого из неравенств (1.14) следует, чтоN(q) 618 q 4 q· 6 + · 4 · Q(q) 6 5 · 4q · Q(q).59Второе из неравенств (1.15) устанавливается аналогично с использованием вторых частей соотношений (1.11), (1.12), (1.14), а также неравенства (1.13).Неравенстваqq+sqq+sb,иN(q, s) 6 e0 3(1.16)N(q) 6 e0 2log qlog (q + s)§1.11вытекают, с учетом (1.12), (1.15), из леммы 1.2, гдеa = 3, m = q + 1, τ = 2, α = 0, y = p и a = 3, m = q + s + 1, τ = 2, α = 1, y = p + sсоответственно.Оценки (1.8) и (1.9) получаются, с учетом леммы 1.1 и её следствия, из первого неравенства (1.16) при q = L, так как число попарно неэквивалентных КСрассматриваемого вида из неориентированных контактов можно оценить сверхупроизведением числа попарно неизоморфных связных неориентированных графовс не более чем L рёбрами и двумя полюсами на число возможных способов выборапометок их рёбер БП x1 , .
. . , xn или отрицаниями этих БП.Для доказательства (1.10) заметим, что число возможных способов выборапометок рёбер для ИКС рассматриваемого вида с p вершинами не превосходит(2n + p)L . Следовательно, справедливо неравенство: ИКСbU2n) · L2 ,(L, n) 6 N(L,из которого неравенство (1.10) вытекает в силу второго неравенства (1.16).Теорема доказана.На основе теоремы 1.1 c помощью мощностного метода Шеннона обычным образом (см., например, [3]) устанавливаются нижние мощностные оценки функций−→−→Шеннона LКС (n), LКС (n), LИКС (n) для классов UКС , UКС и UИКС соответственно.Теорема 1.2. Для натуральных n = 1, 2, .
. . выполняются неравенства2n2 log n − O(1)КСL (n) >1+,nn−→2n2 log n − O(1)LКС (n) >1+,nn!5n−1logn−O(1)2LИКС (n) >1+ 2.nn(1.17)(1.18)(1.19)Доказательство. Неравенства (1.17)–(1.19) могут быть получены в результате применения соотношения (4.1) и леммы 4.1 из §4 гл. 4 пособия [3] к (1.8)–(1.10). Приведём, тем не менее, технически более простой вариант доказательства (1.17)–(1.19),опирающийся на тот факт, что все рассматриваемые функции Шеннона имеют поnрядок роста 2n , то есть, в частности,LA (n) 6 c2n,n−→где A ∈ { КС, КС, ИКС }, а c — некоторая константа, не зависящая от n.(1.20)12Глава 1.В силу (1.20) и равенства Шеннона (см. [3]) A AU L (n), n = 22nиз (1.8)–(1.10) следует, что2n = logUКС LКС (n), n 6 LКС (n) · (n − 2 log n + O(1)),−→ −→ −→2n = logUКС LКС (n), n 6 LКС (n) · (n − 2 log n + O(1)),2n = logUИКС LИКС (n), n 6 LИКС (n) + 2n · (2n − 5 log n + O(1)).Решение полученных неравенств относительно соответствующих функций Шеннона даёт (1.17)–(1.19).Теорема доказана.§2Формулы и СФЭ в произвольном базисе, усилительные СФЭ.Верхние оценки числа формул и СФЭ, нижние мощностныеоценки функций ШеннонаПродолжим начатое в [3] (см.
гл. 2, 4) изучение формул и схем из функциональныхэлементов (СФЭ) над произвольным конечным полным базисом Б = {Ei }bi=1 , гдефункциональный элемент (ФЭ) Ei реализует ФАЛ ϕi (x1 , . . . , xki ), которая в случаеki > 2 существенно зависит от всех своих переменных.Будем по-прежнему (ср. с §3 главы 2 пособия [3]) представлять СФЭ Σ в видеΣ = Σ(x; z), если x = (xi1 , . . . , xin ) и z = (zj1 , . . . , zjn ) — наборы, составленные извсех её различных входных и выходных булевых переменных (БП), перечисленныхв порядке возрастания их номеров в алфавитах X = {x1 , x2 , .
. . , xn , . . . } и Z == {z1 , z2 , . . . , zm , . . . }, соответственно. Сложность, то есть число ФЭ, глубину, тоесть максимальное число последовательно соединённых ФЭ, и ранг, то есть числодуг, исходящих из входов, в схеме Σ, следуя [3], будем обозначать через L(Σ), D(Σ)и R(Σ) соответственно.Будем рассматривать формулы и СФЭ с различными ограничениями на соединения ФЭ.
Так, для базисов, имеющих одновходовые неконстантные ФЭ, введём понятие усилительной СФЭ — СФЭ, в которой «ветвятся» выходы толькоуказанных ФЭ. Заметим, что данное ограничение выполняется во многих классах электронных схем, причем в соответствующих базисах имеются специальные«усилительные» ФЭ, реализующие тождественную ФАЛ.Введём теперь «взвешенные» функционалы сложности и глубины СФЭ. Будемсчитать, что каждому функциональному элементу Ei , i = 1, . . . , b, сопоставленыположительные действительные числа Li и Ti , называемые его «весом» и «задержкой», которые характеризуют сложность («размер») и время срабатыванияE1 соответственно. Предполагается, что «вес» и «задержка» любого ФЭ стандартного базиса Б0 = {&, ∨, ¬} равны 1.
Если (v0 , vt )-цепь C длины t в СФЭ Σ проходит§2.13через вершины v1 , . . . , vt−1 , и вершине vj , j = 1, . . . , t, при этом соответствует ФЭEij базиса Б, то число T (C) = Ti1 + · · · + Tit будем называть задержкой этой цепи.По аналогии с глубиной определим задержку вершины v СФЭ Σ как максимальную задержку тех цепей Σ, которые начинаются в одной из ее входных вершин и заканчиваются в вершине v. Для каждой СФЭ Σ над базисом Б помимосложности L(Σ), глубины D(Σ) и ранга R(Σ) определим следующие параметры(функционалы сложности):1) L(Σ) — размер Σ, то есть сумма «весов» всех её ФЭ;2) T (Σ) — задержка Σ, то есть максимальная задержка её вершин.Заметим, что функционал L (D) является частным случаем функционала L (соответственно T ), когда веса (соответственно задержки) всех ФЭ базиса Б равны 1.Введем также «частичный» размер LБ0 (Σ) (задержку TБ0 (Σ)), который равен сумме весов ФЭ Σ типа Ei , где Ei ∈ Б0 , в СФЭ Σ (соответственно максимальной суммезадержек ФЭ указанного вида, лежащих на одной цепи Σ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
