OK_metodichka_part_3 (1132798), страница 5
Текст из файла (страница 5)
Синтез и сложность управляющих системи поэтому неравенство (4.8) получается из неравенства y > y 0в результате замены y на ay и log q на a log q, если выполненоусловие a log q > 1.Неравенство (4.9) в случае a > 1 получается в результате логарифмирования неравенства ay > q и деления обеихчастей полученного неравенства на log a.Лемма доказана.Теорема 4.1.
Для некоторой последовательности ε=ε(n),n = 1, 2, . . ., такой, что ε (n) > 0 при n > n0 и ε (n) стремится к 0 при n стремящемся к бесконечности, выполняются неравенства2n,nn2LΦ (n) > (1 − ε (n)),log n2nLK (n) > (1 − ε (n)) ,n2nLπ (n) > (1 − ε (n)).log nLC (n) > (1 + ε (n))(4.10)(4.11)(4.12)(4.13)Доказательство. Неравенства (4.10)–(4.13) выводятся из соответствующего рассматриваемому классу схем U с функционалом сложности L неравенства (4.3)–(4.6) на основе мощностного равенства (4.1) с использованием леммы 4.1, гдеnq = 22 , и1)2)3)4)a = 8,a = 8n,a = 8n,a = 16n,yyyy= LC (n) + n,= LΦ (n) + 1,= LK (n),= Lπ (n),еслиеслиеслиеслиU = UC ;U = UΦ ;U = UK ;U = Uπ .Действительно, подставляя указанные значения в (4.8) по-§4.
Нижние мощностные оценки функций Шеннона35лучимC1) L (n) >>2) LΦ (n) >3) LK (n) >>log(n + 3)2n1+−n>n+3n+5(4.14)log n − 3 − o(1)2n1+nnn23 + o(1)2n1−(4.15)−1>log n + 3log nlog n2nlog(n + 3 + log n)1+>n + 3 + log nn + 5 + log n(4.16)2n3 + o(1)1−nnСледовательно, неравенство (4.10) ((4.11), (4.12)) будетсправедливо для достаточно больших n при ε (n) = log nn−4(соответственно ε (n) = log4 n , ε (n) = n4 ).Аналогичным образом устанавливается справедливость(4.13) при ε (n) = log5 n .Теорема доказана.Следствие 1.LC (n) &2n,n2n2n, LK (n) &,log nn2n.Lπ (n) &log nLΦ (n) &Следствие 2. Нижние оценки (4.10)–(4.13) при указанныхв доказательстве значениях ε(n) справедливы для сложности почти всех ФАЛ f, f ∈ P2 (n), при их реализации всоответствующих классах схем.nДействительно, замена величины q = 22 величиной q =1 2nпри получении оценок (4.14)–(4.16) с помощью лемn2мы 4.1 повлияет только на участвующие в их последних36Глава 3.
Синтез и сложность управляющих системнеравенствах функции вида o(1). При этом, в силу (4.2),b — правая часть соответствующего неравенгде δ = n1 , а Ψства (4.10)–(4.12), вновь полученная оценка будет справедлива для почти всех ФАЛ f, f ∈ P2 (n). Справедливостьнижней оценки (4.13) для почти всех ФАЛ устанавливаетсяаналогично.Аналогичным образом на основе (4.9) и леммы 2.3 главы2 доказывается следующее утверждение.Теорема 4.2. Для n = 1, 2, .
. . справедливо неравенствоD(n) > n − log log n + o(1).(4.17)Замечание. Оценка (4.17) справедлива для глубины D(f )почти всех ФАЛ f , f ∈ P2 (n).§5Дизъюнктивно-универсальные множествафункций. Асимптотически наилучшийметод О. Б. Лупанова для синтезасхем из функциональных элементовв базисе {&, ∨, ¬}Рассмотрим метод синтеза схем из класса UC , который былпредложен О.Б. Лупановым [14] и позволил впервые установить асимптотику функции Шеннона LC (n).
Этот метод,как и метод Шеннона (см. §2), основан на представленииреализуемой ФАЛ f, f ∈ P2 (n), в виде (2.4) и построенииискомой СФЭ Σf , реализующей ФАЛ f , как суперпозициисхем вида Σf = Σ00 (Σ0 ). При этом схема Σ00 по-прежнему является мультиплексором порядка (n − q) от адресных БПx00 = (xq+1 , . . . , xn ), а схема Σ0 реализует все ФАЛ видаfσ00 (x0 ), где x0 = (x1 , .
. . , xq ) , σ 00 ∈ B n−q , и fσ00 (x0 ) = f (x0 , σ 00 ).Однако, в отличие от метода Шеннона, каждая ФАЛ fσ00 (x0 )берется не с выхода универсального многополюсника от БПx0 , а реализуется на выходе Σ0 как дизъюнкция некоторых§5. Метод Лупанова синтеза СФЭ37ФАЛ, выбранных из специального множества G, G ⊆ P2 (q),реализованного на выходах соответствующей подсхемы схемыΣ0 .Множество ФАЛ G, G ⊆ P2 (m), называется дизъюнктивно-универсальным множеством (ДУМ) порядка m и ранга p, если любая ФАЛ g, g ∈ P2 (m), может быть представлена в видеg = g1 ∨ .
. . ∨ gp ,где gi ∈ G при всех i, i = 1, . . . , p. Стандартный способ построения таких множеств связан с разбиениями единичногокуба.Пусть Π = (π1 , . . . , πp ) — разбиение куба B m , и пусть длявсех i, i = 1, . . . , p, ФАЛ ψi (x1 , . . . , xm ) — характеристическая ФАЛ множества πi , а G(i) — множество всех тех ФАЛg, g ∈ P2 (m), которые обращаются в 0 вне πi . Заметим, чтомножество ФАЛ G видаG = G(1) ∪ . . .
∪ G(p)является ДУМ порядка m и ранга p. Действительно, любаяФАЛ g, g ∈ P2 (m), может быть представлена в видеg = g1 ∨ . . . ∨ gp ,(5.1)где gi = ψi g и, следовательно, gi ∈ G(i) для всех i, i = 1, . . . , p.Заметим также, что мощность множества G(i) , i = 1, . . . , p,равна 2si , где si = |πi |, и что множество G(i) ∩ G(j) состоит из ФАЛ, тождественно равной 0, если 1 6 i < j 6 p.Следовательно,p pXX (i) λ = |G| =2si 6 p2s ,G − (p − 1) 6i=1i=1гдеs = max si .16i6p38Глава 3. Синтез и сложность управляющих системg1 g2 . . .g2s g2s +1. . .g2s+1 −1 .
. . g(p−1)(2s −1)+2. . . gλx1 x2 . . . xm−1 xm... 00 0 01 0 0 ... 0...π1 ............π2 ...πp−1 πp 0...0...0...00 0 .... . .. . .. . .0 0 ...1...0...0.........0...00...0.........0...1.........0 0 ... 01...1...0...00 0 ....
. .. . .. . .0 0 ...0...0...1.........0...01...0.........0...0...............0 1 ... 1......0...0...0...0...0.........0...00...0.........0...0.........0......0 0 .... . .. . .. . .0 0 ......0 0 ... 00...0...1...1...0 0 .... . .. . .. . .0 0 ...0...0...0.........0...00...0.........1...0.........o2s/o/O...2s −1s=s2...0...O00 0 ...
0...s=s10......Oos2 p −1s=sp−10Osp 6s0/Рис. 5.1: к определению дизъюнктивно-универсальногомножестваУказанное ДУМ G будем называть стандартным ДУМпорядка m и высоты s, гдеs 62m ,если выполнены соотношения(5.2)§5. Метод Лупанова синтеза СФЭ391.p=2m,ss1 = s2 = · · · = sp−1 = s,(5.3)sp = 2m − (p − 1) s 6 s.2. Π = (π1 , . . . , πp ) — разбиение куба B m на последовательные отрезки, то есть такое разбиение, что номерлюбого набора из множества πi меньше номера любого набора из множества πj , если i < j.Компоненты разбиения Π будем при этом называть полосами ДУМ G, а ФАЛ ψ1 , .
. . , ψp — его характеристическими ФАЛ. Заметим, что характеристические ФАЛ попарноортогональны, то есть одновременно в 1 не обращаются, ипринадлежат G. Заметим также, что представление (5.1) вслучае стандартного ДУМ G равносильно представлению:g = ψ1 g1 ∨ ψ2 g2 ∨ · · · ∨ ψp gp(5.4)Таблица значений ФАЛ стандартного ДУМ G приведена нарис. 5.1.Из построения и отмеченных выше свойств стандартногоДУМ вытекает справедливость следующего утверждения.5.1. Для любых натуральных p, m и s, где p =Лемма2m,существуетДУМ G порядка m и ранга p такое, что:s1. λ = |G| 6 p2s ;2. в G имеется система из p ортогональных ФАЛ ψ1 , .
. . , ψp ,обладающих тем свойством, что для любой ФАЛ g,g ∈ P2 (m), и некоторых ФАЛ g1 , . . . , gp из G справедливо не только представление (5.1), но и представление (5.4).40Глава 3. Синтез и сложность управляющих системТеорема 5.1. Для любой ФАЛ f, f ∈ P2 (n), существуетреализующая ее СФЭ Σf , Σf ∈ UC , такая, что2nL (Σf ) 6n5 log n + O (1)1+n.(5.5)Доказательство. Пусть x0 = (x1 , . .
. , xq ), x00 = (xq+1 , . . . , xn )и fσ00 (x0 ) = f (x0 , σ 00 ) для всех σ 00 из B n−q . Пусть, далее,Σ00 — мультиплексор порядка (n − q) от адресных БП x00 иинформационных БП y = (y0 , . . . , y2n−q −1 ), который построен в соответствии с леммой 1.6, представляет собой формулуFn−q и реализует мультиплексорную ФАЛ µn−q (x00 , y).Пусть s — некоторый параметр, удовлетворяющий (5.2),а G — стандартное ДУМ порядка m = q и высоты s, удовлетворяющее требованиям леммы 5.1. Обозначим через ΣG→−СФЭ, которая реализует систему ФАЛ G и представляетсобой объединение схем, построенных для каждой из них всоответствии с леммой 1.2.
Заметим, что, в силу леммы 1.3,(1.3) и леммы 5.1, выполнены неравенстваL Σ00 6 4 · 2n−q ,L (ΣG ) 6 3p2s+q .(5.6)Схема Σ0 содержит СФЭ ΣG в качестве подсхемы и реализует каждую ФАЛ fσ00 (x0 ), где σ 00 ∈ B n−q , на одном из своих выходов как ФАЛ g (x0 ) вида (5.1) с помощью СФЭ из(p − 1) ФЭ ∨, входы которой присоединены к соответствующим выходам ΣG . Искомая СФЭ Σf имеет вид Σf = Σ00 (Σ0 )и реализует ФАЛ f в соответствии с разложением (2.4).
Длянее, в силу (5.6), будут выполняться неравенстваL (Σf ) 6 2n−q (p − 1) + L Σ00 + L (ΣG ) 66 2n−q (p − 1) + 4 · 2n−q + 3p2s+q ,§6. Асимптотически наилучший метод синтеза КС41из которых, выбрав значения параметровs = dn − 5 log ne ,m = q = d2 log ne ,удовлетворяющие (5.2), в соответствии с леммой 5.1 получим n2n2L (Σf ) 6+O=n − 5 log nn25 log n + O (1)2n1+.=nnТеорема доказана.Следствие. Из (5.5) и (4.10) (см. также следствие 1 изтеоремы ??) вытекает, чтоLC (n) ∼2n.nОтметим, в заключение, что в соответствии с (5.5) иследствиями из теорем ??, 5.1 сложность LC (f ) для почтивсех ФАЛ f, f ∈ P2 (n), асимптотически равна функцииШеннона LC (n), то есть сложности самой сложной ФАЛ изP2 (n). Тем самым, в отличие от класса ДНФ (см. §7 главы 1), в классе схем UC имеет место т. н. эффект Шеннона — асимптотическое равенство сложности почти всех ФАЛи сложности самой сложной ФАЛ от заданного числа БП,стремящегося к бесконечности.§6Асимптотически наилучший метод синтезаконтактных схемЗаметим сначала, что асимптотически наилучший метод синтеза СФЭ из §5 без существенных изменений переносится на42Глава 3.
Синтез и сложность управляющих системкласс контактно-вентильных схем (КВС), в которых нарядус контактами можно использовать «вентили», то есть ориентированные ребра, проводящие только в направлении своейориентации. Действительно, для любой ФАЛ f , f ∈ P2 (n),e f может быть получена на осреализующая ее (1, 1)-КВС Σнове разложения 2.4 так же, как и СФЭ Σf из теоремы 5.1.Она является результатом корректной суперпозиции (см. §9e f = Σ00 (Σ0 ), где Σ00 — (2n−q , 1)-КД от БПглавы 2) вида Σ00n−qx , а (1, 2 )-КВС Σ0 реализует систему всех ФАЛ видаfσ00 (x0 ) , σ 00 ∈ B n−q .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
