3 (С.А. Ложкин - Лекции по основам кибернетики (2017)), страница 8

8.3b). Легко видеть, что приэтомL Σ00 6 2q+1 + 2n−m+1 .(8.6)Искомая КС Σf является результатом корректной стыковки вида Σf = Σ00 (Σ0 ), полученной в результате присоединения входов КС Σ00 к выходам КС Σ0 в соответствии спредставлением (8.4), сложность которой, в силу (8.5)–(8.6),удовлетворяет неравенствуL (Σf ) 6 (p + 2)2n−m + (λ + 1)2q+1 .62Введение• ǧe0,i...1•ΣG• ǧσ 00 ,i...• ǧe1,i|{zΣ0i.........xКД(x00 )1•...xКД(x00 )i•x00КД(x )КД(x0 )•...2p•}a)|{zΣ00b)Рис. 8.3: к доказательству теоремы 8.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+3(λ + 1)2q+1 6 p2s · 2m+p+2 66s√322n√6 2n− n+3 log n = o.sn nТеорема доказана.}Введение63Следствие. Из (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 считать отдельной звездой.Описанные в §§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).64ВведениеВозьмем в качестве примера введенный выше класс ФАЛ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 =_(σ1 ,σ2xσ1 1 xσ2 2 fσ1 ,σ2 x0 ,(8.8))∈B 2где 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)) ∼§93 2n.4 nСинтез схем для некоторых дешифраторови мультиплексоровПрименим технику моделирования ФАЛ переменными длясинтеза некоторых дешифраторов и мультиплексоров.Введение65Лемма 9.1 (ср. [14]). Для n = 1, 2, 3, . . . выполняются неравенства n− 2К →n,(9.1)LQn 6 2 + On n− 2n+1К →Jn 62+OL.(9.2)nДоказательство. Выберем параметры m, q и λ так, чтоλ = 2m ,q = m + λ и q 6 n,а затем рассмотрим m-регулярное множество наборов δ1 куба B q от БП x0 = (x1 , . .

. , xq ), связанное с системой ФАЛ→−Q m (x1 , . . . , xm ), которая состоит из всех ЭК вида xσ1 1 · · · xσmm ,где ν(σ1 , . . . , σm ) = j − 1, j ∈ [1, λ].Построим для этой системы по лемме 7.1 разбиение ∆ =(δ1 , . . . , δ2q−m ) куба B q и заметим, что любая ЭК K(x0 ) =σxσ1 1 · · · xq q , где σ 0 = (σ1 , . . . , σq ) ∈ δi , совпадает на множестве→−δi с одной из ЭК системы Q m , то есть совпадет на нем сα 0буквой xj σ0 , где m + 1 6 jσ0 6 q, ασ0 ∈ B.

Заметим, что вσсилу указанных выше свойств разбиения ∆ любая ЭК K =xσ1 1 · · · xσnn , где σ 0 = (σ1 , . . . , σq ) ∈ δi , 1 6 i 6 2λ , может бытьпредставлена в видеαK = χi (x0 ) · xj σ0 · Kσ00 (x00 ),σ0(9.3)где x00 = (xq + 1, . . . , xn ), σ 00 = (σq+1 , . . . , σn ).Пусть, далее, (1, 2λ )-КС Σ0 = Σ0 (a; b1 , . .

. , b2λ ) реализует−0строку из ФАЛ →χ = (χ1 , . . . , χ2λ ), где χλi(x ) — характеристическая ФАЛ множества δi , i ∈ 1, 2 , и получается врезультате отождествления входов у схем Σ01 , . . . , Σ02λ , гдеπ-схема Σ0i , i ∈ [1, 2λ ], построена по лемме 1.2 для ФАЛ χi ,и является ККС сложности не больше, чем q · 2m , с входом ai = a и выходом bi — корнем соответствующего КД(см.

рис. 9.1).66Введение→−(&)Искомая (1, 2n )-КС Σn реализует каждую ЭК из Q n всоответствии с (9.3), имеет вид, показанный на рис. 9.1, иявляется ККС.Полагаяm = dlog ne − 2,получим, чтоλ = 2m 6n,2q = m + λ 6 n.(&)При этом сложность построенной (1, 2n )-КС Σn , являющейся контактным дешифратором порядка n, удовлетворяет неравенствам: n2(&)n−mn−m+1qnL Σn6 λ2+2+ q2 6 2 + O,nиз которых вытекает неравенство (9.1).(∨)Искомая (1, 2n )-КС Σn , являющаяся дизъюнктивнымконтактным дешифратором порядка n, сложность которогоудовлетворяет оценке (9.2), получается в результате перехо(&)да от ККС Σn к инверсной ККС.Лемма доказана.Следствие. Оценки леммы 9.1, следствия из леммы 2.2 иследствия из леммы 2.4 дают асимптотические равенства→− →−LК Q n ∼ 2n ,LK ( J n ) ∼ 2n+1 .Лемма 9.2.

Для n = 1, 2, . . . выполняются неравенства n n22πnCnL (µn ) 6 2 · 2 + O, L (µn ) 6 2 · 2 + O,nnD(µn ) 6 n + 6,Введение67sРис. 9.1: к доказательству леммы 9.1причем существует такая реализующая ФАЛ µn и бесповторная по информационным БП формула Mn с поднятыми отрицаниями, глубина которой удовлетворяет последнему из них, альтернирование не больше 3, а сложностьне превосходит 7 · 2n .Доказательство. Искомая π-схема Σn получается в резуль(&)тате присоединения к каждому из выходов (1, 2n )-КС Σn ,построенной при доказательстве леммы 9.1, контакта соответствующей ему информационной БП и отождествленияконцевых вершин всех таких контактов в выходную вершину Σn . Искомая СФЭ Sn получается из формулы с поднятыми отрицаниями Fn , которая моделирует π-схему Σn68Введение(см. §4 гл.

2), в результате применения операций приведения (см. §1) для вершин, соответствующих ФЭ ¬.Для завершения доказательства леммы на основе разбиения ∆, введенного в лемме 9.1, и представления (9.3) построим для ФАЛ µn формулу F̃n следующим образомF̃n (x1 , . . . , xn , y0 , . . . , y2n −1 ) =2λ_ α 0_(9.4)xj σ0 yν(σ0 ,σ00 ) =Ai x0 & & Jσ00 (x00 ) ∨σi=1σ 00 ∈B n−qσ 0 ∈δiгде Ai — совершенная ДНФ ФАЛ χi , i = 1, .

. . , λ, и Jσ00 (x00 ) =K σ00 (x00 ). Легко видеть, что F̃n реализует мультиплексорнуюФАЛ µn , бесповторна по БП y0 , . . . , y2n −1 и что Alt (F̃n ) 6 3.Пусть, далее, формула Mn получается в результате оптимизации формулы F̃n по глубине. Тогда приl n mn > 3 и m = log3сложность и глубина Mn будут удовлетворять условиям леммы. Действительно, если1 n > 6, то q 6 n − m и, следовательно, e n = 2q−m q · 2m + 2n−q (n − q) + 2m+1 6R F6 2n+1 + n · 2n−m 6 2n+1 + 3 · 2n = 5 · 2n .При этом, очевидно,L¬ (F̃n ) 61R(F̃n ) − 2n 6 2n+12и, таким образом,L(F̃n ) 6 R(F̃n ) + L¬ (Fn ) − 1 6 7 · 2n − 1,1Случай n 6 5 рассматриваются отдельно.Введение69откуда в силу теоремы 2.1 главы 2 следует, что D(Mn ) 6n + 6.Лемма доказана.Следствие.

Из полученных оценок в силу следствий излеммы 2.5 вытекает, чтоLС (µn ) ∼ 2n+1 ,D(µn ) = n + O(1).Литература[1] Алексеев В. Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМиК МГУ, 2002.[2] Алексеев В. Б., Вороненко А. А., Ложкин С. А.,Романов Д. С., Сапоженко А. А., Селезнева С. Н.Задачи по курсу «Основы кибернетики». Издательский отдел ф-та ВМиК МГУ, 2002.[3] Алексеев В.

Б., Ложкин С. А. Элементы теории графов, схем и автоматов. М.: Издательский отдел ф-таВМиК МГУ, 2000.[4] Боровков А. А. Курс теории вероятностей. М.: Наука,1976.[5] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. 3-е изд., перераб.М.: ФИЗМАТЛИТ, 2004.[6] Дискретная математика и математические вопросы кибернетики, под редакцией С.

В. Яблонского иО. Б. Лупанова. Т. 1. М.: Наука, 1974.[7] Евдокимов А. А. О максимальной длине цепи в единичном n-мерном кубе // Матем. заметки. 1969. 6. №3.С. 309–319.[8] Емеличев В. А., Мельников О. И., Сарванов В. И.,Тышкевич Р. И. Лекции по теории графов. М.: Наука,1977.70Введение71[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] Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования.72Введение// Проблемы кибернетики. Вып. 14. М.: Наука, 1965.С. 31–110.[18] Мурога С. Системы проектирования сверхбольшихинтегральных схем.