Введение к работе
Актуальность темы. Задача синтеза управляющих систем является одноії из основных задач математической кибернетики '. Она возникла в 30-х-40-х годах на основе ряда задач, связанных с логическим описанием и проектированием различных типов переключательных схем, и обрела строгую математическую постановку в работе К. Шеннона 2. С тех пор в области математической теории синтеза управляющих систем ведутся интенсивные исследования, актуальность которых обусловлена важностью многочисленных приложений, возникающих в различных разделах науки п техники.
В общем виде задача синтеза рассматривается для какого-либо класса управляющих систем, представляющего собой множество схем. наделенных определенной структурой и характеризующихся поведением (функционированием) дискретного типа. Предполагается, что схемы этого класса строятся по определенным правилам из элементов конечного априорно заданного базиса, каждый элемент которого характеризуется набором полюсов, функционированием и сложностью. а функционирование (сложность) схемы однозначно определяется ее структурой и функциональными (соответственно, сложностныыи) характеристиками ее элементов. Функционирование схемы, как правило, описывается некоторой системой булевских функций, а сложность схемы характеризуется положительным действительным числом, равным, обычно, сумме сложностей ("весов7') всех ее элементов.' Предполагается также, что рассматриваемый класс схем обладает свойством полноты, т.е. схемами из этого класса можно реализовать любую булевскую функцию. При этом предположении сложность булевской функции определяется как минимальное значение
'Яблонский СВ. Основные понятия кибернетик».// Проблемы кибернетики. Вып. 2.- М.:Физматгиз. 1959.- C.7-3S.
:SIiannon СЕ. The synthesis of two-terminal switching circuits // Bell Syst. Techn.. 1949. V.2S. N1. P. 59-9S.
сложности схем. реализующих эту функцию, а затем вводится т.н. функция Шеннона, которая зависит от натурального аргумента п и равна максимальной сложности булевских функций от п переменных.
Асимптотическая постановка задачи синтеза связана с изучением поведения то!! или juiofi функции Шеннона при растущем значении ее натурального аргумента п. При этом верхние оценки функций Шеннона получаются конструктивно на основе специальных методов синтеза, а соответствующие нижние оценки устанавливаются с помощью т.н. мощностного подхода, предложенного К. Шенноном2. Напомним, что в работе2 был установлен порядок роста функции Шеннона для сложности контактных схем, а в работах О. Б. Лупанова 3 л 5 6 наіідена асимптотика функции Шеннона для сложности булевских функции во всех основных классах схем: в классе контактных схем. классе релейно-коктактных схем. в классах формул и схем из функциональных элементов, построенных из элементов произвольного конечного полного базиса. Оказалось, что функция Шеннона для сложности булевских функций асимптотически равна С\2"/logп (в настоящей работе основание 2 у логарифмов опускается, а буквой с с_разлнч-ны.ми индексами или без них обозначаются константы, зависящие только от класса схем и его базиса) в классе формул и ci'2"/л в остальных классах схем. При этом, в частности, для функций Шеннона Lk [п), Lc[n) и L'p{n), характеризующих сложность булевских функций от л переменных в классе контактных схем из ориентированных контактов, в классе
3Лупа.нов О.Б. О сингезе контактных схем // ДАН СССР.- 195S- Т.119, N 1.-С.23-26.
4Лупаноа О.Б. Об одном методе синтеза схем. // Изв. вузов, Радиофизика.- 1058.- T.I. N.I.- С. 120-140.
'Лупаиов О.Б. О сложности реализации функций алгебры логик» формулами // Проблемы кибернетики. Вып. 3. - М.: Фіпматпп. 1960. - С. 61-S0.
'Лупанов О.Б. О сложности реализации функции алгебры логики релеіі но-контактными схемами.// Проблемы кибернетики. Вып. 11.-М.:Наука. 1064.- С. 25—IS.
схем из функциональных элементов над базисом {Л:. V.-i} и в классе формул над базисом {&:. V, ->} соответственно, нз работ О.Б.Лупанова вытекают оценки:
У/ 21оВп + 0(1)\ <х.(п)<Н!(1+31о6гг + 0(1))
п \ П J п \ п
g!fi + l0^ + 0(1)) < LHn)<2-(i + z^n + 0{l))
п \ п ) п \ п )
2" Л.п/ 1 \\^г*,^^ 2" Л , 21oglogn + 0(l)^
log ri I Vlogn// logn \
Iogn v Vlogn// logn\ logn j
Заметим, что указанные верхние оценки функций Шеннона получались для различных классов схем на базе различных синтезных конструкций, имевших, однако, общую методическую основу - т.н. метод Лупанова. Заметим также, что основная сложность построенных схем приходится на т.н. "легкие"' элементы базиса, на которых достигается экстремум, определяющий константу С\. Если при этом для схем нз функциональных элементов ввести т.н. глубину ветвления, которая равна максимальному числу элементов с ветвящимися выходами, лежащих на цепях из '"легких" элементов схемы, то можно отметить тот факт, что указанная верхняя оценка для Lc{n) достигается на схемах с глубиной ветвления, равной 0. Точность получаемых оценок можно характеризовать их относительной погрешностью (ОП), равной отношению разности между верхней и нижней оценками функции Шеннона к ней самой, а также нормированной относительной погрешностью (НОП). т.е. ОП, умноженной на logn в случае функции Шеннона для сложности формул, и ОП, умноженной на п, в остальных случаях. Отметим, что указанные выше оценки функций Шеннона LK{n). Lc(n) и L*{n) имеют НОП вида log а + 0(1). 2logn + 0(1) и 2 loglog п + 0(1) соответственно. Отметим также, что НОП оценок3 и6 для сложности контактных и релейно-контактных схем равна 0{Jn). а НОП оценок5
и4 ' для сложности формул и схем из функциональных элементов в произвольном полном базисе равна Tloglogn 4-0(1) и 2 logn + 0(1) соответственно.
Работа С. В. Яблонского8, где была найдена асимптотика функции Шеннона для сложности реализации контактными схемами булевских функций из т.н. инвариантных классов, образующих континуальное семейство, положила начало исследованиям, связанным с распространением перечисленных выше результатов "вширь". В дальнейшем, усилиями многих авторов (Андреев А.Е.. Захарова Е.Ю..Лу панов О. Б. .Марковский А.В.. Нечипорук Э.И., Редькин Н.П., Угольников А.Б., Шоломов Л.А., Яблонский СВ. и др.) была установлена асимптотика сложностных функций Шеннона для различных бо-' лее узких, по сравнению с множеством всех функций, классов и. в частности, для классов функций с фиксированным числом единиц, монотонных функций и др.. а также для сложности реаппашш не всюду определенных функций. Была получена асимптотика функции Шеннона для сложности схем, обладающих некоторыми дополнительными свойствами, и. в частности, свойством самокорректнруемости. а также схем с некоторыми ограничениями на структуру и. в частности, для схем с ограничениями на ветвление выходов элементов или для схем из блоков. Была найдена асимптотика функций Шеннона для сложности схем в некоторых бесконечных базисах, в некоторых т.н. вырожденных базнзах. когда веса отдельных элементов могут быть равны нулю, а также в некоторых неполных базисах. Была установлена асимптотика функций Шеннона для сложности схем и формул в некоторых базисах &-значной логики. При этом сначала в работе О.Б.Лупанова7, а затем
Мупанои О.Б. Об одной подходе к синтезу управляющих систем — принципе локального кодирования.// Проблемы кибернетики, вып. 14.- М.: Наука. 1965.- С. 31-110.
"Яблонскніі СВ. 06 алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики. Вып. 2.- М.:Фиэматгиз. 1959.-С. 75-121.
в работах Э.Н.Нечнпорука 9 и А.Е.Андреева 10 п были разработаны общие подходы, позволяющие получать асимптотику функции Шеннона для сложности булевских функций из специальных классов или для сложности булевских функций в различных классах самокорректирующихся схем. В работе С.В.Яблонского 12 предложен единый метод получения мощ-ностных нижних оценок в различных классах схем.
В работе О.Б.Лупанова 13 было установлено асимптотическое поведение функции Шеннона для естественной временной меры сложности схем из функциональных элементов, называемой задержкой или глубиной. Оказалось, что эта функция Шеннона асимптотически равна с',п, где п - число переменных, причем ОП ее оценок из13 имеет вид 0(logn/n). Поведение функции Шеннона для глубины булевских функций в базисе {&:,V,-i} последовательно уточнялось в работах и 19 и [1.3]. причем в[1.3] оно было установлено с точностью до слагаемого вида о(1). которое входит в сумму, находяи^у-юся под "знаком" ближайшего сверху целого числа. В работе [2] поведение функции Шеннона для глубины монотонных булевских функций в базисе {&. V} было установлено с точностью до слагаемого вида 0[1). Вместе с тем, относительная-точность оценок для экспоненциальных сложностных функ-
'Нечипорук Э.И. О топологических принципах самокорректирования // Проблемы кибернетики. Вып.21.- М.:Наука. 1969.- С. 5-102.
'"Андреев А.Е. О синтезе функциональных сетей.- М.:11зд-во МГУ, 19S5.-250 с.
"Андреев А.Е. Универсальный принцип-самокорректирования // Мат. сборник.- 19S-5-- Т. 127 (169), К 6- С. 147-172.
1;Яблонскнп СВ. Нижние мошностные оценки для сложности реализации функций из Рк схемами из функциональных элементов в произвольном базисе // Дискретная математика, т. 6 (1994), вып.4.- С. 3-9.
'Vlynanoa О.Б. О схемах из функциональных элементоп с задержками // Проблемы кибернетики. Вып.23.- M..HavKa. 1970.- С. 43-81.
иМсСо11 W.R.Paterson M.S. The depth of all Boolean functions // SIAM J. of Computing. 1977. V.6. N2. P. 373-3S0.
"Гашков СБ. О глубине булевых функции // Проблемы кибернетики. Вып. 34.- М.:Наука, 1976.- C.265-26S.
ціні Шеннона во всех указанных выше работах не превышала точности соответствующих оценок из3-'.
Цель работы. Конечной целью данной работы является получение оценок высокой степени точности, т.е.. как правило, оценок с НОП вида 0(1), для функции Шеннона, характеризующих сложность реализации булевских функций во всех основных и некоторых других классах схем. Достижение этой цели основано на разработке новых методов синтеза, которые позволяют получать верхние оценки высокой степени точности и являются универсальными в том смысле, что они единообразно, без изменения основных конструкций, применяются к различным классам схем (схемам из функциональных элементов, контактным схемам, формулам и др.) Соответствующие нижние оценки устанавливаются при этом с помощью модифицированных мошностных методов. Создание указанных методов также является целью работы.
Методы исследования. Получение оценок высокой степени точности для сложности управляющих систем потребовало формирования новых понятий и подходов, разработки принципиально новых методов оптимального синтеза схем. Наряду с ними в работе использованы известные подходы и. методы асимптотической теории сложности управляющих систем, а также теории булевских функций, дискретного анализа, теории графов и других разделов дискретной математики и математической кибернетики.
Научная новизна. Данная работа представляет собой первое исследование, направленное на получение оценок высокой степени точности для сложности управляющих систем. Все основные результаты диссертации являются новыми. Перечислим некоторые из них.
Разработаны новые универсальные методы синтеза, позволяющие получать оценки высокой степени точности для сложности управляющих систем. Для удобства применения этих методов на базе сетей нз т.н. функционально-проводящих эле-
ментов (ФПЭ) создана единая структурно-логическая модель управляющих систем, которая охватывает все основные и некоторые другие классы схем.
С помощью новых методов поведение функцнії Шеннона для сложности булевских функций в классе формул, а также в классе схем из функциональных элементов с глубиной ветвления 0 и 1 над произвольным конечным полным базисом установлено с НОП вида 0(1). Оценки с НОП впда 0(1) получены в диссертации для схем из ФПЭ над т.н. строго итеративными базисами, причем частными случаями таких классов схем являются контактные н обобщенные контактные схемы из ориентированных контактов, некоторые классы релейно-контактных схем и др.
Оказалось, что при заданной константе С] и ограниченном числе входов у элементов базиса в любом из указанных классов схем имеется конечное число различимых на уровне оценок с НОП вида 0(1) типов поведения функции Шеннона, каждый из которых связан с определенным набором функциональных и метрических свойств легких элементов базиса. При этом как в классе формул, так и в классе схем из функциональных элементов с глубиной ветвления і, і Є {0,1}, имеется ровно два таких типа. Отмеченное явление установлено впервые.
Из полученных результатов следует, в частности, что
Lc{n) = 21 (і + logn + 0(loglognn
''-'-бІпгИШ)
Разработанные в диссертации методы могут быть использованы при получении оценок высокой степени точности для глубины или задержки булевских функций. С их помощью в [11]
удалось установить поведение функции Шеннона для глубины булевских функцпіі в произвольном полном базисе с ОП вида 0(1/«). тогда как известные ранее оценки13 имели ОП вида 0[logn/n). Предложенные методы могут быть применены при синтезе схем и формул в различных базисах многозначной логики. С их помощью в [9] были получены оценки функции Шеннона для сложности формул в некоторых полных базисах Рк. имеющие ОП вида 0(1/log л).
Основные результаты, выносимые на зашиту. На зашиту выносятся следующие основные результаты: оценки с НОП вида 0(1) для функций Шеннона, характеризующих сложность реализации булевских функций формулами над произвольным конечным полным базисом, схемами из функциональных элементов с глубиной ветплення 0 н 1 над произвольным конечным полным базисом, а также схемами из ФПЭ над произвольным конечным полным строго итеративным базисом.
Теоретическая и практическая ценность. Данная работа носит теоретический характер. Полученные в ней результаты дают достаточно полную картину поведения функций Шеннона для сложности булевских функций во всех основных и некоторых других классах схем на уровне оценок высокой степени точности. Результаты диссертации создают базу для нового этапа в развитии асимптотической теории синтеза управляющих систем, который связан с их распространением "вширь", т.е. с получением оценок высокой степени точности для сложности булевских функций из специальных классов, для сложности реализации булевских функций схемами с дополнительными свойствами и др. Результаты и методы данной работы могут найти применение в различных областях дискретной математики, а также в технпк(&-при логическом проектировании больших и сверхбольших интегральных схем.
Апробация работы и публикации. Результаты диссертации в 1995-1997 годах неоднократно докладывались на се-
мпнарах по математическим вопросам кибернетик» (рук. членкор]). РАН. профессор С.В.Яолонскпіі), синтезу управляющих систем (рук. член-корр. РАН. профессор О.Б.Лупанов) в МГУ, на V международном семинаре по дискретной математике и ее приложениям (Москва, 1995 г.). на XI международной конференции по теоретическим проблемам кибернетики (Ульяновск, 199G г.), па международных конференциях "Дискретные модели в теории управляющих систем" (Подмосковье, 1995.1997).'
Все основные результаты диссертации опубликованы. По теме диссертации автором опубликовано 11 печатных работ.
Структура работы. Диссертация состоит из введения, трех глав и списка литературы. Глава 1 разбита на два параграфа, глава 2 - на четыре параграфа и глава 3 - на два параграфа. Список литературы содержит 53 наименования. Общий, объем работы составляет 99 страниц машинописного текста.