OK_metodichka_part_3 (1132798), страница 6
Текст из файла (страница 6)
При этом схема Σ0 по-прежнему содержит в качестве подсхемы (1, λ)-КС ΣG , реализующую систе→−му ФАЛ G на основе леммы 1.2, и реализует каждую ФАЛg (x0 ) типа fσ00 (x0 ) на основе ее представления 5.1 в видедизъюнкции g = g1 ∨ · · · ∨ gp с помощью присоединения входов вентильной звезды порядка p к соответствующим выходам КС ΣG (см. рис. 6.1a, а также рис. 9.2c из главы 2),которое является корректной суперпозицией.
Сложность поe f при тех же значениях параметров, что истроенной КВС Σв теореме 5.1, будет удовлетворять неравенству 5.5.Напомним (см. §5), что в силу специфики стандартногоДУМ G вместо представления 5.1 для ФАЛ g можно использовать эквивалентное 5.1 представлениеg = ψ1 · g1 ∨ · · · ∨ ψp · gp(6.1)и на его основе реализовать ФАЛ g с помощью корректной суперпозиции т.н. итеративно-контактных схем, показанной на рис.
6.1b, где ФАЛ ψ1 , . . . , ψp управляют проводимостью соответствующих контактов. Асимптотически наилучший метод синтеза КС связан с «моделированием» этойсуперпозиции и представления 6.1 на компонентах подходящего m-регулярного разбиения куба B m+p .Пусть δ̌ — m-регулярное множество наборов куба B m+p ,→−соответствующее системе ФАЛ ψ = (ψ1 , . .
. , ψp ) (см. рис. 6.2a),§6. Асимптотически наилучший метод синтеза КСqqqqqqqqqqqqqqΣG1 •qMMMMMMMMMMMMMMM43gN1• NNNNNN.. NNNr•9& g. rrrrrrrrr•...gpa)qqqqqqqqqqqqqqΣG1 •MqMMMMMMMMMMMMMMgN1• NNNNψNN1.. NNNr• g. rrrrrrrψprr•...gpb)Рис. 6.1: Корректная реализация дизъюнкции ФАЛg1 , . . . , gp в классах КВС и ИКСа ∆ = (δ1 , . . . , δ2p ) — построенное для нее по лемме 5.1 разбиение куба B m+p . Заметим, что любая ФАЛ g, g ∈ P2 (m + p),на любой компоненте этого разбиения вида δ̌ ⊕ α, гдеα = (0, .
. . , 0, αm+1 , . . . , αm+p ),| {z }mсовпадает с ФАЛααm+pm+1ǧ = xm+1· g1 ∨ . . . ∨ xm+p· gp ,(6.2)где gi = gψi ∈ G(i) , i = 1, . . . , p. При этом ФАЛ ǧ может быть реализована в результате операции присоединеαm+pαm+1ния звезды из контактов вида xm+1, . . . , xm+pк выходам44Глава 3.
Синтез и сложность управляющих систем. . . 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)qq g1qqqq•MMM xαm+1qMMm+1qqqMMMqqqM..qΣG1 qMMMMq.qqMMMǧqqMMMqqq αm+p•q xm+pMMMMM gpb)Рис. 6.2: m-регулярное множество δ̌ и связанная с нимсуперпозиция КС§6.
Асимптотически наилучший метод синтеза КС45→−(1, λ)-КС ΣG , реализующей систему ФАЛ G , так, как этопоказано на рис. 6.2b. Заметим также, что указанная операция суперпозиции является корректной на множестве наборов δ̌ ⊕α в силу разделительности присоединяемой (p, 1)-КСна этом множестве.Теорема 6.1 (ср. [14]). Для любой ФАЛ f , f ∈ P2 (n), существует реализующая ее КС Σf такая, что2nL (Σf ) 6n1+O1√n(6.3)Доказательство.
Пусть q = m + p, а ∆ = (δ1 , . . . , δ2p ) —описанное выше разбиение куба B q , с помощью которогоФАЛ f можно представить в видеp000f x ,x=2_i=1где xixx0i_σq+1xq+1· · · xσnn ǧσ00 ,i x0 ,σ 00 =(σq+1 ,...,σn )(6.4)— характеристическая ФАЛ δi , а в качестве ФАЛ fσ00 ,iпри всех σ 00 ,σ 00 ∈ B n−q , и i, i ∈ [1, 2p ], берется ФАЛ ǧσ00 ,i вида6.2, совпадающая с ФАЛ fσ00 (x0 ) на компоненте δi = δ̌ ⊕ α.Пусть ΣG — (1, λ)-КС, которая реализует систему ФАЛ→−G по их совершенным ДНФ на основе контактного дерева(см. лемму 1.2 и оценку 1.2). Для каждого i, i = 1, .
. . , 2p , построим (1, 2n−q )-КС Σ0i (см. рис. 6.3a), которая содержит КСΣG в качестве подсхемы и реализует каждую ФАЛ ǧσ00 ,i вида6.2 с помощью корректной на множестве наборов δi суперпозиции, показанной на рисунке 6.2b. Пусть, далее (1, 2n−m )КС Σ0 получается в результате отождествления входов у построенных выше КС Σ0i , i ∈ [1, 2p ], и реализует систему извсех ФАЛ вида ǧσ00 ,i , где σ 00 ∈ B n−q , i ∈ [1, 2p ]. Заметим, что46Глава 3. Синтез и сложность управляющих системпри этом выполняются неравенстваL (ΣG ) 6 λ2m+1 ,L Σ0i 6 L (ΣG ) + p2n−q ,L Σ0 6 p2n−m + λ2q+1 .(6.5)Построим, наконец, разделительную по входам (2n−m , 1)КС Σ00 , которая реализует столбец из всех ФАЛ вида x (x0 )·iσq+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 в результате соответствующего отождествления входов (см. рис.
6.3b).Легко видеть, что при этомL Σ00 6 2q+1 + 2n−m+1 .(6.6)Искомая КС Σf является результатом корректной стыковки вида Σf = Σ00 (Σ0 ), полученной в результате присоединения входов КС Σ00 к выходам КС Σ0 в соответствии спредставлением 6.4, сложность которой, в силу 6.5–6.6, удовлетворяет неравенствуL (Σf ) 6 (p + 2)2n−m + (λ + 1)2q+1 .Из этого неравенства при q = m + p и3m=log n ,2√ s= n−2 n ,при которых выполнены условия (4.3) и (6.1), в силу (4.2) и§6. Асимптотически наилучший метод синтеза КС~~OO~~ ZdZdZdOZdOo• ǧe~~ooo 0,i~~..~~~.~OOZOO~~ZZZ@~d1 • @@ ΣG dododoo• ǧσ00 ,i@@..@@.@@O@@ OO@@ dZdZdZodZoO• ǧe1,i@@oo|{zΣ0i.........}47@@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Σ00a)}b)Рис.
6.3: к доказательству теоремы 6.1(4.4), вытекает неравенство 6.3 для сложности Σf , так какn−m(p + 2)22n2n6+ 3 · 2n−m =sn1+O1√n,22m+s+p+36s√322n√6 2n− n+3 log n = o.sn n(λ + 1)2q+1 6 p2s · 2m+p+2 6Теорема доказана.Следствие. Из 6.3 с учетом нижней оценки (4.12) вытекает, что2n.LK (n) ∼nЗамечание. Построенную КС Σf можно разбить на не более,48Глава 3. Синтез и сложность управляющих системчем2n√n n«звезд», каждая из которых состоит из контактов одногои того же типа. Для этого достаточно контакты всех звезд,показанных на рис.
6.2b, перераспределить в звезды из однотипных контактов, «центрами» которых являются выходыподсхем ΣG схем Σ0i , i = 1, . . . , 2q−m , а любой из остальныхконтактов КС Σf считать отдельной звездой.λp · 2p + 2n−m+1 + (λ + 1)2q+1 = OЛитература[1] Алексеев В. Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМиК МГУ, 2002.[2] Алексеев В. Б., Вороненко А. А., Ложкин С. А.,Романов Д. С., Сапоженко А.
А., Селезнева С. Н.Задачи по курсу «Основы кибернетики». Издательский отдел ф-та ВМиК МГУ, 2002.[3] Алексеев В. Б., Ложкин С. А. Элементы теории графов, схем и автоматов. М.: Издательский отдел ф-таВМиК МГУ, 2000.[4] Боровков А. А. Курс теории вероятностей. М.: Наука,1976.[5] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. 3-е изд., перераб.М.: ФИЗМАТЛИТ, 2004.[6] Дискретная математика и математические вопросы кибернетики, под редакцией С. В. Яблонского иО. Б. Лупанова. Т.
1. М.: Наука, 1974.[7] Евдокимов А. А. О максимальной длине цепи в единичном n-мерном кубе // Матем. заметки. 1969. 6. №3.С. 309–319.[8] Емеличев В. А., Мельников О. И., Сарванов В. И.,Тышкевич Р. И. Лекции по теории графов. М.: Наука,1977.4950Литература[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] Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики.Вып.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
