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

Пусть 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 )(7.4)54Глава 3. Синтез и сложность управляющих системгде x — характеристическая ФАЛ δi , а в качестве ФАЛ fσ00 ,iiпри всех σ 00 ,σ 00 ∈ B n−q , и i, i ∈ [1, 2p ], берется ФАЛ ǧσ00 ,i вида7.2, совпадающая с ФАЛ fσ00 (x0 ) на компоненте δi = δ̌ ⊕ α.Пусть ΣG — (1, λ)-КС, которая реализует систему ФАЛ→−G по их совершенным ДНФ на основе контактного дерева(см. лемму 1.2 и оценку 1.2).

Для каждого i, i = 1, . . . , 2p , построим (1, 2n−q )-КС Σ0i (см. рис. 7.3a), которая содержит КСΣG в качестве подсхемы и реализует каждую ФАЛ ǧσ00 ,i вида7.2 с помощью корректной на множестве наборов δi суперпозиции, показанной на рисунке 7.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 .(7.5)Построим, наконец, разделительную по входам (2n−m , 1)КС Σ00 , которая реализует столбец из всех ФАЛ вида x (x0 )·σiq+1xq+1· · · xσnn , где i ∈ [1, 2p ] и σ 00 = (σq+1 , .

. . , σn ) ∈ B n−q .Эта КС получается в результате объединения 2p схем типа (2n−q , 1)-КД от БП x00 , к выходам которых присоединены входы (2p , 1)-КС, реализующей столбец из ФАЛ x ,ii ∈ [1, 2p ], и получающейся из (2q , 1)-КД от БП x0 в результате соответствующего отождествления входов (см.

рис. 7.3b).Легко видеть, что при этомL Σ00 6 2q+1 + 2n−m+1 .(7.6)Искомая КС Σf является результатом корректной стыковки вида Σf = Σ00 (Σ0 ), полученной в результате присоединения входов КС Σ00 к выходам КС Σ0 в соответствии с§7. Асимптотически наилучший метод синтеза КС~~OO~~ ZdZdZdOZdOo• ǧe~~ooo 0,i~~..~~~.~OOZOO~~ZZZ@~d1 • @@ ΣG dododoo• ǧσ00 ,i@@..@@.@@O@@ OO@@ dZdZdZodZoO• ǧe1,i@@oo|{zΣ0i.........}|a)55@@VVVVx@VVVV 1 ooo @@@@VVVOZdoZdododdd00hZКД(x ) hh • OOZZZ@@hOhhOh@@Ohhhh@@..@@. oVVVVx@@VVVVodoioodV@dVVZdoZdOdZZZZ КД(x0 )КД(x00 ) hhh•O~•OhOh~hOhO~~hhhh..~~~.VVVVx~VVVV 2p ooo~~VVVodZOdZododdd~00~КД(x ) hhh• OZOZOZOZ ~~hhhhO ~~hhhh~~{zΣ00}b)Рис.

7.3: к доказательству теоремы 7.1представлением 7.4, сложность которой, в силу 7.5–7.6, удовлетворяет неравенствуL (Σf ) 6 (p + 2)2n−m + (λ + 1)2q+1 .Из этого неравенства при q = m + p и√ 3m=log n ,s= n−2 n ,2при которых выполнены условия (4.3) и (6.1), в силу (4.2) и(4.4), вытекает неравенство 7.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√2n32√6 2n− n+3 log n = o.sn n56Глава 3. Синтез и сложность управляющих системТеорема доказана.Следствие. Из 7.3 с учетом нижней оценки (5.12) вытекает, что2nLK (n) ∼.nЗамечание.

Построенную КС Σf можно разбить на не более,чем n 2pn−m+1q+1√λp · 2 + 2+ (λ + 1)2=On n«звезд», каждая из которых состоит из контактов одногои того же типа. Для этого достаточно контакты всех звезд,показанных на рис. 7.2b, перераспределить в звезды из однотипных контактов, «центрами» которых являются выходыподсхем ΣG схем Σ0i , i = 1, .

. . , 2q−m , а любой из остальныхконтактов КС Σf считать отдельной звездой.Литература[1] Алексеев В. Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМиК МГУ, 2002.[2] Алексеев В. Б., Вороненко А. А., Ложкин С. А.,Романов Д. С., Сапоженко А. А., Селезнева С. Н.Задачи по курсу «Основы кибернетики». Издательский отдел ф-та ВМиК МГУ, 2002.[3] Алексеев В. Б., Ложкин С.

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

6. №3.С. 309–319.[8] Емеличев В. А., Мельников О. И., Сарванов В. И.,Тышкевич Р. И. Лекции по теории графов. М.: Наука,1977.5758Литература[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] Мурога С. Системы проектирования сверхбольшихинтегральных схем.

М.: Мир, 1985.Литература59[18] Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики. Вып. 21.М.: Наука, 1969. С. 5–102.[19] Нигматуллин Р. Г. Сложность булевых функций.М.: Наука, 1991.[20] Поваров Г. Н. Метод синтеза вычислительных и управляющих контактных схем // Автоматика и телемеханика. 1957. Т. 18.

№2. С. 145–162.[21] Сапоженко А. А. Дизъюнктивные нормальные формы. М.: Изд-во МГУ, 1975.[22] Сапоженко А. А. Некоторые вопросы сложности алгоритмов. Издательский отдел ф-та ВМиК МГУ, 2001.[23] Сапоженко А. А., Ложкин С. А. Методы логического проектирования и оценки сложности схем на дополняющих МОП-транзисторах // Микроэлектроника. 1983. Т.

12. №1. С. 42–47.[24] Фихтенгольц Г. М. Основы математического анализа,том 1. М.: Наука, 1968.[25] Фихтенгольц Г. М. Основы математического анализа,том 2. М.: Наука, 1964.[26] Чегис И. А., Яблонский С. В. Логические способыконтроля работы электрических схем // Труды МИАН СССР. Т. 51. М.: Изд-во АН СССР, 1958. С. 270–360.[27] Яблонский С.

В. Введение в дискретную математику.2-е изд., перераб. и доп. М.: Наука, 1986.[28] Яблонский С. В. Надежность управляющих систем.М.: Изд-во МГУ, 1991.60Литература[29] Яблонский С. В. Некоторые вопросы надежности иконтроля управляющих систем // Математические вопросы кибернетики.

Вып. 1. М.: Наука, 1988. С. 5–25.[30] Яблонский С. В. Эквивалентные преобразования управляющих систем. М.: Изд-во МГУ, 1986.[31] Cardot C. Quelques resultats sur l’application de l’algèbrede Boole à la synthèse des circuits a relais //Ann. Telecommunications. 1952. V.7. №2. P. 75–84.[32] Shannon C. E. The syntesis of two-terminal switchingcircuits // Bell Syst. Techn. J. 1949. V. 28.

№1.P. 59–98 (Русский перевод: Шеннон К. Работы потеории информации и кибернетике. М.: ИЛ, 1963.С. 59–101).[33] Wegener I. Branching programs and binary decisiondiagrams. SIAM Publishers, 2000..