ОК_Часть_3_2015_(320-328) (1132807), страница 8
Текст из файла (страница 8)
, ψp ) (см. рис. 8.2a),а ∆ = (δ1 , . . . , δ2p ) — построенное для нее по лемме 7.1 разбиение куба B m+p . Заметим, что любая ФАЛ g, g ∈ P2 (m + p),58Глава 3. Синтез и сложность управляющих системg1•...ΣG1••&9 g...•gpa)g1•...ΣG1•ψ1...•gψp•gpb)Рис. 8.1: Корректная реализация дизъюнкции ФАЛg1 , . . . , gp в классах КВС и ИКСна любой компоненте этого разбиения вида δ̌ ⊕ α, гдеα = (0, . . . , 0, αm+1 , . . . , αm+p ),| {z }mсовпадает с ФАЛααm+pm+1ǧ = xm+1· g1 ∨ . .
. ∨ xm+p· gp ,(8.2)где gi = gψi ∈ G(i) , i = 1, . . . , p. При этом ФАЛ ǧ может быть реализована в результате операции присоединенияαm+pαm+1звезды из контактов вида xm+1, . . . , xm+pк выходам (1, λ)→−КС ΣG , реализующей систему ФАЛ G , так, как это показанона рис. 8.2b. Заметим также, что указанная операция суперпозиции является корректной на множестве наборов δ̌ ⊕ α§8. Асимптотически наилучший метод синтеза КС.
. . xm−1 xm ψ1 x1 0 ... 010... 0101.....π1....1...0...0.....π2....0.........0...0.....πp....1110ψ200...011...1.... . . ψp00... ...000... ...0... ...00.. . . ..011...1δ̌a)g1•1αm+1xm+1...ΣG•gpǧαm+pxm+pb)Рис. 8.2: m-регулярное множество δ̌ и связанная с нимсуперпозиция КС5960Глава 3. Синтез и сложность управляющих системв силу того, что из контактов присоединяемой (p, 1)-КС налюбом наборе этого множества проводит только один.Теорема 8.1 (ср.
[14]). Для любой ФАЛ f , f ∈ P2 (n), существует реализующая ее КС Σf такая, что12n√1+O(8.3)L (Σf ) 6nnДоказательство. Пусть q = m + p, а ∆ = (δ1 , . . . , δ2p ) —описанное выше разбиение куба B q , с помощью которогоФАЛ f можно представить в видеp000f x ,x=2_i=1xx0i_σq+1xq+1· · · xσnn ǧσ00 ,i x0 ,σ 00 =(σq+1 ,...,σn )(8.4)где x — характеристическая ФАЛ δi , а в качестве ФАЛ fσ00 ,iiпри всех σ 00 ,σ 00 ∈ B n−q , и i, i ∈ [1, 2p ], берется ФАЛ ǧσ00 ,i вида(8.2), совпадающая с ФАЛ fσ00 (x0 ) на компоненте δi = δ̌ ⊕ α.Пусть ΣG — (1, λ)-КС, которая реализует систему ФАЛ→−G по их совершенным ДНФ на основе контактного дерева(см.
лемму 1.2 и оценку (1.2)). Для каждого i, i = 1, . . . , 2p ,построим (1, 2n−q )-КС Σ0i (см. рис. 8.3a), которая содержитКС ΣG в качестве подсхемы и реализует каждую ФАЛ ǧσ00 ,iвида (8.2) с помощью корректной на множестве наборовδi суперпозиции, показанной на рисунке 8.2b. Пусть, далее, (1, 2n−m )-КС Σ0 получается в результате отождествления входов у построенных выше КС Σ0i , i ∈ [1, 2p ], и реализует систему из всех ФАЛ вида ǧσ00 ,i , где σ 00 ∈ B n−q , i ∈ [1, 2p ].Заметим, что при этом выполняются неравенстваL (ΣG ) 6 λ2m+1 ,L Σ0i 6 L (ΣG ) + p2n−q ,L Σ0 6 p2n−m + λ2q+1 .(8.5)§8. Асимптотически наилучший метод синтеза КС• ǧe0,i...1•ΣG• ǧσ 00 ,i...• ǧe1,i|{zΣ0i61x...1•КД(x00 )...x...i•КД(x00 )x...КД(x0 )•...2p•00КД(x )}|{zΣ00a)}b)Рис.
8.3: к доказательству теоремы 8.1Построим, наконец, каскадную (2n−m , 1)-КС Σ00 , котораяσq+1реализует столбец из всех ФАЛ вида x (x0 )·xq+1· · · xσnn , гдеii ∈ [1, 2p ] и σ 00 = (σq+1 , . . . , σn ) ∈ B n−q . Эта КС получаетсяв результате объединения 2p схем типа (2n−q , 1)-КД от БПx00 , к выходам которых присоединены входы (2p , 1)-КС, реализующей столбец из ФАЛ x , i ∈ [1, 2p ], и получающейсяiиз (2q , 1)-КД от БП x0 в результате соответствующего отождествления входов (см. рис. 8.3b). Легко видеть, что приэтомL Σ00 6 2q+1 + 2n−m+1 .(8.6)Искомая КС Σf является результатом корректной стыковки вида Σf = Σ00 (Σ0 ), полученной в результате присоединения входов КС Σ00 к выходам КС Σ0 в соответствии спредставлением (8.4), сложность которой, в силу (8.5)–(8.6),62Глава 3.
Синтез и сложность управляющих системудовлетворяет неравенствуL (Σf ) 6 (p + 2)2n−m + (λ + 1)2q+1 .Из этого неравенства при√ 3m=log n и s = n − 2 n ,2при которых выполнены условия m2ms62 , p=и q = m + p 6 n,sвытекает неравенство (8.3) для сложности Σf , так как2n2n1n−mn−m(p + 2)26+3·2=1+O √,snn22m+s+p+36(λ + 1)2q+1 6 p2s · 2m+p+2 6s√322n√6 2n− n+3 log n = o.sn nТеорема доказана.Следствие. Из (8.3) с учетом нижней оценки (5.13) вытекает, что2nLK (n) ∼.nЗамечание. Построенную КС Σf можно разбить на не более,чем n 2pn−m+1q+1√λp · 2 + 2+ (λ + 1)2=On n«звезд», каждая из которых состоит из контактов одногои того же типа.
Для этого достаточно контакты всех звезд,показанных на рис. 8.2b, перераспределить в звезды из однотипных контактов, «центрами» которых являются выходыподсхем ΣG схем Σ0i , i = 1, . . . , 2q−m , а любой из остальныхконтактов КС Σf считать отдельной звездой.§8. Асимптотически наилучший метод синтеза КС63Описанные в §§6, 7, 8 асимптотически наилучшие методысинтеза схем ориентированы, вообще говоря, на произвольную или самую «сложную» ФАЛ.
Тем не менее, во многихслучаях они служат основой асимптотически наилучших методов синтеза СФЭ и КС для ФАЛ из заданного специального класса Q и позволяют установить для этого класса «стандартные» (см. (5.20) и (5.21)) асимптотики видаLK (Q(n)) ∼ LC (Q(n)) ∼log log |Q(n)|.log |Q(n)|(8.7)Заметим, что асимптотики (8.7) устанавливаются, как правило, путем сведения задачи синтеза СФЭ или КС для любой ФАЛ из Q(n) к задаче синтеза соответствующей схемыдля системы из одной или нескольких произвольных ФАЛот меньшего числа БП. При этом требуется, чтобы двоичный логарифм числа тех систем ФАЛ, к реализации которых сводится реализация ФАЛ из Q(n), был асимптотическиравен log |Q(n)|, а сложность вспомогательных ФАЛ, обеспечивающих данное сведение, была бы существенно меньшеправой части (5.20) или (5.21).Возьмем в качестве примера введенный выше класс ФАЛQ, состоящий из всех ФАЛ, симметричных по первым двумБП, и докажем, чтоLC (Q (n)) .3 2n· ,4 nто есть, с учетом (5.22), установим для него асимптотику (8.7)вида3 2nLC (Q (n)) ∼ · .4 nДействительно, разлагая ФАЛ f (x1 , .
. . , xn ) из Q (n) по БПx1 , x2 , получим_f x1 , x2 , x0 =xσ1 1 xσ2 2 fσ1 ,σ2 x0 ,(8.8)(σ1 ,σ2 )∈B 264Глава 3. Синтез и сложность управляющих системгде x0 = (x3 , . . . , xn ) и fσ1 ,σ2 (x0 ) = fσ1 ,σ2 (σ1 , σ2 , x0 ), причемf01 = f10 в силу симметричности ФАЛ f по БП x1 , x2 . Искомая СФЭ Σf реализует ФАЛ f в соответствии с (8.8) и имеетвид Σf = Σ00 (Σ0 ), где Σ00 — мультиплексорная СФЭ порядка2 от адресных БП x1 , x2 , а СФЭ Σ0 от БП x0 реализует асимптотически наилучшим способом ФАЛ f00 , f01 = f10 и f11 отБП x0 . Легко видеть, что сложность построенной схемы Σfnасимптотически не больше, чем 43 2n . Аналогичным образомдоказывается, чтоLK (Q(n)) ∼3 2n.4 nЛитература[1] Алексеев В.
Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМиК МГУ, 2002.[2] Алексеев В. Б., Вороненко А. А., Ложкин С. А.,Романов Д. С., Сапоженко А. А., Селезнева С. Н.Задачи по курсу «Основы кибернетики». Издательский отдел ф-та ВМиК МГУ, 2002.[3] Алексеев В. Б., Ложкин С. А. Элементы теории графов, схем и автоматов.
М.: Издательский отдел ф-таВМиК МГУ, 2000.[4] Боровков А. А. Курс теории вероятностей. М.: Наука,1976.[5] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. 3-е изд., перераб.М.: ФИЗМАТЛИТ, 2004.[6] Дискретная математика и математические вопросы кибернетики, под редакцией С. В. Яблонского иО. Б. Лупанова.
Т. 1. М.: Наука, 1974.[7] Евдокимов А. А. О максимальной длине цепи в единичном n-мерном кубе // Матем. заметки. 1969. 6. №3.С. 309–319.[8] Емеличев В. А., Мельников О. И., Сарванов В. И.,Тышкевич Р. И. Лекции по теории графов. М.: Наука,1977.6566Литература[9] Журавлев Ю. И. Локальные алгоритмы вычисленияинформации // Кибернетика.
№1. 1965. С. 12–19.[10] Журавлев Ю. И. Теоретико-множественные методы валгебре логики // Проблемы кибернетики. Вып. 8.М.: Физматгиз, 1962. С. 5-44.[11] Кузьмин В. А. Оценки сложности реализации функций алгебры логики простейшими видами бинарныхпрограмм // Сб. «Методы дискретного анализа втеории кодов и схем». Новосибирск, 1976. Вып. 29.С. 11–39[12] Ложкин С. А. Оценки высокой степени точности длясложности управляющих систем из некоторых классов // Математические вопросы кибернетики.
Вып. 6.М.: Наука, 1996. С. 189–214.[13] Ложкин С. А. Структурное моделирование и декомпозиция для некоторых классов схем. М.: Издательский отдел ф-та ВМиК МГУ, 2001.[14] Лупанов О. Б. Асимптотические оценки сложностиуправляющих систем. М.: Изд-во МГУ, 1984.[15] Лупанов О. Б. О сложности реализации функцийалгебры логики релейно-контактными схемами //Проблемы кибернетики. Вып. 11. М.: Наука, 1964.С. 25–48.[16] Лупанов О.
Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики.Вып. 3. М.: Физматгиз, 1960. С. 61–80.[17] Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования.Литература67// Проблемы кибернетики. Вып. 14. М.: Наука, 1965.С. 31–110.[18] Мурога С. Системы проектирования сверхбольшихинтегральных схем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
