Синтез схем контактного типа с ограничениями на смежные контакты тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

московский государственный университет имени М. В. Ломоносова

На правах рукописи

Шиганов Александр Евгеньевич

Синтез схем контактного типа

с ограничениями на смежные контакты

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

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

0046061

Москва - 2010

004606113

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

Научный руководитель:

Официальные оппоненты:

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

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

доктор физико-математических наук, профессор механико-математического факультета МГУ имени М. В. Ломоносова Редькин Николай Петрович

кандидат физико-математических наук, старший научный сотрудник Института системных исследований РАН Кузнецов Юрий Владимирович

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

Институт системного анализа РАН

Защита диссертации состоится 18 июня 2010 г. в И час. 00 мин. на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М. В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет вычислительной математики и кибернетики, ауд. 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ имени М. В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.su в разделе «Наука» — «Работа диссертационных советов» — «Д 501.001.44».

Автореферат разослан мая 2010 г.

1 Ученый секретарь

диссертационного совета Д 501.001.44 АХ//гМ^^^У

профессор ^ ' Трифонов Н. П.

•1г. О. -уЛл /^-г^в^о^

АуО-Еу . Л е-/ 1°. Ж*.

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

Актуальность темы. Задача синтеза управляющих систем является одной из основных задач кибернетики. Она состоит в построении для заданной системы булевых функций реализующей ее схемы, принадлежащей заданному классу и являющейся оптимальной по какому-либо критерию. Чаще всего в качестве такого критерия выступает сложность схемы, понимаемая как сумма сложностей составляющих её элементов. В диссертации рассматривается задача массового синтеза, которая заключается в изучении асимптотического поведения так называемой функции Шеннона L{n) от натурального аргумента п. равной сложности реализации самой «трудной» булевой функции от п переменных с помощью схем из заданного класса.

Среди различных моделей дискретных управляющих систем можно выделить модели схем «проводящего» или «контактного» типа, в которых реализация булевых функций осуществляется с помощью передачи сигналов по ребрам (дугам) графа схемы, называемым контактами. При этом проводимостью контактов «управляют» внешние или специальные внутренние булевы переменные.

Задача массового синтеза для класса контактных схем была впервые поставлена в работе Шеннона1, в которой им был установлен порядок функции L(n), связанной со сложностью контактных схем. где под сложностью понималось общее число контактов схемы. Асимптотически оптимальный метод синтеза контактных схем был разработан О. Б. Лупановым2. Им же были установлены асимптотические значения функций Шеннона, связанных с реализацией булевых функций во всех основных классах схем (классе схем из функциональных элементов, классе формул, классе контактных и релейно-контактных схем и др.)2 3 45.

'Shannon С. Е. The synthesis of two-terminal switching circuits. Bell Syst. Techn. J., 1949, v. 28, N-l, pp. 59-08.

2 Лу nan ob О. Б. О синтезе контактных схем // ДАН СССР. - 1958. - Т. 119, № 1. - С. 2J-26.

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

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

5Лупанов О. Б. О сложности реализации функций алгебры логики релейно-контактньши схемами // Проблемы кибернетики. Вып. 11. - М.: Наука, 1964. - С. 25-48.

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

Так, например, О. Б. Лупанов получил6 асимптотику функции Шеннона, связанной со сложностью схем из функциональных элементов, в которых выход любого элемента может соединятся не более, чем с заданным числом входов других элементов. А. Д. Коршунов разработал7 асимптотически оптимальный метод синтеза контактных схем, в которых степени вершин ограничены некоторой константой. Отметим, что подобные ограничения позволяют, в том числе, учитывать ограниченную ёмкость физических элементов схем.

Модели схем контактного типа являются удобными математическими моделями интегральных схем на дополняющих МОП-транзисторах (КМОП-схем)8. При этом, обычно, контакт с пометкой х? соответствует п-МОП или р-МОП транзистору, на затвор которого подаётся значение а контактная схема описывает соединения между истоками и стоками транзисторов. Известна8 асимптотика функции Шеннона, связанной со сложностью КМОП-схем, для случая, когда контакты разрешается помечать только символами «внешних» булевых переменных. Этот случай соответствует моделированию КМОП-схем с помощью контактных схем. Если также допускается использование в качестве пометок контактов специальных «внутренних» булевых переменных, реализуемых в вершинах схемы, то возможно получение асимптотически в два раза более эффективной реализации булевых функций9. Этот случай, фактически, соответствует моделированию КМОП-схем с помощью итеративных

6Лупанов О. Б. Об одном классе схем из функциональных элементов (формулы с конечной памятью) // Проблемы кибернетики. 1962. Вып. 7. С. 61-114.

7Коршунов А. Д. Об асимптотических оценках сложности контактных схем заданной степени // Дискретный анализ. Сб. науч. тр. Вып. 5. Новосибирск: Ип-т математики СО АН СССР, 1965. С. 35-63.

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

9Касим-Заде О. М. О сложности реализации булевых функций в одной модели электронных схем //' Математические вопросы кибернетики. Вып. 2. М.: Наука, 1989. С. 145-160.

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

К классу схем контактного тина можно также отнести впервые предложенный Ли11 класс двоичных решающих диаграмм (Binary Decision Diagrams, BDDs), активно изучаемый в настоящее время и применяемый, в том числе, для «программной» реализации булевых функции. Асимптотика функции Шеннона для сложности BDD установлена В. А. Кузьминым12.

Наряду с моделями схем с «жёсткими» структурными ограничениями, в литературе также рассматриваются модели, в которых допускается наличие незначительного числа «нарушений» ограничений. Так. A.A. Никитин получил13 асимптотику функции Шеннона для сложности схем из функциональных элементов и элементов задержки, в которых допускались ветвления выходов только элементов задержки, причём максимальное количество «ветвящихся» элементов задержки в схеме было ограничено.

Важным направлением теории синтеза является получение для функций Шеннона оценок высокой степени точности, то есть таких оценок некоторой функции Шеннона L(n), имеющей порядок роста 2п/п, относительная погрешность которых имеет вид 0(1/п). Заметим, что указанные оценки, по сути, устанавливают значение первого остаточного члена асимптотического разложения соответствующей функции Шеннона. Методы получения оценок высокой степени точности разработаны С. А. Ложкиным1014. В своих работах С. А. Ложкин получил оценки высокой степени точности для сложности основных классов схем, в том числе ориентированных контактных схем и итеративных контактных схем.

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

uLee С. Y. Representation of switching circuits by binary-decision programs. Bell. Sys. Tech. J., vol. 38, 1959. - pp. 985-999.

1гКузьмин В. А. Оценка сложности реализации булевых функций программами простого типа. // Методы Дискретного анализа, 29, 1976. - С. 11-39.

13Ннкитин А. А. О сложности реализации функций алгебры логики в некоторых классах автоматных схем /'/ Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 1999. № 3. С. 41-49.

14Ложкин С. А. Асимптотические оценки высокой степени точности для сложности управляющих систем. Диссертация на соискание ученой степени доктора физ.-матем. наук. Москва. 1997.

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

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

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

Теоретическая и практическая ценность. Работа носит теоретический характер. Методы синтеза, разработанные в диссертации, могут, по мнению автора, быть применены при решении задач синтеза различных видов схем контактного типа, в том числе, КМОП-схем.

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

Публикации и апробирование. По теме диссертации опубликовано 7 печатных работ [1-7], из которых статьи [5,6] - в изданиях, рекомендованных ВАК. Результаты диссертации докладывались на семинарах кафедры математической кибернетики факультета ВМК МГУ, а также на семинаре ка-

федры дискретной математики механико-математического факультета МГУ и, кроме того, докладывались и обсуждались на следующих конференциях и семинарах:

1. XV международная конференция «Проблемы теоретической кибернетики» (Казань, 2-7 июня 2008);

2. XVII международная школа-семинар «Синтез и сложность управляющих систем» (Новосибирск, 27 октября - 1 ноября 2008);

3. XVIII международная научная конференция «Дискретные модели в теории управляющих систем» (Москва, 6-9 апреля 2009);

4. X международный семинар «Дискретная математика и её приложения» (Москва, 1-6 февраля 2010).

Структура и объем диссертации. Диссертация состоит из введения, четырёх глав и списка литературы. Текст изложен на 124 страницах, диссертация содержит 14 рисунков. Список литературы включает 33 наименования.

Краткое содержание работы

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

В диссертации изучаются следующие классы схем.

1. Класс Ыокс всех ориентированных контактных схем (ОКС), то есть контактных схем из ориентированных контактов, проводящих только в соответствующем направлении.

2. Класс ц(Х1/)-окс всех ОКС, в которых из каждой вершины исходит не более Л дуг и для каждой вершины среди пометок исходящих из неё дуг встречается не более, чем V, различных переменных.

3. Класс ивво двоичных решающих диаграмм (ВБО), причём под ВЭЭ от переменных х\..... хп в диссертации понимается произвольная ациклическая схема Б из класса ¿^2,1)"окс, граф которой содержит два стока, помеченных 0 и 1 и являющихся выходами схемы, один или несколько

истоков, являющихся входами схемы, а из каждой вершины £. отличной от выходов исходит пара противоположных контактов вида х,• и х^ где 1 ^ г ^ п.

4. Класс ик'ошю (цк-501Ю°') упорядоченных (строго) ¿-считывающих двоичных решающих диаграмм, то есть схем £ из класса Ывт, в которых произвольная простая цепь из входа в выход Е разбивается на к сегментов. таких, что па каждом сегменте переменные встречаются в порядке, одинаковом для всех сегментов и указанных цепей, и при этом на каждом сегменте каждая входная переменная £ встречается не более одного раза (соответственно в точности один раз).

5. Класс и"КС всех итеративных контактных схем (ИКС), где под итеративной контактной схемой понимается схема £', полученная из некоторой контактной схемы £, имеющей один вход и т выходов Ь\,... ,Ьт и зависящей от переменных х\,...,хп, в результате применения операции присоединения различных переменных х^,..., Х{к к различным выходам Ь^...., Ь^ соответственно. При этом накладывается ограничение, связанное с тем, что переменные х^, ■ ■ ■ ,Хц входят в схему £ без отрицаний, а функции, реализуемые в выходах ¿>^,...,6^, не зависят существенно от переменных х^,... .х^.

Пусть схема £ принадлежит одному из введённых классов схем, тогда под сложностью Ь(£) схемы £ понимается число контактов в £. Далее, если схема £ является ОКС или ЕЮЭ, то для фиксированных положительных действительных чисел и/ и и>", где у/' > и/. дополнительно определим вес схемы £, как сумму весов вершин £, причём вес истока и вер-

шины с одной входящей дугой равен и/, а все остальные вершины имеют вес т".

Для булевой функции / в диссертации определяются следующие функционалы сложности:

1. Величина ЬЛ(/), где иА - один из введенных классов схем, равна минимуму сложностей £(£), где минимум берётся по множеству всех схем £ из класса ЫА, реализующих /.

2. Величина где 1АЛ - один из введённых классов ОКС или ВВО, равна минимуму весов И/„/.и/'(£), где минимум берётся по множеству

всех схем £ из класса ЫА. реализующих /.

3. Величина ¿л(/, £), где £ - натуральное, а ЫА - один из введенных классов ОКС или ВБО, равна минимуму сложностей £(£), где минимум берётся по множеству всех схем £ из класса иА, реализующих /, таких. что схема £ содержит не более I вершин, в которые заходит более одной дуги.

4. Величина Ь°кс(/) (соответственно ¿"кс(/)) равна минимуму сложностей Ь(£), где минимум берётся по множеству всех ОКС (соответственно ИКС) £, реализующих /, таких, что степень вершин Е ограничена константой Л.

Для натурального п функции Шеннона вида ЬА{п), И^, и,„(п), Ьл(п, £) и ЬА(п) традиционно определяются, как максимум величин ЬА(/), №А, ЬА(/: £) и ЬА(/) соответственно, где максимум берётся по множеству булевых функций / от п переменных.

В первой главе вводится ряд определений и утверждений, используемых в диссертации при описании методов синтеза схем.

Разбиение й множества переменных булевой функции '■р(у1, ■ ■ ■ ,Уг) называется селекторным, если для каждой переменной у из произвольной компоненты V разбиения Ю можно подобрать набор булевых констант а. такой, что переменные из одной компоненты разбиения О принимают на наборе а одинаковые значения и что после подстановки в функцию ¡р констант набора а на места всех переменных, за исключением переменных компоненты У, функция у совпадает с у или у.

В §1.1 диссертации формулируются леммы 1.1 и 1.2, в которых описаны способы получения «хороших» селекторных разбиений при суперпозициях булевых функций. Формулировки леммы 1.2 в различных вариантах встречаются у С. А. Ложкина1014, а сама лемма 1.2 доказывается с использованием леммы 1.1, являющейся, по сути, более сильным утверждением. С содержательной точки зрения лемма 1.1 позволяет упростить процесс получения селекторных разбиений, сводя его к проверке некоторых свойств функций, участвующих в суперпозиции.

В §1.2 вводится понятие у-универсального множества функций порядка т. то есть такого множества функций С от переменных х\,..., хт, что

для любой функции д(хь ..., хт) в множестве С? найдутся функции, которые можно подставить в функцию так, что полученная в результате суперпозиции функция совпадает с д. Главным критерием «качества» универсального множества является число функций в нём. В лемме 1.5 утверждается возможность построения «эффективного» ^-универсального множества при наличии подходящего селекторного разбиения функции <р.

Некоторые вопросы суперпозиции ОКС изложены в §1.3. Там же вводятся вспомогательные классы схем, с помощью которых удобно описывать построение упорядоченных (строго) ^-считывающих ВОВ, и приводятся простейшие методы синтеза ОКС. В лемме 1.7 даётся оценка сложности реализации булевой функции посредством моделирования её совершенной ДНФ с использованием контактного дерева. В лемме 1.8 приводится оценка сложности реализации системы булевых функций с помощью одного шага разложения по методу каскадов, после чего остаточные функции реализуются по лемме 1.7.

Во второй главе диссертации описывается метод синтеза ОКС и ВБИ с близким к оптимальному значением веса, а также близким к оптимальному значением сложности при наличии ограничения на число вершин, в которые заходит более одной дуги, для почти всех функций.

В §2.1 изучаются вопросы реализации схемами из класса ¿/(А-1/)-°кс ряда вспомогательных функций, для которых можно «эффективно» строить универсальные множества. Отдельно рассматриваются два случая: случай V — А и случай и < Л. В обоих случаях указанные функции получаются в результате многократной суперпозиции некоторых базисных функций, причём множество переменных базисных функций условно разделяется на множество прямых и множество итеративных переменных, а при суперпозиции базисных фЗ'нкций подстановка одних функций осуществляется на места итеративных переменных других функций. Для получения необходимых селекторных разбиений при суперпозиции функций в случае V = А используется лемма 1.2, а в случае и < А - лемма 2.3, вытекающая из леммы 1.1.

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

функцию / от переменных х\.... ,хп, включает в себя:

1. построение специальной схемы Е1)3. реализующей вспомогательную булеву функцию <р, и построение ^-универсального множества й порядка тп, где тл < щ

2. построение специального разбиения Л множества наборов (/-мерного единичного куба, где тп < д < п, от переменных х\,... .хч, такого, что функции из множества б", где С С «моделируются» указанными переменными или их отрицаниями на компонентах разбиения Д;

3. моделирование значений каждой функции вида

где о^+ь... ,сгп - булевы константы, на каждой компоненте разбиения Д с помощью суперпозиции схемы Е^, и схемы Ее, реализующей систему С" = С\С.

4. «сборка» схемы Е/, реализующей /, из схем, построенных в п.З, на основе разложения / по переменным ..., хп.

Метод синтеза схем класса Ц(хр)-окс приводится в теореме 2.1. Метод синтеза упорядоченных (строго) &-считывающих, где к > 2, двоичных решающих диаграмм описан в теореме 2.2 (соответственно теореме 2.3) и представляет собой, но сути, незначительную модификацию метода синтеза схем класса и^-ОКС.

В §2.3 доказываются верхние оценки числа схем определённого вида из классов ОКС и ВБЭ, которые затем используются при получении мощност-ных неравенств для доказательства нижних оценок функций Шеннона, связанных с классами ОКС и ВБО и различными функционалами сложности схем.

Из результатов §2.2 и §2.3 вытекают теоремы 1-4, сформулированные во введении диссертации.

Теорема 1. Для любых натуральных А и V, где А ^ 2 и 1 ^ и ^ Л, а также положительных вещественных величин ги' и и)", где и)" > и/,

при п = 1,2,... справедливо15

Теорема 2. Для любого натурального к ^ 2, а также положительных вещественных выичин ги' и и>", где ю" > к/, при п — 1.2,... справедливо

_ Л , 1о8п±0(1)

= I 1 +

п

п \ п J

Теорема 3. Для любых натуральных А и v, где А ^ 2 и 1 ^ 1/ ^ А, при п = 1,2,... ut = t(n), где16 log f(n) = u t(n) не превосходит 2 ™/n2, справедливо

ЬМ-окс{ *) = , , 2" - f 1 ± о f-

v ' A - 1 logi + xTjlogn V vn

Теорема 4. Для любого натурального k ^ 2 при п = 1,2,... и i = i(n), где t(n) —> оо при п —» оо и t(n) не превосходит 2п/п2, справедливо

Lk'soriDD(n,t) = ±0

к ' ' logí V \>g

Jogi

и eo/iu, кроме того, logí(n) = Q(n), то

15Равеиство r(n) = р(п)±0(д(п)) означает, что jr(ra) —р(п)| = ^(^(п)). В данной работе основание 2 у логарифмов опускается.

16Равенство р(тг) = ft(q(n)) означает, что р(п) = 0{q{n)) и q(n) = 0(р(п)).

В §2.3 также установлено, что если в определении веса И^щ^Е) ОКС Е учитывать с весом ги" вершины, в которые заходит более в, дуг. где с? - натуральная константа, а все остальные вершины учитывать с весом и/, то асимптотика функций Шеннона но-прежнему составляет 2Л/п для класса ¿/(Л.")-°кс и и/2п/п для классов ВБО соответственно.

В третьей главе диссертации приводятся методы синтеза схем из класса

^(ЛЛ)-окс

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

1. разбиение множества наборов п-мерного единичного куба на два подмножества Ах и А2, причём является гц-меркым единичным кубом, где щ < п, а А2 = {0,

2. построение специальных схем Е^,, и реализующих вспомогательные булевы функции <р\ и щ соответственно;

3. построение множества функций такого, что на наборах каждого из множеств А1 и Л2 функции из С совпадают с функциями некоторых (¿^-универсальных множеств, а на наборах множества А2 на промежуточных входах схем определённым образом соединённых со схемой Е", реализующей часть функций из <7. реализуются функции некоторого (¿^-универсального множества;

4. построение для i = 1,2 специального разбиения А^ множества наборов Аг, такого, что некоторые функции системы С можно «промоделировать» переменными или их отрицаниями на компонентах разбиения Д,-;

5. моделирование значений функции / на каждой компоненте разбиения Д1 с помощью суперпозиции схемы Е(?1 и схемы Е";

6. моделирование значений функции / на каждой компоненте разбиения Дг с помощью суперпозиции схем и промежуточных входов схем, построенных в п.5;

7. «сборка» схем, построенных в пп.5-6 в схему Е/, реализующую /.

Метод синтеза схем класса ¿/(л-л>-°кс приводится при доказательстве теоремы 3.1, а метод синтеза упорядоченных /с-считывающих, где к ^ 4, двоичных решающих диаграмм - при доказательстве теоремы 3.2. В §3.2 также

делается замечание к теореме 3.1 об одном свойстве схемы £/, построенной при доказательстве этой теоремы. В замечании приводится оценка суммарной полустепени захода тех вершин схемы £/, в которые заходит более одной Дуги.

Из теорем 3.1 и 3.2, из соотношений между классами схем ц(2'1)-°кс _ цк-овэ^ а также из нижних оценок функций Шеннона, доказанных в §2.3, вытекают теоремы 5 и 6, сформулированные во введении диссертации.

Теорема 5. Для любых натуральных X и и, где X ^ 2 и \ ^ V < при п = 1,2,... справедлива нижняя оценка

А - 1 п V п I

а также в случае V = 1, \ = 2 ив случае V = А при п= 1,2.... справедлива верхняя оценка

ьМ-окс(п) ^ . ^ Л + ^1оёп + 1оё1оЕп + 0(1)\

А — 1 п ( п I

Теорема 6. Для любого натурального к ^ 4 при п = 1,2.... справедливы оценки

2п+1 Л „ А\\ . ,„пп, ч - 2"+1

п

\п)) п \ п

271+1 '1 - О (!Уи I*™(п) г—(г + 1оё1оё" + 0(1)

п \ \п)) п \ п

Четвёртая глава диссертации посвящена методам синтеза итеративных контактных схем и ориентированных контактных схем с ограничением на степени вершин.

Построения для класса итеративных контактных схем приводятся в п. 4-1.1. В нём описывается подход А. Д. Коршунова7 к построению контактных схем с ограниченной степенью вершин для функций вида уа где а 6 {0,1}, если известна контактная схема для функции /. Этот подход сформулирован в лемме 4.2 и сводится к добавлению в схему для / необходимого количества

контактов вида у". Также в п. ЬЛЛ формулируется следствие из теоремы Холла, которое заключается в том, что в двудольном графе, таком, что степень вершин одной доли равна в., а степень вершин второй доли не превосходит <1, существует паросочетание. насыщающее вершины первой доли.

Построение итеративной контактной схемы, реализующей заданную булеву функцию / от переменных х{,...,х„ п имеющую вершины степени не более Л, происходит следующим образом. Функция / представляется в виде / = хп/о VI»/!. где /7 = /(х1,.... хп-1,7), 7 е {0,1}. Для 7 = 0,1 строится схема Е/ , реализующая функцию /7, из которой с использованием леммы 4.2 получается схема Е'д, реализующая функцию хЦ^ с вершинами степени не более Л. Схема Е/, реализующая /, получается в результате параллельного соединения схем £^о и Е^. Метод синтеза схемы £д, 7 б {0,1}, включает в себя:

1. построение специальной схемы реализующей вспомогательную булеву функцию 1р. и построение ^-универсального множества (7 порядка т, гдетп < (п—1), причём множество С имеет вид С = С^С^иСз, а его функции зависят от переменных Х[,.... хт;

2. построение схемы реализующей функции множества г = 1,2,3;

3. построение по функции /7 специальных двудольных графов и получение по следствию из теоремы Холла в каждом из графов паросочетания, насыщающего вершины одной из долей;

4. присоединение схем Спредставляющих собой цепочки контактов, к выходам схемы £1;

5. выбор в соответствии с правилами, определяемыми построенными па-росочетаннями, для каждого контакта схем С\,..., С^ функции из системы Сг для «управления» указанным контактом;

6. реализация каждой функции вида

/у(х1- ..., хт% ..., СГП_1),

где стт+1,.. .,<т„_1 - булевы константы, с помощью суперпозиции схемы и некоторых выходов цепочек Су.... ,Ск, причём контакты схемы «управляются» функциями системы 63;

7. «сборка» схемы £д из схем, построенных в п.6, на основе разложения

/7 по переменным хт+1,.... Метод синтеза ориентированных контактных схем, имеющих вершины степени не более Л, излагается в п. 4.1.2 и заключается в незначительной модификации схемы из класса построенной при доказатель-

стве теоремы 3.1 с учётом замечания к ней.

Из результатов §4-1 и §4-2 вытекают теоремы 7 и 8, сформулированные во введении диссертации.

Теорема 7. Для любого натурального А ^ 3 при п = 1,2,... справедливы оценки

1П„,« . 2 Л + -Аье,,-иоею8п + о(1Л

Л 2 и V ть I

Теорема 8. Для любого натурального А ^ 3 при п = 1,2,... справедливы оценки

Заметим, что нижние оценки функций Шеннона, приведённые в теоремах 1-8, справедливы для сложности (относительно соответствующих функционалов) почти всех функций от п переменных.

Основные результаты работы

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

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

Шеннона, связанных с введёнными функционалами сложности указанных схем.

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

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

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

[1] Шиганов А. Е. Асимптотические оценки высокой степени точности для сложности схем из некоторых классов // Сборник тезисов лучших дипломных работ 2006 года. - М.: Издательский отдел фак-та ВМиК, 2006, С. 73-74

[2] Шиганов А. Е. О сложности ориентированных контактных схем с ограниченной полустепенью исхода // Проблемы теоретической кибернетики. Тезисы докл. XV Международной конф. Казань: Отечество, 2008. С. 133.

[3] Шиганов А. Е. О сложности ориентированных контактных схем с весовыми и структурными ограничениями // Материалы XVII Международной школы-семинара "Синтез и сложность управляющих систем"имени академика О. Б. Лупанова (Новосибирск, 27 октября - 1 ноября 2008 г.) - Новосибирск: Издательство Института математики СО РАН, 2008, С. 190— 192.

[4] Ложкин С. А., Шиганов А. Е. О синтезе ориентированных и итеративных контактных схем заданной степени // Труды VIII Международной конференции "Дискретные модели в теории управляющих систем"(Москва, 6-9 апреля 2009 г.). - М.: Издательский отдел факультета ВМиК МГУ, 2009.-С. 201-203.

[5] Шиганов А. Е. О синтезе ориентированных контактных схем с некоторыми ограничениями на смежные контакты // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2009. №3. С. 46-52.

[6] Шиганов А. Е. О сложности ориентированных контактных схем с ограниченной полустепенью исхода // Учен. зап. Казан, ун-та. Сер. Физ.-матем. науки. - 2009. - Т. 151, кн. 2 - С. 164-172.

[7] Ложкин С. А., Шиганов А. Е. Некоторые оценки сложности ориентированных контактных схем с ограниченной полустепенью исхода // Материалы X Международного семинара "Дискретная математика и её приложения "(Москва, МГУ, 1-6 февраля 2010 г.). - М.: Изд-во механико-математического факультета МГУ, 2010. - С. 122-123.

Подписано в печать 18.05.2010 Формат 60x88 1/16. Объем 1 п.л. Тираж 100 экз. Заказ № 1005 Отпечатано в ООО «Соцветие красок» 119991 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. А-102

Введение

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

Основные определения и формулировка полученных результатов

Глава 1. Представление функций на основе специальных универсальных множеств. Некоторые вопросы суперпозиции схем

§ 1.1. Селекторные разбиения множества переменных булевых функций

§ 1.2. Универсальные множества функций и способы их построения

§ 1.3. Некоторые вопросы суперпозиции и синтеза ориентированных контактных схем

Глава 2. Синтез оптимальных по весу ориентированных контактных схем с ограниченной полустепенью исхода

§ 2.1. Построение универсальных множеств для некоторых функций

§ 2.2. Синтез ориентированных контактных схем на основе регулярных разбиений единичного куба и универсальных множеств функций.

§ 2.3. Оценки числа схем из некоторых классов ориентированных контактных схем.

Глава 3. Синтез оптимальных по сложности ориентированных контактных схем с ограниченной полустепенью исхода

§ 3.1. Некоторые сведения из теории полислов.

§ 3.2. Верхние оценки сложности ориентированных контактных схем с ограниченной полустепенью исхода.

Глава 4. Синтез оптимальных по сложности ориентированных и итеративных контактных схем с ограниченной степенью

§ 4.1. Верхние оценки сложности схем с ограниченной степенью

4.1.1. Синтез итеративных контактных схем.

4.1.2. Синтез ориентированных контактных схем.

§ 4.2. Нижние мощностные оценки функций Шеннона.

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

Теория дискретных управляющих систем является важным разделом дискретной математики и математической кибернетики [16,24,33]. Она занимается изучением математических моделей дискретных преобразователей информации, то есть устройств, осуществляющих требуемое преобразование наборов входных значений в выходные. К числу примеров подобных устройств относятся различные виды интегральных схем.

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

Одна из основных задач теории управляющих систем - задача синтеза, -состоит в построении для заданной системы функций F реализующей её схемы Е из заданного класса, на которой достигается оптимальное значение заданного «"показателя» эффективности. В качестве показателя эффективности традиционно используется функционал L, который ставит в соответствие каждой схеме Е из заданного класса некоторое неотрицательное действительное число Ь(Е), называемое её сложностью. Решение задачи синтеза для системы функций F состоит в нахождении схемы Е, обладающей минимальной сложностью среди всех схем из заданного класса, реализующих F.

Понятие полноты заданного класса управляющих систем означает, что схемами из этого класса можно реализовать любую булеву функцию. В этом случае можно определить сложность произвольной булевой функции, как минимальную сложность схемы, которая ее реализует. В теории дискретных управляющих систем рассматривается асимптотическая постановка задачи синтеза, которая была впервые предложена К. Шенноном [3]. В этой постановке вводится функция Ь{п) от натурального аргумента п, названная впоследствии функцией Шеннона, которая равна максимальной сложности булевой функции от п переменных при ее реализации схемами из заданного класса. Таким образом, Ь{п) характеризует сложность реализации самой «трудной» функции от п переменных в заданном классе схем. Далее изучается поведение функции L(n) при растущих значениях п.

В работе [3] был установлен порядок 271/п функции Шеннона LKC(n), связанной со сложностью контактных схем, где под сложностью понималось общее число контактов схемы. Асимптотическое значение 2п/п этой функции Шеннона было позже получено О. Б. Лупановым [19]. Изучение основных классов схем продолжилось в работах О. Б. Лупанова [20,21,23], где им была установлена асимптотика функций Шеннона, связанных с классом релейно-контактных схем, классом схем из функциональных элементов и формул над произвольным полным конечным базисом.

Среди различных моделей дискретных управляющих систем можно выделить классы систем «преобразующего» («функционального») и «проводящего» («контактного») типов. В системах «преобразующего» или «функционального» типа схемы обычно строятся по определенным правилам из элементов априорно заданного базиса. Каждый элемент базиса реализует некоторую булеву функцию (базисную функцию) и обладает определенной сложностью. Граф схемы задает последовательность операций суперпозиции базисных функций. Примерами управляющих систем «преобразующего» типа являются класс схем из функциональных элементов и класс формул, построенных из элементов конечного полного базиса (см., например, [33]) и др. При реализации булевых функций схемами из перечисленных моделей учитываются такие меры сложности, как общее число элементов в схеме, сумма сложностей элементов, из которых состоит схема, задержка или время срабатывания схемы, площадь (объем) геометрической реализации схемы на плоскости (в пространстве) и т.д.

В управляющих системах «проводящего» или «контактного» типа реализация булевых функций осуществляется с помощью передачи сигналов по ребрам (дугам) графа схемы, называемых контактами. При этом проводимостью контактов «управляют» внешние или специальные внутренние булевы переменные. К системам «контактного» типа относятся класс контактных схем [20], класс релейно-контактных схем [23] и др.

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

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

Напомним, что функция Шеннона для сложности схем из функциональных элементов над произвольным полным конечным базисом Б асимптотически равна рБ2п/п, где рв - некоторая константа, зависящая от базиса Б [20]. Класс формул [21] над базисом Б является частным случаем класса схем из функциональных элементов, в которых выход любого элемента может быть соединен только с одним входом другого элемента. В работе [21] О. Б. Лу-паповым была установлена асимптотика1 рв2п/ log п функции Шеннона для сложности формул над базисом Б. Таким образом, введение «жёстких» ограничений на,структуру схемы повлияло на порядок функции Шеннона. В работе [22] О. Б. Лупанов изучал класс схем из функциональных элементов над базисом Б, являющийся промежуточным между классом схем без ограничений [20] и классом формул [21]. В нем выход любого элемента мог соединятся не более, чем с d входами других элементов, где d - константа. Было установлено, что при определенных соотношениях на величину d, а также сложность и число входов элементов базиса Б, асимптотика соответствующей функции Шеннона по-прежнему составляет рв2п/п.

Класс параллельно-последовательных схем (тг-схем) (см., например, [24]) -частный случай класса контактных схем, допускающих, в частности, геомет

ХВ данной работе основание 2 у логарифмов опускается. рическую реализацию на плоскости. Воспользовавшись соответствием между 7Г-схемами и формулами над базисом {&;, V, ->}, в которых знаки отрицания встречаются лишь над символами переменных, а также методом синтеза [21], можно получить асимптотическое значение 2П/ logn функции Шеннона L"(n), связанной со сложностью булевых функций в классе 7г-схем (см. также [24]).

В работе [7] А. Д. Коршуновым было изучено асимптотическое поведение функций Шеннона L^c(n) и LJ(n), связанных со сложностью реализации булевых функций контактными схемами и 7г-схемами соответственно с ограничением Л на степени вершин схем. При А ^ 3 была установлена асимптотика функции Шеннона L*c(ri) вида д^271/п, а для функции Шеннона Щ(п) было доказано, что при любом А ^ 3 она асимптотически равна 2П/ log п.

Представление булевых функций с помощью двоичных решающих диаграмм (Binary Decision Diagrams, BDD) было впервые предложено в [1]. Отметим, что BDD можно рассматривать, как ориентированную контактную схему с одним истоком, являющимся входом, и двумя стоками, являющимися выходами, в графе которой отсутствуют ориентированные циклы и из каждой вершины, отличной от выходов, исходят две дуги с противоположными пометками вида a^afj. Под размером BDD понимается количество вершин BDD, отличных от выходов. В другой интерпретации [8], BDD можно рассматривать как программу, состоящую из операторов условного перехода, не содержащую циклов и имеющую две точки останова 0 и 1. В каждом операторе условного перехода вычисляется значение одной из входных булевых переменных и в зависимости от вычисленного значения осуществляется переход либо в другой оператор программы, либо в одну из точек останова. Результат работы программы на заданном наборе переменных определяется той точкой останова, в которую приведет последовательность операторов перехода (путь вычисления). Под размером программы понимается количество содержащихся в ней операторов. В работе [1] была получена нижняя асимптотическая оценка 2п~1/п и верхняя асимптотическая оценка 2п+2/п для функции Шеннона 5BDD(n), связанной с реализацией булевых функций в классе BDD. Позднее в [8] для этой функции была установлена асимптотика 2 п/п.

Отметим, что для получения верхней оценки функции Шеннона, связанной со сложностью реализации булевых функций в заданном классе схем, обычно предлагается специальный метод синтеза, а соответствующая нижняя оценка устанавливается из т.н. мощностного неравенства, предложенного К. Шенноном [3]. Точность получаемых оценок можно характеризовать их относительной погрешностью, равной отношению разности между верхней и нижней оценками функции Шеннона к ней самой [13]. Будем также рассматривать г(п)-нормированную относительную погрешность (г(п)-НОП) оценок некоторой функции Шеннона L(n), равную величине относительной погрешности оценок, умноженной на г (га), где г (га) - растущая функция от натурального аргумента га.

Для указанных выше оценок [19], [7] и [8] функций Шеннона LKC(ra), Ьд°(га) и <S'BDD(ra) соответственно величина га-НОП составляла 0(л/п). Оценки [21] и [7] функций Шеннона 1Л(га) и Щ(п) соответственно для классов 7г-схем, а также оценки функции Шеннона, связанной со сложностью формул над произвольным полным конечным базисом, были получены с log га-НОП вида O(loglogra).

Работа С. А. Ложкина [9] положила начало исследованиям, связанным с уточнением известных оценок функций Шеннона для основных классов схем. В частности, в [9] изучался класс ориентированных контактных схем, т.е. контактных схем из ориентированных контактов, и для соответствующей функции Шеннона LOKC(ra) были получены асимптотические оценки, имеющие га-НОП вида 0(1). В работе [11] С. А. Ложкиным был предложен термин асимптотические оценки высокой степени точности (АОВСТ), для обозначения оценок некоторой функции Шеннона L(n) с г(га)-НОП вида 0(1), где г (га) асимптотически равно отношению 2п/Ь(п).

В работах [10-14] был изложен общий подход к получению верхних асимптотических оценок функций Шеннона, который в т.ч. позволяет получать АОВСТ для функций Шеннона, связанных с реализацией булевых функций в основных классах управляющих систем. В частности, в этих работах были получены АОВСТ для сложности формул над произвольном полным конечным базисом, для сложности схем из функциональных элементов с ограничениями на ветвления выходов элементов определенного типа, а также для сложности т.н. функционально-проводящих схем, класс которых обобщает некоторые распространенные классы схем.

Отметим, методы синтеза [11] позволяют установить асимптотическое значение 2п~1/п функции Шеннона £икс(?г), связанной с реализацией булевых функций в классе итеративных контактных схем, который является модификацией класса релейно-контактных схем [23]. При этом полученные оценки будут иметь n-НОП вида O(l), т.е. будут являться оценками высокой степени точности.

В работе [25] рассматривались схемы из функциональных элементов над произвольным полным базисом Б и элементом задержки, в которых допускались ветвления выходов только элементов задержки, а параметр t задавал максимальное допустимое количество ветвящихся элементов задержки в схеме. При некоторых ограничениях на величину t — t(n) были получены АОВСТ для соответствующей функции Шеннона.

В последнее время активно изучаются различные подклассы BDD, в которых вводятся определенные ограничения на структуру BDD (см, например, [2,4,5,15]). Так, например, рассматриваются упорядоченные (строго) ^-считывающие BDD, в которых каждый путь вычисления разбивается на к непересекающихся сегментов, таких, что на каждом сегменте каждая переменная встречается не более одного раза (соответственно в точности один раз) и переменные встречаются в определенном порядке, одинаковом для всех сегментов и путей вычисления. Упорядоченные 1-считывающие BDD являются «удобной» структурой данных для внутреннего представления некоторых булевых функций в системах автоматизированного проектирования интегральных схем (см., например, [2]). Исследуются вопросы о возможности реализации булевых функций упорядоченными (строго) ^-считывающими BDD полиномиальной сложности, а также вопросы существования нижних экспоненциальных оценок для сложности булевых функций в этих классах BDD (см. [5]). Отметим, что при к ^ 2 асимптотическое значение 2п/п для сложности упорядоченных ^-считывающих и строго ^-считывающих BDD приводится в работе [15]. При этом полученные оценки имеют n-НОП вида o(logn). Там же получены асимптотические оценки для сложности BDD общего вида с n-НОП вида o(logn).

В работе [26] описан класс схем контактного типа, представляющий собой математическую модель интегральных схем на дополняющих МОП-транзисторах (КМОП схем). В этой модели замыкающий (соответственно размыкающий) контакт переменной Х{ соответствует n-МОП или р-МОП транзистору, на затвор которого подаётся значение Xi (соответственно а контактная схема описывает соединения между истоками и стоками транзисторов. Отметим, что одно из естественных ограничений, которое можно вводить в подобных моделях, является ограничение степеней вершин контактной схемы. В работе [26] установлена асимптотика 271+1/п функции Шеннона, связанной со сложностью КМОП схем, для случая, когда контакты разрешается помечать только символами «внешних» булевых переменных. В другой модели КМОП схем [6] допускается использование в качестве пометок контактов специальных «внутренних» булевых переменных, реализуемых в вершинах схемы. Для соответствующей функции Шеннона в работе [6] получена асимптотика вида 2п/п.

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

В данной работе вводится класс ориентированных контактных схем с ограничением Л на полустепень исхода вершин схемы и ограничением v на количество различных булевых переменных, которые используются среди пометок исходящих дуг. При таком определении произвольная BDD принадлежит указанному классу схем при А.= 2, v = 1. Под сложностью ориентированной- контактной схемы понимается, как обычно, число контактов в ней. В работе разработаны новые методы синтеза, позволяющие установить асимптотические оценки сложности схем из класса , при v = Л, а также при Л = 2 и v — 1, имеющие n-НОП вида log log п + O(l). Предложенные методы синтеза позволяют также получить асимптотические оценки сложности BDD и сложности упорядоченных /с-считывающих BDD при k ^ 4 с 77.-НОП вида log log п + O(l). Таким образом, получены более точные, по сравнению с работой [15], асимптотические оценки соответствующих функций Шеннона для классов BDD.

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

В первом подходе для произвольных действительных положительных чисел w' и w", где w" > w', вес вершины v ориентированной контактной схемы Е полагается равным w', если в v заходит не более одной дуги и и>" иначе. Вес схемы равен сумме весов её вершин. Для функций Шеннона, связанных с весом схем класса весом BDD, а также весом упорядоченных (строго) ^-считывающих BDD при k ^ 2 в работе получены асимптотические оценки, являющиеся оценками высокой степени точности.

Следующая постановка задачи синтеза, предлагаемая в работе, состоит в том, что сложность булевой функции / определяется как минимальная сложность схемы из класса^/(Л.гУ>-°кс) реализующей / и имеющей не более t вершин, в которые заходит более одной дуги. При некоторых ограничениях на t ~ t(n) в работе получены оценки высокой степени точности для соответствующих функций Шеннона, связанных с классом и классами BDD.

Теперь опишем рассматриваемые в диссертации классы схем контактного типа, в которых накладывается ограничение на степени вершин. Отметим, что используя методы синтеза [7] можно получить асимптотическое значение j~2n/n (верхнюю оценку ^2п/п) для функции Шеннона L°KC(n) (соответственно L"KC(n)), связанной со сложностью ориентированных контактных схем (соответственно итеративных контактных схем), в которых степени вершин ограничены константой Л. При этом оценки для функции Шеннона L™(n) можно получить с п-НОП вида 0(у/п).

Метод синтеза, предложенный в настоящей работе позволяет установить асимптотические оценки функции Шеннона L°KC(n), для которых п-НОП составляет logn + log logn + 0(1). Также в работе описан новый асимптотически оптимальный метод синтеза, из которого вытекает асимптотика д^-2п1/п функции Шеннона L"KC(n). При этом оценки, полученные для функции Шеннона L"KC(n) имеют п-НОП вида 0{^Jn\ogn).

Основные результаты работы представлены в [17,18,28-32].

Основные определения и формулировка полученных результатов

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

Напомним основные понятия теории графов.

Набор Е вида (G,Vr, V"), где G = (V, Е) - граф с множеством вершин V и множеством ребер Е, а V' и V" - упорядоченные выборки из V длины р и q соответственно называется (р,ц)-сетъю. При этом i-я вершина выборки V' (соответственно выборки V") называется i-м входным полюсом или входом (соответственно i-м выходным полюсом или выходом) сети Е. Будем называть сеть Е = (G, VV") ориентированной (соответственно неориентированной) если граф G является ориентированным (соответственно неориентированным).

Число ребер, инцидентных вершине v графа G, т.е. степень вершины v, будем, как обычно, обозначать через deg^v). Пусть v - вершина ориентированного графа G, тогда обозначим через degj(v) (соответственно deg^(v)) полустепень захода вершины v, т.е. число дуг, заходящих в v (соответственно полустепень исхода вершины v, т.е. число дуг, исходящих из v). Напомним, что вершина v ориентированного графа G называется стоком (соответственно истоком), если deg^(v) — 0 (соответственно degj(v) = 0).

Буквами булевой переменной Х{ будем называть Х( и Xi.

Неориентированная сеть Е с входами а\,. ,ар, выходами &i,.,bq, в которой все ребра помечены буквами переменных xi,.,xn, называется (р, д)-контактной схемой ((р, q)-KC) от переменных xi,. ,хпк обозначается E(#i,., хп) или E(ai,., ар] &i,., bq\х\,., хп). Ребра КС называются контактами. При этом контакт, помеченный буквой Х{ (буквой х\) называется замыкающим (соответственно размыкающим). Обозначим множество всех контактных схем через UKG.

Напомним, что в графе G = (V:E) последовательность, состоящая из ребер ei,. ,еп, где ег- = (vi,vi+i) G Е, называется (vi — vn+i) путём графа G. Если все ребра пути различны, то он называется цепью, а если, кроме того, различны все его вершины, то - простой цепью. Цепь, начальная и конечная вершина которой совпадают, называется циклом.

Пусть Е - КС от переменных х\,., хп и пусть vi, V2 ~ вершины Е. Определим функцию проводимости gVuV2(x\,. ,хп) между вершинами vi и vi, как булеву функцию, которая равна 1 на наборе а — (о^,., ап) € {0,1}п тогда и только тогда, когда в схеме Е существует (vi — V2) цепь, состоящая из контактов, помеченных буквами х^1,., х%п ■ При этом будем говорить, что функция gVl,v2 реализуется между вершинами vi,V2- Отметим, что функции проводимости gVl,v2 и gV2,vl совпадают.

Положим по определению, что если v - вершина (1, т)-КС Е, то в v реализуется функция проводимости между входом и вершиной v, и что Е реализует набор функций (Д,., /то), где Д - функция проводимости между входом и г-м выходом схемы Е, г = 1,. ,ш. Также будем говорить, что (р, д)-КС E(sci,., хп) реализует матрицу из р строк и q столбцов, состоящую из булевых функций от переменных xi,.,xn так, что на пересечении г-й строки и j-ro столбца стоит функция проводимости между г-м входом и j-м выходом схемы Е, г = 1,. ,р, j = 1,., q. Схемы Е' и Е", реализующие матрицы F' и F" соответственно, называются эквивалентными, если2 F' = F".

Аналогично определяется структура и функционирование ориентированной контактной схемы (ОКС) с тем исключением, что граф ОКС является ориентированной сетью. При этом отметим, что если v\ и г>2 - различные вершины ОКС Е, то в общем случае функции проводимости gVuv2 и 9v2,vх могут не совпадать. Обозначим через Ыокс множество всех ОКС.

Пусть р ^ 1. Назовем р-входовой двоичной решающей диаграммой (p-BDD) любую (р, 2)-ОКС Е(я1,., хп), граф которой не содержит ориентированных циклов, входы Е и только они являются истоками, выходы являются стоками и из каждой вершины Е, отличной от выходов, исходит-пара противоположных контактов, помеченных буквами Х{ и х^ где г е [1, п]. При этом выходы p-BDD Е помечены 0 и 1, и считается, что Е реализует столбец функций проводимости между входами и выходом, помеченным 1.

Обозначим через UBDD класс всех ОКС, являющихся p-BDD для некоторого р ^ 1. Для удобства в обозначении произвольной схемы Е из класса ubdd будем иногда опускать указание числа входов схемы и называть схему Е двоичной решающей диаграммой (BDD). Отметим, что определение 1-входовой BDD совпадает с традиционным определением двоичной решающей диаграммы или ветвящейся программы (см., например, [4,5]).

Будем также рассматривать BDD с некоторыми структурными ограничениями. Зафиксируем порядок булевых переменных xi,. ,хп. Назовем BDD Е от переменных xi,.,xn упорядоченной (строго) k-считывающей с по

2Равеиство булевых функций, как обычно, будем рассматривать с точностью до добавления или изъятия несущественных переменных. рядком переменных х\,. ,хп, если произвольная простая цепь из входа в выход Е разбивается на к сегментов, таких, что:

1. на каждом сегменте переменные встречаются в порядке xi,. ,хп]

2. на каждом сегменте каждая переменная встречается не более одного раза (соответственно в точности один раз).

Множество всех упорядоченных ^-считывающих (соответственно строго fc-считывающих) с порядком ., хп BDD обозначим через Uk~OBDD(x 1,., хп) (соответственно через Uk-SOBDD(xi,., хп)). Введем также класс Uk-°BDD (Uk-S0BDD), содержащий все упорядоченные /с-считывающие (соответственно строго к-считывающие) BDD.

Пусть в (1, т)-КС Е(а; b\,., Ът\ х\,., хп) переменная Xi входит без отрицаний, а функция /j, реализуемая в выходе bj, не зависит от переменной Х{. В этом случае определим операцию присоединения переменной Х{ к выходу bj, в результате которой вершине, помеченной bj, сопоставляется внутренняя переменная и, выходная пометка bj снимается, а все пометки Х{ заменяются на пометку и. Полученная таким образом схема Е' зависит от переменных х\,., Xi-i,Xi+i,. • •, хп, имеет входной полюс а и выходные полюса Ь\,., ., bm. Пусть v - вершина схемы Е, и пусть gatV - функция, которая в ней реализуется, тогда по определению положим, что в схеме Е' в вершине v реализуется функция ga,v(xъ • • • > ^г-ъ fji xi+ь • • • > хп)- Функционирование схемы Е' представляет собой набор функций, реализуемых в ее выходах. Теперь пусть 1 < ji < . < ^ т и 1 ^ i\ < . < ^ п -наборы индексов и пусть переменные х^,., Х{к входят в схему Е без отрицаний, а каждая из функций fjt,., fjk не зависит существенно от переменных а. ,Xik. В этом случае определим операцию одновременного присоединения переменных х^,., Х{к к выходам bj1,., bjk соответственно, состоящую в последовательном выполнении операций присоединения переменной х^ к выходу bjx, ., переменной Х{к к выходу bjk. При этом выходу bjt сопоставляется внутренняя переменная Ujt, t = 1,. ,к. Нетрудно убедиться в том, что при выполнении указанных условий на функции ,., fjk введённая операция определена корректно и её результат не зависит от порядка, в котором применяются однократные операции присоединения переменной к выходу. Схема, полученная в результате присоединения переменных к выходам, называется итеративной контактной схемой (ИКС) на базе КС Е. Множество всех ИКС обозначим через ЫИКС.

Для КС (ОКС) Е и натурального Л обозначим через М>А(Е) множество вершин v схемы Е, таких, что degs(i>) > Л. Для ОКС Е положим М>Л(Е) (соответственно М~Л(Е)) - множество вершин v схемы Е, таких, что deg£(i;) > Л (соответственно deg^f) > Л). Если £' - ИКС на базе КС Е, то положим М>Л(Е') = М>л( Е).

Для вершины v ОКС Е обозначим через число различных булевых переменных, которые встречаются среди пометок дуг, исходящих из v. Пусть г/(Е) = тах^(^)) где максимум берется по всем вершинам Е.

Обозначим через множество всех ОКС Е, таких, что множество М~Л(Е) является пустым и z/(E) ^ и. Таким образом, класс содержит схемы, в которых из каждой вершины исходит не более Л дуг, а среди пометок этих дуг используются буквы не более, чем г/ различных булевых переменных. Отметим, что из введённых определений следует, что WBDD С

Пусть Е - схема, принадлежащая одному из введенных выше классов ЫА, тогда сложностью 1/(Е) схемы Е называется число контактов в Е. Отметим, что если Е является BDD, то L(Е) - четное и число вершин Е равно величине (L(E)/2 + 2). В предположении, что класс

UA является полным, т.е. что любую булеву функцию можно реализовать некоторой схемой из класса ЫА, для булевой функции / определим величину LA(f), называемую сложностью f относительно функционала ЬА, как минимальное значение величины L(Е) на множестве тех схем Е из ЫА, которые реализуют /. Для натурального п определим, как обычно, функцию Шеннона ЬА(п)

LA(n) = max LA(f). f(xi,.,xn)

Пусть дополнительно известно, что для натурального Л множество схем Е класса ЫА, таких, что степени вершин Е не превосходят Л, является полным. Тогда для булевой функции / определим ЬА(/), как минимальное значение величины L(Е) на множестве схем Е из ЫА, реализующих /, таких, что М>Л(Е) = 0. Введём соответствующую функцию Шеннона LA (п)

L?(n) = max LA{f).

J(Xi,.,Xn)

Пусть г; - вершина ОКС Е. Для положительных действительных величин w' и го", где w" > w', введем понятие веса Ww^w»{v) вершины v следующим образом: w' 1 degJO) < 1, w\ degj(i/)>l.

Вес WW'iW"(E) схемы E есть сумма весов вершин Е.

Пусть UA - один из введенных выше классов ОКС с ограничением на полу степени исхода вершин. В предположении, что класс ЫА является полным, для булевой функции / определим величину WA,w„(f), называемую весом / относительно функционала WA, w„, как минимальное значение величины WW')Wit(Е) на множестве тех схем Е из ЫА, которые реализуют /. Пусть для натурального параметра t подмножество схем Е класса UA, таких, что IM+^E)! < t, является полным. Тогда определим LA(f, £), как минимальное значение величины L(Е) на множестве схем Е из ЫА1 реализующих /, таких, что IM+^E)! ^ t. Введём функции Шеннона WA, „(п) и LA(n,t)

Ww>,w»{n) = ™ах WA,iW„(f), f{xi,.,xn)

LA(n,t) = max LA{f,t). f(xi,.,xn)

Точность оценок некоторой функции Шеннона L{n) будем характеризовать их относительной погрешностью (ОП), т.е. отношением разности между верхней и нижней оценками функции Шеннона к ней самой [13]. Также введём n-нормированную относительную погрешность (n-НОП) оценок функции Шеннона L{n), равную величине относительной погрешности, умноженной на п. Асимптотическими оценками функции Шеннона L(n) высокой степени точности будем называть оценки с n-НОП вида 0(1).

Перечислим основные результаты для введенных функций Шеннона. Первая серия результатов относится к поведению функций Шеннона для веса ориентированных контактных схем и BDD.

Теорема 1. Для любых натуральных X и и, где а таксисе положительных вещественных величин w' и w", где w" > w', при п = 1,2,. справедливо3

Теорема 2. Для любого натурального k ^ 2, а также положительных вещественных величин w' и w", где w" > w', при п = 1,2,. справедливо 0) fb\ /I / п \ п w^(n) = 0*2. (г + 21ogn±0(l)^ (4)

W.W . .

П V 71

Отметим, что полученные асимптотические оценки (1)-(4) являются оценками высокой степени точности.

В диссертации также установлено, что если в определении веса WW>JW»(E) ОКС Е учитывать с весом w" вершины, в которые заходит более d дуг, где d - натуральная константа, а все остальные вершины учитывать с весом гс/, то асимптотика соответствующих функций Шеннона по-прежнему составляет 2п/п для класса и(х>иУокс и w' 2п/п для классов BDD.

Перечислим результаты для функций Шеннона, связанных со сложностью ориентированных контактных схем и BDD при наличии растущего ограничения t = t(n) на число вершин с полустепенью захода больше 1.

Теорема 3. Для любых натуральных X и и, где при п — 1,2,. и t = t{n), гдеА logt{n) = Г2(тг) и t(n) не превосходит 2п/п2, справедливо

L<V>-okc( t) = * . , , 2" т- (l ± О (-)).

А-1 log^ + ^lognV \nJJ

3Равенство r(n) — pin) ±0{q{n)) означает, что |r(rc) — p(n)| = 0(g(n)).

4Равенство p(n) = f2(q(n)) означает, что р(п) = 0(q(n)) и д(тг) = 0(р(тг)).

Теорема 4. Для любого натурального к ^ 2 при п = 1,2,. и £ = где £(п) —► оо при тг —> оо и t(n) не превосходит 2п/п2, справедливо и если, кроме того, log t(n) = шо

Отметим, что асимптотические оценки, приведенные в теореме 3 и в теореме 4 для класса BDD и класса упорядоченных ^-считывающих BDD при k ^ 2, являются оценками высокой степени точности.

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

Теорема 5. Для любых натуральных X и и, где при п = 1,2,. справедлива нижняя оценка

А-1 п1 п / а также в случае р = 1, X — 2 ив случае и — А при п = 1,2,. справедлива верхняя оценка ь<А,,)-окс(п) ^ . ^ Л + Wlogn + loglogn + Q(l)\ Л — 1 п \ п )

Теорема 6. Для любого натурального k ^ 4 при п = 1,2,. справедливы оценки

ОП+1 / / 1 \ \ ОП+1

-—(l-of-l ) <Lfc-0BDD' ' 1 п V \п J / + loglogn + 0(m п \ п J

Легко видеть, что асимптотические оценки, приведенные в теоремах 5, 6 имеют п-НОП вида log log п + 0(1).

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

Теорема Т. Для любого натурального А ^ 3 при п — 1,2,. справедливы оценки

LoKc(n) ^ Л • ^ f 1 4- -Alogrc + loglogn + Q(l) А — 2 п I п

Таким образом, оценки для функции Шеннона L°KC(n) имеет n-НОП вида log n -f log log п + O(l).

Теорема 8. Для любого натурального А ^ 3 при п = 1,2,. справедливы оценки

А 22 / logn - От А . £ /1 + 0 flgSg) V

2А — 2 п \ п J 2А — 2 п \ \ \/п J J

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

Отметим, что методы синтеза, используемые в диссертации при доказательстве верхних оценок теорем 1, 3 и 5 для класса ОКС с ограниченной полустепенью исхода, могут быть применены для получения аналогичных результатов в модели ОКС с ограниченной полустепенью захода.

Дальнейшее изложение будет построено следующим образом. Глава 1 содержит вспомогательные определения и утверждения, необходимые для получения верхних оценок функций Шеннона. В ней вводятся такие понятия, как селекторное разбиение переменных булевой функции, каноническая матрица булевой функции, универсальное множество функций и др. Там же приводятся простейшие методы синтеза схем. В главе 2 описывается метод синтеза схем из класса ^/(Л'г/)-°кс На основе регулярных разбиений единичного куба и универсальных множеств функций, позволяющий установить верхние оценки в теоремах 1-4. Также в главе 2 доказываются верхние оценки числа схем определённого вида из класса и классов BDD, которые затем используются при получении мощностных неравенств, позволяющих установить нижние оценки в теоремах 1-6. В третьей главе описан новый метод синтеза для получения верхних оценок теорем 5 и 6. Доказательство верхних и нижних оценок теорем 7 и 8 ведётся в главе 4 диссертации. При этом доказательство верхней оценки теоремы 7 основано на использовании метода синтеза главы 3, в то время как верхние оценки теоремы 8 получены с использованием нового метода синтеза.

1. Lee С. Y. Representation of switching circuits by binary-decision programs. Bell. Sys. Tech. J., vol. 38, 1959. - pp. 985-999.

2. Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD Foundations and Applications. Springer-Verlag, 1998. - p. 267.

3. Shannon С. E. The synthesis of two-terminal switching circuits. Bell Syst. Techn. J., 1949, v.28, N-l, pp. 59-98.

4. Wegener I. The complexity of Boolean functions. Teubner (Stuttgart)/Wiley (Chichester), 1987. p. 457.

5. Wegener I. Branching programs and binary decision diagrams. SIAM Publisher, 2000. p. 408.

6. Касим-Заде О. M. О сложности реализации булевых функций в одной модели электронных схем // Математические вопросы кибернетики. Вып. 2. М.: Наука, 1989. С. 145-160.

7. Коршунов А. Д. Об асимптотических оценках сложности контактных схем заданной степени // Дискретный анализ. Сб. науч. тр. Вып. 5. Новосибирск: Ин-т математики СО АН СССР, 1965. С. 35-63.

8. Кузьмин В. А. Оценка сложности реализации булевых функций программами простого типа. // Методы Дискретного анализа, 29, 1976. -С. 11-39.

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

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

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

12. Ложкин С. А. Асимптотические оценки высокой степени точности для сложности управляющих систем. Диссертация на соискание ученой степени доктора физ.-матем. наук. Москва. 1997.

13. Ложкин С. А., О сложности реализации произвольных булевых функций в некоторых классах BDD // Труды Международной школы-семинара "Дискретная математика и математическая кибернетика" (Ратмино, 31 мая 3 июня 2001 г.). - М.: МАКС Пресс, 2001. - С. 18-19.

14. Ложкин С. А. Лекции по основам кибернетики. М.: Изд-во МГУ, 2004. -256 с.

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

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

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

18. Лупанов О. Б. Об одном классе схем из функциональных элементов (формулы с конечной памятью) // Проблемы кибернетики. 1962. Вып. 7. С. 61-114.

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

20. Лупанов О. Б., Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984. 137 с.

21. Никитин А. А. О сложности реализации функций алгебры логики в некоторых классах автоматных схем // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 1999. №3. С. 4149.

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

23. Ху. Т. Целочисленное программирование и потоки в сетях. М.: Мир -1974. - 520 с.

24. Шиганов А. Е. Асимптотические оценки высокой степени точности для сложности схем из некоторых классов // Сборник тезисов лучших дипломных работ 2006 года. М.: Издательский отдел фак-та ВМиК, 2006, С. 73-74

25. Шиганов А. Е. О сложности ориентированных контактных схем с ограниченной полустепеныо исхода // Проблемы теоретической кибернетики. Тезисы докл. XV Международной конф. Казань: Отечество, 2008. С. 133.

26. Шиганов А. Е. О синтезе ориентированных контактных схем с некоторыми ограничениями на смежные контакты // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2009. т. С. 46-52.

27. Шиганов А. Е. О сложности ориентированных контактных схем с ограниченной полустепенью исхода // Учен. зап. Казан, ун-та. Сер. Физ.-матем. науки. 2009. - Т. 151, кн. 2 - С. 164-172.

28. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. -384 с.