Асимптотические оценки высокой степени точности для сложности управляющих систем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА

Асимптотические оценка высокой степени точности для сложности управляющих систем

Специальность 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физик0- математических наук

Механико-математический факультет

рге од

На правах рукописи УДК 519.6

Ложкин Сергей Андреевич

Москва-1997

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета им VI.В. Ломоносова.

Официальные

оппоненты: доктор физико-математи-

ческих наук, профессор М.М.Глухов

доктор физико-математических наук, профессор Н.П.Редькин

м. доктор физико-математи-

ческих наук, профессор Л.А.Шоломов

Институт математики им.С.Л.Соболева Сибирского отделения РАН

Зашита диссертации состоится "•^У" <)(Л'/М 1997 г.

в 16 час 15 мин. на заседании диссертационного совета Д.053.05.05 прп Московском государственном университете им М.В.Ломоносова по адресу:

110899. ГСП. Москва, Воробьевы горы. МГУ, механико-матсматическш! факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ ¿Главное здание, 14 этаж).

Автореферат разослан ' •-/У" ¿ОЪ^^Щ. 1997 г.

Ведущая организация:

Ученый секретарь диссертационного совета Д.053.05.05 при МГУ д.ф.-м.н.. профессор

В.Н.Чубариков

§ 1 Общая характеристика работы

Актуальность темы. Задача синтеза управляющих систем является одной нз основных задач математической кибернетики Она возникла в 30-х-40-х годах на основе ряда задач, связанных с логическим описанием и проектированием различных типов переключательных схем, и обрела строгую математическую постановку в работе К. Шеннона 2. С тех пор в области математической теории синтеза управляющих систем ведутся интенсивные исследования, актуальность которых обусловлена важностью многочисленных приложений, возникающих в различных разделах науки и техники.

В общем виде задача синтеза рассматривается для какого-либо класса управляющих систем, представляющего собой множество схем. наделенных определенной структурой и характеризующихся поведением (функционированием) дискретного типа. Предполагается, что схемы этого класса строятся по определенным правилам нз элементов конечного априорно заданного базиса, каждый элемент которого характеризуется набором полюсов, функционированием и сложностью, а функционирование (сложность) схемы однозначно определяется ее структурой и функциональными (соответственно, сложностныыи) характеристиками ее элементов. Функционирование схемы, как правило, описывается некоторой системой булевских функций, а сложность схемы характеризуется положительным действительным числом, равным, обычно, сумме сложностей ("весов") всех ее элементов.' Предполагается также, что рассматриваемый класс схем обладает свойством полноты, т.е. схемами из этого класса можно реализовать любую булевскую функцию. При этом предположении сложность булевской функции определяется как минимальное значение

'Яблонский C.B. Основные понятия кибернетик«.// Проблемы кибернетики. Вып. 2.- М.:Физматгиз. 1959.- C.7-3S.

:Shannon С.Е. The synthesis of two-terminal switching circuits // Bell Syst. Techn.. 1049. V.2S. N1. P. 59-9$.

сложности схем. реализующих эту функцию, а затем вводится т.н. функция Шеннона, которая зависит от натурального аргумента п и равна максимальной сложности булевских функций от п переменных.

Асимптотическая постановка задачи синтеза связана с изучением поведения то!! или иной функции Шеннона при растущем значении ее натурального аргумента п. При этом верхние оценки функций Шеннона получаются конструктивно на основе специальных методов синтеза, а соответствующие нижние оценки устанавливаются с помощью т.н. мощностного подхода. предложенного К. Шенноном2. Напомним, что в работе2 был установлен порядок роста функции Шеннона для сложности контактных схем, а в работах О. Б. Лупанова 3 * 5 6 найдена асимптотика функции Шеннона для сложности булевских функций во всех основных классах схем: в классе контактных схем. классе релейно-контактных схем. в классах формул и схем из функциональных элементов, построенных из элементов произвольного конечного полного базиса. Оказалось, что функция Шеннона для сложности булевских функций асимптотически равнас\2п/\о%п (в настоящей работе основание 2 у логарифмов опускается, а буквой с с_различ-ными индексами или без них обозначаются константы, зависящие только от класса схем и его базиса) в классе формул и с\2"¡п в остальных классах схем. При этом, в частности, для функций Шеннона Ьк (п), Ьс[п) и Ь'р{п), характеризующих сложность булевских функций от п переменных в классе контактных схем из ориентированных контактов, в классе

^Лупанов О.Б. О синтезе контактных схем // ДАН СССР.- 1958 - ТЛ19, N 1.- С.23-26.

4Лупаноа О.Б. Об одном методе синтеза схем. // Изв. вузов, Радиофизика,- 1058,- Т.1. N.1,- С. 120-140.

'Лупаиов О.Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. - М.: Физматпп. 1960. - С. 61-80.

'Лупаиов О.Б. О сложности реализации функции алгебры логики релей но-контактными схемами.// Проблемы кибернетики. Вып. 11.-М.:На\ка. 1064.- С. 25-4Й.

схем из функциональных элементов над базисом {<£:. V.-!} и в классе формул над базисом {&:. V, ->} соответственно, из работ О.Б.Лупанова вытекают оценки:

2^1+21оВп + 0(1)\ < х.(п)<Н!(1+31о6гг + 0(1))

п \ п / п \ п

п \ п ) п \ п )

2" П -- г*,.., , Л , aiogiogn+ 0(i)4

log П 4 Vlogn// bgn\ logn /

Заметим, что указанные верхние оценки функций Шеннона получались для различных классов схем на базе различных синтезных конструкций, имевших, однако, общую методическую основу - т.н. метод Лупанова. Заметим также, что основная сложность построенных схем прнходптся на т.н. "легкие'' элементы базиса, на которых достигается экстремум, определяющий константу Ci. Если при этом для схем из функциональных элементов ввести т.н. глубину ветвления, которая равна максимальному числу элементов с ветвящимися выходами. лежащих на цепях из "легких"' элементов схемы, то можно отметить тот факт, что указанная верхняя оценка для Lc{n) достигается на схемах с глубиной ветвления, равной 0.

Точность получаемых оценок можно характеризовать их относительной погрешностью (ОП), разной отношению разности между верхней и нижней оценками функции Шеннона к ней самой, а также нормированной относительной погрешностью (НОП). т.е. ОП, умноженной на logn в случае функции Шеннона для сложности формул, и ОП, умноженной на л, в остальных случаях. Отметим, что указанные выше оценки функций Шеннона LK(n). Lc(n) и L"*(n) имеют НОП вида loga + 0(1). 2logn + 0(1) и 2 lóglogn + 0(1) соответственно. Отметим также, что НОП оценок3 и6 для сложности контактных и релейно-контактных схем равна 0{Jñ). а НОП оценок5

и4 ' для сложности формул и схем из функциональных элементов в произвольном полном базисе равна Tloglogn 4-0(1) и 2 log п 4-0(1) соответственно.

Работа С. В. Яблонского8, где была найдена асимптотика функции Шеннона для сложности реализации контактными схемами булевских функций из т.н. инвариантных классов, образующих континуальное семейство, положила начало исследованиям. связанным с распространением перечисленных выше результатов "вширь". В дальнейшем, усилиями многих авторов (Андреев А.Е..ЗахароваЕ.Ю.. ЛупановО.Б..Марковский A.B.. Нечипорук Э.И., Редькин Н.П., Угольников A.B., Шоломов Л.А., ЯблонскиИ C.B. и др.) была установлена асимптотика сложностных функций Шеннона для различных бо- ' лее узких, по сравнению с множеством всех функций, классов п. в частности, для классов функций с фиксированным числом единиц, монотонных функций и др.. а также для сложности реализации не всюду определенных функций. Была получена асимптотика функции Шеннона для сложности схем, обладающих некоторыми дополнительными свойствами, и. в частности. свойством самокорректнруемости. а также схем с некоторыми ограничениями на структуру и. в частности, для схем с ограничениями на ветвление выходов элементов или для схем из блоков. Была найдена асимптотика функций Шеннона для сложности схем в некоторых бесконечных базисах, в некоторых т.н. вырожденных базизах. когда веса отдельных элементов могут быть равны нулю, а также в некоторых неполных базисах. Была установлена асимптотика функций Шеннона для сложности схем и формул в некоторых базисах ¿-значной логики. При этом сначала в работе О.Б.Лупанова7, а затем

Мупанов О.Б. Об одной подходе к синтезу управляющих систем — прин-

ципе локального кодирования.// Проблемы кибернетики, вып. 14.- М.: Наука. 1965.- С. 31-110.

"ЯблонскнИ C.B. 06 алгоритмических трудностях синтеза минимальных

контактных схем // Проблемы кибернетики. Вып. 2,- М.:Фиэматгиз. 1959.-

С. 75-121.

в работах Э.П.Нечпиорука 9 н А.Е.Андреева 10 11 были разработаны общие подходы, дозволяющие получать асимптотику функции Шеннона для сложности булевских функций из специальных классов или для сложности булевских функций в различных классах самокорректирующихся схем. В работе С.В.Яблонского 12 предложен единый метод получения мощ-ностных нижних оценок в различных классах схем.

В работе О.Б.Лупанова 13 было установлено асимптотическое поведение функции Шеннона для естественной временной меры сложности схем из функциональных элементов. называемой задержкой или глубиной. Оказалось, что эта функция Шеннона асимптотически равна с\п, где п - число переменных, причем ОП ее оценок из13 имеет вид 0(logn/n). Поведение функции Шеннона для глубины булевских функций в базисе {¿,V,-i} последовательно уточнялось в работах и 13 и [1.3]. причем в[1.3] оно было установлено с точностью до слагаемого вида о(1). которое входит в сумму, находящуюся под "знаком" ближайшего сверху целого числа. В работе [2] поведение функции Шеннона для глубины монотонных булевских функций в базисе {¿с. V} было установлено с точностью до слагаемого вида 0(1). Вместе с тем, относительная-точность оценок для экспоненциальных сложностных функ-

'Нечипорук Э.И. О топологических принципах самокорректирования // Проблемы кибернетики. Вып.21.- М.:Наука. 1969.- С. 5-102.

'"Андреев А.Е. О синтезе функциональных сетей.- М.:11зд-во МГУ, 19S5.-250 с.

"Андреев А.Е. Универсальный принцип-самокорректирования // Мат. сборник.- 19S-5-— Т. 127 (169), К 6 - С. 147-172.

1;Ябло11скн(! C.B. Нижние мошностные оценкн для сложности реализации функция из Рк схемами из функциональных элементов в произвольном базисе // Дискретная математика, т. 6 (1994), вып.4.- С. 3-9.

'VlynanoB О.Б. О схемах из функциональных элементоп с задержками // Проблемы кибернетики. Вып.23.- M..HavKa. 1970.- С. 43-81.

иМсСо11 W.F..Paterson M.S. The depth of all Boolean functions // SIAM J. of Computing. 1977. V.6. N2. P. 373-3S0.

"Гашков С'.Б. О глубине булевых функций // Проблемы кибернетики. Вып. 34.- М.:Наука, 197$.- C.26Ô-26S.

miii Шеннона во всех указанных выше работах не превышала точности соответствующих оценок из3-'.

Цель работы. Конечной целью данной работы является получение оценок высокой степени точности, т.е.. как правило. оценок с НОП вида 0(1), для функций Шеннона, характеризующих сложность реализации булевских функций во всех основных и некоторых других классах схем. Достижение этой цели основано на разработке новых методов синтеза, которые позволяют получать верхние оценки высокой степени точности и являются универсальными в том смысле, что они единообразно. без изменения основных конструкций, применяются к различным классам схем (схемам из функциональных элементов. контактным схемам, формулам и др.) Соответствующие нижние оценки устанавливаются при этом с помощью модифицированных мошностных методов. Создание указанных методов также является целью работы.

Методы исследования. Получение оценок высокой степени точности для сложности управляющих систем потребовало формирования новых понятий и подходов, разработки принципиально новых методов оптимального синтеза схем. Наряду с ними в работе использованы известные подходы и. методы асимптотической теории сложности управляющих систем, а также теории булевских функций, дискретного анализа, теории графов и других разделов дискретной математики и математической кибернетики.

Научная новизна. Данная работа представляет собой первое исследование, направленное на получение оценок высокой степени точности для сложности управляющих систем. Все основные результаты диссертации являются новыми. Перечислим некоторые из них.

Разработаны новые универсальные методы синтеза, позволяющие получать оценки высокой степени точности для сложности управляющих систем. Для удобства применения этих методов иа базе сетей из т.н. функционально-проводящих эле-

ментов (ФПЭ) создана единая структурно-логическая модель управляющих систем, которая охватывает все основные и некоторые другие классы схем.

С помощью новых методов поведение функций Шеннона для сложности булевских функций в классе формул, а также в классе схем из функциональных элементов с глубиной ветвления 0 и 1 над произвольным конечным полным базисом установлено с НОП вода 0(1). Оценки с НОП вида 0(1) получены в диссертации для схем из ФПЭ над т.н. строго итеративными базисами, причем частными случаями таких классов схем являются контактные и обобщенные контактные схемы из ориентированных контактов, некоторые классы релейно-контактных схем и др.

Оказалось, что при заданной константе сi и ограниченном числе входов у элементов базиса в любом из указанных классов схем имеется конечное число различимых на уровне оценок с НОП вида 0(1) типов поведения функции Шеннона, каждый из которых связан с определенным набором функциональных и метрических свойств легких элементов базиса. При этом как в классе формул, так и в классе схем из функциональных элементов с глубиной ветвления г, г 6 {0,1}, имеется ровно два таких типа. Отмеченное явление установлено впервые.

Из полученных результатов следует, в частности, что

Разработанные в диссертации методы могут быть использованы при получении оценок высокой степени точности для глубины или задержки булевских функций. С их помощью в [11]

Lc(n) = \

п

s

удалось установить поведение функции Шеннона для глубины булевских функций в произвольном полном базисе с ОП вида 0(1/«). тогда как известные ранее оценки13 имели ОП вида 0(logn/n). Предложенные методы могут быть применены при синтезе схем и формул в различных базисах многозначной логики. С их помощью в [9] были получены оценки функции Шеннона для сложности формул в некоторых полных базисах Рк. имеющие ОП вида 0(l/logn).

Основные результаты, выносимые на заш^ту. На защиту выносятся следующие основные результаты: оценки с НОП вида 0(1) для функций Шеннона, характеризующих сложность реализации булевских функций формулами над произвольным конечным полным базисом, схемами из функциональных элементов с глубиной ветвления 0 и 1 над произвольным конечным полным базисом, а также схемами из ФПЭ над произвольным конечным полным строго итеративным базисом.

Теоретическая и практическая ценность. Данная работа носит теоретический характер. Полученные в ней результаты дают достаточно полную картину поведения функций Шеннона для сложности булевских функций во всех основных и некоторых других классах схем на уровне оценок высокой степени точности. Результаты диссертации создают базу для нового этапа в развитии асимптотической теории синтеза управляющих систем, который связан с их распространением "вширь", т.е. с получением оценок высокой степени точности для сложности булевских функций из специальных классов, для сложности реализации булевских функций схемами с дополнительными свойствами и др. Результаты и методы данной работы могут найти применение в различных областях дискретной математики, а также в технпк(&-при логическом проектировании больших и сверхбольших интегральных схем.

Апробация работы и публикации. Результаты диссертации в 1995-1997 годах неоднократно докладывались на се-

мпнарах по математическим вопросам кибернетики (рук. членкор ]>. РАН. профессор С.В.Яблонский), синтезу управляющих систем (рук. член-корр. РАН. профессор О.Б.Лупанов) в МГУ, на V международном семинаре по дискретной математике и ее приложениям (Москва, 1995 г.). на XI международной конференции по теоретическим проблемам кибернетики (Ульяновск, 1996 г.), на международных конференциях "Дискретные модели в теории управляющих систем" (Подмосковье, 1995.1997).'

Все основные результаты диссертации опубликованы. По теме диссертации автором опубликовано 11 печатных работ.

Структура работы. Диссертация состоит из введения, трех глав и списка литературы. Глава 1 разбита на два параграфа. глава '2 - на четыре параграфа и глава 3 - на два параграфа. Список литературы содержит 53 наименования. Общий объем работы составляет 99 страниц машинописного текста.

§ 2 Основное содержание работы

Во введении приводится асимптотический постановка задачи синтеза управляющих систем и обзор результатов, связанных с темой диссертации, дается характеристика работы и формулируются в общем виде полученные в ней результаты.

В первой главе диссертации излагается единая структурно-логическая модель управляющих систем, которая обобщает и объединяет все основные классы схем. Структурной базой этой модели являются сети из т.н. функционально-проводящих элементов (ФПЭ). Каждый ФПЭ представляет собой блок из ориентированного или неориентированного контакта и функционального элемента, причем выход функционального элемента не является полюсом, а лишь "управляет" проводимостью контакта, "открывая" его своим единичным значением и "закрывая" нулевым. К полюсам сети, построенной из ФПЭ. относятся ее входы, выходы и истоки, а функционирование соответствующей схемы определяется в § 1 как

множество ее т.н. допустимых пар. каждая из которых состоит из входного и выходного наборов схемы (ср.6 16). Если каждый входной набор схемы участвует не более чем в одной допустимой паре, то схема считается преобразующей, а ее функционирование задается некоторым частичным оператором, т.е. системой частичных булевских функций с общей областью определенности. В § 1 для схем из ФПЭ обычным образом определяется операция суперпозиции, устанавливается критерий полноты для класса преобразующих схем над заданным базисом (теорема 1), а также доказывается, что т.н. ациклические схемы из ФПЭ являются преобразующими (лемма 2). При этом отмечается, что если суперпозиция прообразующих схем является преобразующей схемой, то она реализует некоторое доопределение соответствующей суперпозиции частичных операторов.

Пусть - класс ациклических схем над базисом Б, Б =

{Е|.....ЕГ}. где ФПЭ Е,■, г = 1____,?•, имеет "вес" р,-, р,' > 0,

и состоит из функционального элемента, который реализует булрвскую функцию существенно зависящую от А:,- переменных. а также контакта с признаком ориентированности с,-, С; £ {0.1}. В § 2 все основные классы схем и некоторые их обобщения рассматриваются как подклассы класса выделяемые из него наложением определенных ограничений на структуру сети. Это относится, в частности, к классу - классу схем из функциональных элементов над базисом Б. При изучении класса и его подклассов вводятся, как обычно, параметры

Р] = - Р' ■, где к) > 2, 1 < } < г, и рв = пШ1р},

к; у — 1

а легкими элементами Б считаются те элементы для которых р;- = рв- Вводится также булевский параметр «б- ко_

"Саиожсико А.А.. Ложкин С.А. Методы логического проектирования и оценки сложности схем на дополняющих МОП-транзисторах.// Микроэлектроника.- 1983.- Т. 12. N 1- С.<12-47.

торыН является признаком симметричности базиса Б и равен 1 тогда и только тогда, когда множество, состоящее из базисных функций легких элементов, содержится либо во множестве линейных функций, либо во множестве конъюнкций переменных, либо во множестве дизъюнкций переменных.

В классе 5ц выделяется подкласс формул ¿>£ и, кроме того,

для любого г = 0.1,____выделяется подкласс состоящий

из всех схем с глубиной ветвления не больше, чем г.

Во многих случаях ограничения на структуру сети задаются тем, что первые 0 < к[ < А-;, входов функционального элемента, входящего в ФЛЭ £;, г = объявляются т.н. "прямыми" входами, которые при построении схемы могут присоединяться только к ее прямым сходам, истокам или т.н. антннстокам. При этом остальные входы элемента (схемы) считаются итеративными" входами. Схема," удовлетворяющая указанным требованиям, считается итеративно правильной, а через 5цА обозначается множество всех итеративно правильных схем из 5ц . Частными случаями классов вида «5з1Л являются классы контактных и обобщенных контактных схем. некоторые классы релейно-контактпых схем и др. При изучении класса ^А вводятся параметры:

Pi „ 2kJ - Щ +3 • 1

= з^фтг- е'= +1 'где j = 1.....г-"

7Гк = mill 7Г;, 0G = min О;,

а к легким элементам базиса осносятся те элементы Ej. для которых -j = -в и Оj — ©Б. Базис Б считается строго итеративным, если для некоторого легкого элемента Ej из функции *pjdj можно получить тождественный ноль в результате подстановки константы вместо одной из итеративных входных переменных. Частными случаями классов вида S}jA, где Б -строго итеративный базис, являются классы контактных и обобщенных контактных схем. построенные из ориентированных

контактов, а также некоторые классы релейно-контактньгх схем.

В § 2 устаиаилпвается критерий полноты для класса (теорема 3). а также формулируются результаты диссертации, связанные с оценками высокой степени точности для функций Шеннона и £{-л(п) в полных классах б^'1,

где 1 = 0,1, и где Б - строго итеративный базис, соответственно. Эти оценки в указанных классах схем выглядят следующим образом:

Предлагаемые в диссертации методы синтеза ациклических схем из ФПЭ основаны на построении и использовании т.н. универсальных булевских матриц и связанных с ними т.н. представительных разбиений единичного куба. Универсальная для булевской функции •-,!/() матрица С позволяет получить любой булевский столбец 0, высота которого равна высоте и. в результате построчного применения функции у к матрице [/', которая задается упорядоченной выборкой, состоящей из 1 столбцов матрицы 1\ т.е. представить его в виде •3 = -р(Сг'). Матрицей, универсальной для функции <р(у) = у, является, в частности, матрица высоты 5,5 = 1,2,..., столбцами которой являются все различные столбцы из 0 и 1 высоты 5, расположенные в порядке возрастания номеров. Если функция <¿7 реализуется схемой, имеющей прямые входы, то те столбцы ^-универсальной матрицы С/, которые используются для подстановки вместо прямых входов (¿>, считаются прямыми столбцами и, а все остальные столбцы II - ее итеративными столбцами.

Представительное для матрицы М высоты 27 разбиение О единичного гг-мерного куба В" характеризуется тем. что каждая компонента с1 разбиения В взаимно однозначно проектируется в подкуб В7 от д т.н. опорных переменных куба В" и что каждый прямой столбец М совпадает на в. либо со столбцом значений одной из переменных куба, либо со столбцом значений ее отрицания, если г-й строке матрицы Л/ сопоставить набор из (I. у которого подиабор значений опорных переменных имеет номер г. г = 1.....27. Итеративные столбцы матрицы М задают при этом ее столбцовые булевские функции, зависящие от опорных переменных. Те компоненты с! разбиения О, на которых для "моделирования" прямых столбцов М достаточно одних переменных, считаются "хорошими" компонентами О.

Вторая глава диссертации посвящена методам построения универсальных матриц и представительных разбиений, а также оптимизации их параметров. Главным критерием оптимальности универсальной матрицы с заданным числом строк является число ее различных столбцов, а главным критерием оптимальности представительного разбиения - доля его хороших компонент.

В § 3 вводится операция горизонтальной (вертикальной) конкатенации матриц одинаковой высоты (соответственно, длины). результат применения которой к матрицам М\. М-г обозначается через Л/! • М-1 (соответственно. М\ о Мч). При этом считается, что

Г-(Д/) = г-(Л/1 )•...• у(Л/5), если М = Л/, •... • Л/5.

а длина каждой матрицы равна числу переменных функции г-

Основное утверждение § 3 - теорема 4. В ней доказывается, что для любой матрицы М" из 0 и 1 с т прямыми столбцами и 27 строками при л > 3т существует представительное для М" разбиение О куба Вя+п, причем доля "плохих" компонент П не больше чем е". где е2 < 1 - некоторая константа. Отметим.

что матрица, строками которой являются наборы произвольной компоненты d указанного разбиения D. имеет вид M'J • ¡.tq, где матрица M'¡ получается из М" путем дублирования и инвертирования столбцов, a fiq - матрица, транспонированная к матрице ¡1,,.

В § 4 изучаются специальные структурные представления для матриц и разбиений, доказываются некоторые вспомогательные утверждения. Рассматриваются, в частности, т.н. геометрические разбиения и оценивается их энтропия. Вводятся т.н. суперматрнцы. т.е. матрицы, элементами которых снова являются матрицы. Для суперматрнцы Л/ определяется ее расширение, т.е. матрица, которая получается в результате сначала горизонтального, а затем вертикального дублирования с помощью операций конкатенации каждой матрицы тп, являющейся элементом Л/, такое число раз, чтобы ее высота (длина) стала равна максимальной высоте (соответственно, длшю) матриц, расположенных в той же строке (соответственно. столбце) суперматрнцы А/. что и т.

В § 5 вводится понятие селекторной матрицы булевской функции, связанной с селекторным разбиением множества переменных этой функции. Селекторное разбиение D переменных функции ¡¿{tji____,yt) определяется тем, что для любой

переменной >j¡. i = 1____,í, в результате подстановки при всех

d. где d - компонента D и d ~í y¡, некоторой булевской константы вместо каждой переменной из d можно получить функцию, тождественно равную либо у,, либо y¡. При этом матрица А/ с í строками и í столбцами, в которой элемент, стоящий на пересеченна i-й строки и j-ro столбца, равен 2,

ГЧ (О

если ij¡ и ijj входят в одну и ту же компоненту и, и равен a¿ , где d - компонента D и щ € d, в остальных случаях, считается селекторной матрицей функции ¡р. связанной с разбиением D. Заметим, что число различных столбцов матрицы М равно числу компонент разбиения D и для матрицы М, которая получается в результате замены всех элементов вида 2 в г-м

столбце Л/ переменной тд, ¡'= 1____справедливо равенство:

/ г/1 ^^ \

9(М)= ••• .

V У( Ф й ,

где ____, - булевские константы.

Селекторная энтропия существенной булевской функции, т.е. функции, существенно зависящей от всех своих переменных. определяется как минимальная энтропия селекторных разбиений множества ее переменных. Основное утверждение § 5 - теорема 5. В ней доказывается, что в классе 5ц для любого I — 1,2.....существует абсолютная формула, т.е. формула. входы которой не разветвляются, построенная из легких элементов Б. имеющая сложность не больше, чем -Ь С5, и реализующая существенную функцию 9, которая зависит не менее, чем от I, переменных, причем селекторная энтропия у не больше, чем +

В § 6 рассматриваются т.н. канонические матрицы, которые составляют специальный класс универсальных матриц, а также специальные (канонические) выборки из множества их столбцов. Каноническая для заданной булевской функции ■ • • * !/г) матрица II получается в результате подстановки вместо каждого элемента вида 2 из ¡-го столбца селекторной для функшш матрицы Л/, связанной с селекторным разбиением В, матрицы /I,., где г = 1,... и эг = в;, если уч и у¡ принадлежат одной и той же компоненте с последующим переходом к расширению соответствующей суперматрицы. Доказывается. что матрица 0' является ¡^-универсальной матрицей. причем любую матрицу ф, высота которой равна высоте С. можно представить в виде <3 = <р(И'"), где IV - каноническая выборка из и. Исследуются возможности минимизации числа различных столбцов у канонической ^-универсальной матрицы при заданном числе ее строк. Из леммы 14 следует, в частности. что для существенной функции .....у<), имеющей

селекторную энтропию Я. при любом натуральном 5 >

можно построить каноническую ^-универсальную матрицу с т.н. приведенной шириной 5, которая имеет не меньше, чем /(•? — Я) строк, и не больше, чем 2*+1, различных столбцов.

Кроме того, в § б предлагается способ "динамического" построения универсальных матриц, который позволяет при реализации выборок из одних универсальных матриц получать на промежуточных выходах столбцы других, более оптимальных универсальных матриц. Пусть функция -ф\ реализуется абсолютной формулой, получающейся в результате подстановки функции со вместо каждой переменной функции фз и пусть {/,-, I 6 {1.2}, - каноническая ^-универсальная матрица, а \У\ -произвольная каноническая выборка столбцов Щ. В теореме б доказывается, что при определенных соотношения между параметрами функций фц, ф] и матриц Ь\, [<2, И'] существует такая матрица II, каждый столбец которой имеет вид Д о 02 > где .3-, - столбец С*;, а число различных столбцов V сравнимо с числом различных столбцов матрицы и такая выборка I!" столбцов С', имеющая вид И" = \\\ о И^, для которой из столбцов матрицы Фо{№?) можно составить каноническую ф?-унпверсальную матрицу с большей приведенной шириной, чем у матрицы II

В третьей главе диссертации исследуется поведение функций Шеннона на уровне оценок высокой степени точности.

В § 7 излагаются методы синтеза ациклических схем из ФПЭ на основе разложений, связанных с универсальными матрицами и представительными разбиениями. При этом в любом из классов построение схемы Е/, реализующей произвольную булевскую функцию /{х\,..., х„)< включает в себя:

1. построение универсальной матрицы С высоты 2' для булевской функции которая реализуется специальной базовой схемой состоящей из легких элементов;

2. построение представительного для матрицы II разбиения £> куба В"~", где а < п - д:

3. разложение функции / сначала по переменным Х[,____ха,

а затем по всем компонентам разбиения D куба Вп~а от остальных переменных:

4. моделирование функции / на каждой компоненте d разбиения В" х D куба В" с помощью схемы Е^", которая получается в результате инвертирования отдельных прямых входов у схемы Е^,. причем Е^' = Е^, если d соответствует "хорошей" компоненте D, путем присоединения прямых входов Е^1 к некоторым входным переменным / и реализации на итеративных входах Е^ некоторых столбцовых функций матрицы U;

•5. "сборка" схемы Е/ из схем Е^ и вспомогательных схем, которые реализуют систему столбцовых функций матрицы U, систему характеристических функций компонент D и 2"~ч~" раз - систему элементарных конъюнкций от переменных Г|____,г„.

С о

Отметим, что q + а = п в случае Е G 5Б' и q = 0 в случае Е € что основная сложность схемы Е/ приходится на ее базовые подсхемы Е^ и что сборка схемы Е/, а также синтез вспомогательных схем осуществляются с помощью простейших методов синтеза, связанных с моделированием совершенной ДНФ и контактного дерева. Заметим, что метод Шеннона для синтеза контактных схем2, метод О. Б. Лупанова для синтеза схем из функциональных элементов в базисе {&:. V, ->} (см.. напр., w). а также метод синтеза схем в базисе из элементов .к. V, -1 и элемента голосования18могут рассматриваться как частные случаи предлагаемого общего метода. Этот метод и связанные с ним оценки сложности схем изложены в

17Лупанов О.Б. Асимптотические оценки сложности управляющих систем.- М.:1Ьд-во Моск. ун-та, 19S4.

"ЯблонскиН C.B. Асимптотически наилучший метод синтеза надежных схем m ненадежных элементов // Banach Center Pub.- 19S2.- N 7,- P. 11-19.

лемме 19, с помощью которой в теореме 7 получаются необходимые верхние оценки для функций Шеннона LÎ{n), X"A(n), LCAn).

С 1

Для синтеза схемы S/ в классе 5Б' , рассмотренное выше представление функции / применяется сначала к области V\ куба В", где используется матрица £Д и базовые схемы а затем к области Г>2, V2 = В" \ Т>ь где используется матрица i~2 и базовые схемы При этом в соответствии с теоремой б на промежуточных выходах базовых схем Е^, реализуются столбцовые функции матрицы Щ. Указанным способом в теореме 8 устанавливаются требуемые верхние оценки для функции Шеннона

В § 8 на основе мощностных соображений, учитывающих специфику того или иного класса схем. устанавливаются нижние оценки функций Шеннона.

§ 3 Публикации по теме диссертации

1. Ложкин С.А. О поведении функции Шеннона для глубины булевских функций в некоторых базисах.// V Всесоюзная конференция по проблемам теоретической-кибернетики. 1980 - Новосибирск. 1980.- С. 69-70.

2. Ложкин С.А. О связи между глубиной и сложностью формул и о глубине монотонных функций алгебры логики.// Проблемы кибернетики. Вып. 38-М.:Наука,1981.-С. 269271.

3. Ложкин С.А. О глубине функций алгебры логики в некоторых базисах // Annales Univ. Budapest. Sectio Computa-torica - 1983.- Tomus IV.- P. 113-125.

4. Ложкин С.А. О синтезе ориентированных контактных схем// Вестник МГУ. Вычислительная математика и кибернетика,- 1995 - N 2,- С.36-42.

5. Ложкин С.А. Новые, более точные оценки функций Шеннона для сложности управляющих систем.// Дискретный анализ и исследование операций,- 1995.-х 2, N З.-С. 7778.

6. Ложкин С.А. О синтезе некоторых типов схем на основе сдвиговых разбиений, порожденных универсальными матрицами.// Вестник МГУ. Вычислительная математика и кибернетика - 1996, N 1,- С. 62-69.

7. Ложкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов.- М.,1996.-(Препр./ ИПМ РАН; N 36).

8. Ложкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов.// Проблемы теоретической кибернетики.- Тезисы докладов XI Международной конференции 10-14 июня 1996 г.- М., 1996 - С. 123-125.

9. Ложкин С.А. О сложности реализации функций ¿-значной логики формулами и квазиформуламн.// Проблемы теоретической кибернетики.- Тезисы докладов XI Междуна- • родной конференции 10-14 июня 1996 г.- М., 1996.- С. 125127.

10. Ложкин С.А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов.// Математические вопросы кибернетики, Вып. 6.- М.:Наука. 1996.- С. 189-214.

11. Ложкин С.А. О глубине функций алгебры логики в произвольном полном базисе.// Вестник МГУ. Математика, механика.- 1996 - N 2,- С. 80-82.