оки3 (1155746), страница 8
Текст из файла (страница 8)
Пусть Q — инвариантный класс ФАЛ. Тогдаего мощностная последовательность σQ (n) монотонно невозрастает и сходится к пределуσQ = lim σQ (n) = limn→∞n→∞log |Q(n)|,2nгде число σQ удовлетворяет неравенствам 0 6 σQ 6 1.Доказательство. Из определения последовтельности σQ (n)следует, что для каждого n выполнено неравенство 0 6σQ (n) 6 1, то есть эта последовательность σQ (n) ограничена. Покажем, что она монотонно не возрастает, откуда будетследовать её сходимость. В силу инвариантности класса Q,всякую функцию f из множества Q(n + 1) можно представить в видеf (x1 , .
. . , xn+1 ) = xn+1 f0 (x1 , . . . , xn ) ∨ xn+1 f1 (x1 , . . . , xn ),где fσ (x1 , . . . , xn ) = f (x1 , . . . , xn , σ), σ ∈ B, и обе ФАЛ f0 ,f1 принадлежат множеству Q(n). Отсюда сразу вытекает62Глава 3. Синтез и сложность управляющих системнеравенство|Q(n + 1)| 6 |Q(n)|2 ,из которого, в свою очередь, следуeт, чтоσQ (n + 1) =log |Q(n)|log |Q(n + 1)|6= σQ (n).n+122nМонотонное невозрастание и, следовательно, сходимость последовательности σQ (n), n = 1, 2, . . .
, доказана, а принадлежность её предела σQ действительному отрезку [0, 1] следует из того, что ему принадлежат все члены данной последовательности.Лемма доказана.Замечание. Предел σQ будем называть мощностной характеристикой класса Q. При этом инвариантный класс Q схарактеристикой σQ = 0 (σQ > 0) называется нулевым (соответственно ненулевым).Рассмотрим достаточно общий подход к решению задачисинтеза СФЭ для ФАЛ из специальных классов, предложенный в работе [17] О.
Б. Лупанова и названный им принципомлокального кодирования.Основаная идея этого подхода состоит в том, чтобы спомощью определённого «кодирования» свести задачу синтеза СФЭ для ФАЛ или систем ФАЛ из заданного класса Qк аналогичной задаче синтеза для класса произвольных илиблизких к ним систем ФАЛ соответствующей размерности.Следующее утверждение и его доказательство дают примеррешения задачи синтеза СФЭ для ФАЛ из инвариантногокласса Q с помощью принципа локального кодирования.Лемма 9.3. Для всякого инвариантного класса Q и n =§9.
Синтез схем для функций из специальных классов631, 2, . . .2nLC Q(n) ∼ σQпри σQ > 0,(9.7)n 2n при σQ = 0.(9.8)LC Q(n) = o σQnДоказательство. Рассмотрим сначала случай σQ > 0. Вэтом случае в соответствии с введёнными выше обозначениями и в силу леммы 9.2 получимσQ (n) · 2nlog |Q(n)|2nJ Q(n) ==∼σ,Qlog log |Q(n)|log(σQ (n) · 2n )nоткуда по лемме 9.1 следует нижняя оценка (9.7).Перейдём к получению верхней оценки (9.7). Для этого возьмём произвольное натуральное n и натуральное q,q 6 n, а затем обычным образом разобьём набор БП x =(x1 , . . . , xn ) на поднаборы x0 = (x1 , . . .
, xq ) и x00 =(xq+1 , . . . , xn ). Выберем из множества Q(n) произвольнуюФАЛ f и для каждого набора σ 00 , σ 00 ∈ B n−q (x00 ), положимкак обычно, fσ00 (x0 ) = f (x0 , σ 00 ), причём в данном случаеfσ00 (x0 ) ∈ Q(q) в силу инвариантности класса Q.Положим λ = dlog |Q(q)|e и пусть Π0 — произвольное инъективное отображение (кодирование) ФАЛ множества Q(q) двоичными наборами куба B λ от БП y =(y1 , . . . , yλ ), то есть Π0 : Q(q) 7→ B λ (y), которое существует,так как 2λ > |Q(q)|.
Заметим, что ФАЛ fσ00 (x0 ) однозначно определяется своим «кодом» πσ00 = Π0 (fσ00 (x0 )) и поэтомусуществует ФАЛ h(x0 , y), h ∈ P2 (q + λ), такая чтоf (σ 0 , σ 00 ) = h(σ 0 , πσ00 )при любых σ 0 и σ 00 из B q (x0 ) и B n−q (x00 ) соответственно.Пусть O = (O1 , . . . , Oλ ) ∈ P2λ (n−q) — система ФАЛ, которая сопоставляет произвольному набору σ 00 , σ 00 ∈ B n−q , набор («код») πσ00 и пусть СФЭ ΣO из UC , построенная асимптотически наилучшим методом, реализует эту систему ФАЛ64Глава 3.
Синтез и сложность управляющих системсо сложностью 2n−q 2n−qL ΣO 6 λ+o.n−qn−qИскомая СФЭ Σf реализует ФАЛ f в соответствии спредставлениемf (x0 , x00 ) = h(x0 , O(x00 ))и содержит в качестве подсхемы СФЭ ΣO (x00 , y), а такжепостроенную асимптотически наилучшим методом СФЭ Σh ,которая реализует ФАЛ h(x0 , y).Полагая q = dlog ne, и учитывая, чтоλ 6 σQ (q)2q + 1 .
σQ 2q ,получим верхнюю оценку2n2n−q. σQ .L Σf . σQ 2qn−qnВ случае σQ > 0 отсюда, с учётом нижней оценки, вытекает (9.7).В случае σQ = 0 искомая СФЭ Σf строится аналогично,но так как при этом полседовательность σQ (q) стремится кнулю, то 2n L Σf = o,nчто доказывает (9.8).Лемма доказана.Литература[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] Мурога С. Системы проектирования сверхбольшихинтегральных схем. М.: Мир, 1985.[19] Нечипорук Э. И.
О топологических принципах самокорректирования // Проблемы кибернетики. Вып. 21.М.: Наука, 1969. С. 5–102.[20] Нигматуллин Р. Г. Сложность булевых функций.М.: Наука, 1991.[21] Поваров Г. Н. Метод синтеза вычислительных и управляющих контактных схем // Автоматика и телемеханика. 1957. Т. 18. №2.
С. 145–162.[22] Сапоженко А. А. Дизъюнктивные нормальные формы. М.: Изд-во МГУ, 1975.[23] Сапоженко А. А. Некоторые вопросы сложности алгоритмов. Издательский отдел ф-та ВМиК МГУ, 2001.[24] Сапоженко А. А., Ложкин С. А. Методы логического проектирования и оценки сложности схем на дополняющих МОП-транзисторах // Микроэлектроника.
1983. Т. 12. №1. С. 42–47.[25] Фихтенгольц Г. М. Основы математического анализа,том 1. М.: Наука, 1968.[26] Фихтенгольц Г. М. Основы математического анализа,том 2. М.: Наука, 1964.[27] Чегис И. А., Яблонский С. В. Логические способыконтроля работы электрических схем // Труды МИАН СССР. Т. 51. М.: Изд-во АН СССР, 1958. С. 270–360.68Литература[28] Яблонский С.
В. Введение в дискретную математику.2-е изд., перераб. и доп. М.: Наука, 1986.[29] Яблонский С. В. Надежность управляющих систем.М.: Изд-во МГУ, 1991.[30] Яблонский С. В. Некоторые вопросы надежности иконтроля управляющих систем // Математические вопросы кибернетики. Вып. 1. М.: Наука, 1988. С. 5–25.[31] Яблонский С. В. Элементы математической кибернетики. М.: Высшая школа, 2007.[32] 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.[33] Shannon C. E. The syntesis of two-terminal switchingcircuits // Bell Syst. Techn. J. 1949. V. 28. №1.P. 59–98 (Русский перевод: Шеннон К. Работы потеории информации и кибернетике. М.: ИЛ, 1963.С. 59–101).[34] Wegener I. Branching programs and binary decisiondiagrams. SIAM Publishers, 2000..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
