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




Скачать 77.79 Kb.
PDF просмотр
НазваниеАвтореферат диссертации на соискание ученой степени
Дата конвертации12.01.2013
Размер77.79 Kb.
ТипАвтореферат диссертации
Московский государственный университет
имени М. В. Ломоносова
На правах рукописи
Шиганов Александр Евгеньевич
Синтез схем контактного типа
с ограничениями на смежные контакты
Специальность 01.01.09 — дискретная математика
и математическая кибернетика
Автореферат
диссертации на соискание ученой степени
кандидата физико-математических наук
Москва — 2010

Работа выполнена на кафедре математической кибернетики факультета вы-
числительной математики и кибернетики Московского государственного уни-
верситета имени М. В. Ломоносова.
Научный руководитель:
доктор физико-математических наук,
профессор
Ложкин Сергей Андреевич
Официальные оппоненты:
доктор физико-математических наук,
профессор механико-математического
факультета МГУ имени М. В. Ломоносова
Редькин Николай Петрович
кандидат физико-математических наук,
старший научный сотрудник
Института системных исследований РАН
Кузнецов Юрий Владимирович
Ведущая организация:
Институт системного анализа РАН
Защита диссертации состоится 18 июня 2010 г. в 11 час. 00 мин. на заседании
диссертационного совета Д 501.001.44 при Московском государственном уни-
верситете имени М. В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленин-
ские горы, МГУ, 2-й учебный корпус, факультет вычислительной математики
и кибернетики, ауд. 685.
С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ
имени М. В. Ломоносова. С текстом автореферата можно ознакомиться на
официальном сайте факультета ВМК МГУ http://cs.msu.su в разделе «Нау-
ка» — «Работа диссертационных советов» — «Д 501.001.44».
Автореферат разослан «
» мая 2010 г.
Ученый секретарь
диссертационного совета Д 501.001.44
профессор
Трифонов Н. П.

Общая характеристика работы
Актуальность темы. Задача синтеза управляющих систем является од-
ной из основных задач кибернетики. Она состоит в построении для заданной
системы булевых функций реализующей е¨
е схемы, принадлежащей заданно-
му классу и являющейся оптимальной по какому-либо критерию. Чаще всего
в качестве такого критерия выступает сложность схемы, понимаемая как сум-
ма сложностей составляющих е¨
е элементов. В диссертации рассматривается
задача массового синтеза, которая заключается в изучении асимптотического
поведения так называемой функции Шеннона L(n) от натурального аргумен-
та n, равной сложности реализации самой «трудной» булевой функции от n
переменных с помощью схем из заданного класса.
Среди различных моделей дискретных управляющих систем можно вы-
делить модели схем «проводящего» или «контактного» типа, в которых реа-
лизация булевых функций осуществляется с помощью передачи сигналов по
ребрам (дугам) графа схемы, называемым контактами. При этом проводимо-
стью контактов «управляют» внешние или специальные внутренние булевы
переменные.
Задача массового синтеза для класса контактных схем была впервые по-
ставлена в работе Шеннона1, в которой им был установлен порядок функции
L(n), связанной со сложностью контактных схем, где под сложностью пони-
малось общее число контактов схемы. Асимптотически оптимальный метод
синтеза контактных схем был разработан О. Б. Лупановым2. Им же были
установлены асимптотические значения функций Шеннона, связанных с ре-
ализацией булевых функций во всех основных классах схем (классе схем из
функциональных элементов, классе формул, классе контактных и релейно-
контактных схем и др.)2 3 4 5.
1Shannon C. E. The synthesis of two-terminal switching circuits. Bell Syst. Techn. J., 1949, v. 28, N-l,
pp. 59–98.
2Лупанов О. Б. О синтезе контактных схем // ДАН СССР. – 1958. – Т. 119, № 1. – С. 23–26.
3Лупанов О. Б. Об одном методе синтеза схем // Известия вузов, Радиофизика. – 1958. – Т. 1, № 1. –
C.120–140.
4Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы киберне-
тики. Вып. 3. – М.: Физматгиз, 1960. – C. 61–80.
5Лупанов О. Б. О сложности реализации функций алгебры логики релейно-контактными схемами //
Проблемы кибернетики. Вып. 11. – М.: Наука, 1964. – C. 25–48.
1

При моделировании дискретных преобразователей информации обычно
стремятся учесть их физические особенности, например, площадь, ¨
емкость
или задержку функционального элемента интегральной схемы, возможность
размещения транзисторов на подложке интегральной схемы и т.д. С этой
целью ставится задача синтеза схем из классов с некоторыми ограничения-
ми на структуру, а также применяются различные подходы к определению
сложности схем.
Так, например, О. Б. Лупанов получил6 асимптотику функции Шенно-
на, связанной со сложностью схем из функциональных элементов, в которых
выход любого элемента может соединятся не более, чем с заданным числом
входов других элементов. А. Д. Коршунов разработал7 асимптотически опти-
мальный метод синтеза контактных схем, в которых степени вершин ограни-
чены некоторой константой. Отметим, что подобные ограничения позволяют,
в том числе, учитывать ограниченную ¨
емкость физических элементов схем.
Модели схем контактного типа являются удобными математическими мо-
делями интегральных схем на дополняющих МОП-транзисторах (КМОП-схем)8.
При этом, обычно, контакт с пометкой xσ соответствует n-МОП или p-МОП
i
транзистору, на затвор которого пода¨
ется значение xσ, а контактная схема
i
описывает соединения между истоками и стоками транзисторов. Известна8
асимптотика функции Шеннона, связанной со сложностью КМОП-схем, для
случая, когда контакты разрешается помечать только символами «внешних»
булевых переменных. Этот случай соответствует моделированию КМОП-схем
с помощью контактных схем. Если также допускается использование в каче-
стве пометок контактов специальных «внутренних» булевых переменных, ре-
ализуемых в вершинах схемы, то возможно получение асимптотически в два
раза более эффективной реализации булевых функций9. Этот случай, фак-
тически, соответствует моделированию КМОП-схем с помощью итеративных
6Лупанов О. Б. Об одном классе схем из функциональных элементов (формулы с конечной памятью) //
Проблемы кибернетики. 1962. Вып. 7. С. 61–114.
7Коршунов А. Д. Об асимптотических оценках сложности контактных схем заданной степени // Дис-
кретный анализ. Сб. науч. тр. Вып. 5. Новосибирск: Ин-т математики СО АН СССР, 1965. С. 35–63.
8Сапоженко А. А., Ложкин С. А. Методы логического проектирования и оценки сложности схем на
дополняющих МОП-транзисторах // Микроэлектроника. 1983. Т. 12. № 1. С. 42–47.
9Касим-Заде О. М. О сложности реализации булевых функций в одной модели электронных схем //
Математические вопросы кибернетики. Вып. 2. М.: Наука, 1989. С. 145–160.
2

контактных схем10, являющихся модификацией класса релейно-контактных
схем. В связи с этим интересен вопрос об асимптотике функции Шеннона,
связанной со сложностью итеративных контактных схем с ограниченной сте-
пенью вершин.
К классу схем контактного типа можно также отнести впервые предло-
женный Ли11 класс двоичных решающих диаграмм (Binary Decision Diagrams,
BDDs), активно изучаемый в настоящее время и применяемый, в том чис-
ле, для «программной» реализации булевых функций. Асимптотика функции
Шеннона для сложности BDD установлена В. А. Кузьминым12.
Наряду с моделями схем с «ж¨
есткими» структурными ограничениями,
в литературе также рассматриваются модели, в которых допускается нали-
чие незначительного числа «нарушений» ограничений. Так, А. А. Никитин
получил13 асимптотику функции Шеннона для сложности схем из функцио-
нальных элементов и элементов задержки, в которых допускались ветвления
выходов только элементов задержки, прич¨
ем максимальное количество «вет-
вящихся» элементов задержки в схеме было ограничено.
Важным направлением теории синтеза является получение для функций
Шеннона оценок высокой степени точности, то есть таких оценок некоторой
функции Шеннона L(n), имеющей порядок роста 2n/n, относительная по-
грешность которых имеет вид O(1/n). Заметим, что указанные оценки, по
сути, устанавливают значение первого остаточного члена асимптотического
разложения соответствующей функции Шеннона. Методы получения оценок
высокой степени точности разработаны С. А. Ложкиным10 14. В своих рабо-
тах С. А. Ложкин получил оценки высокой степени точности для сложности
основных классов схем, в том числе ориентированных контактных схем и
итеративных контактных схем.
10Ложкин С.А. Асимптотические оценки высокой степени точности для сложности управляющих систем
из некоторых классов // Математические вопросы кибернетики. Вып. 6. М.: Наука, 1996. C. 189–214.
11Lee C. Y. Representation of switching circuits by binary-decision programs. Bell. Sys. Tech. J., vol. 38,
1959. – pp. 985–999.
12Кузьмин В. А. Оценка сложности реализации булевых функций программами простого типа. // Ме-
тоды Дискретного анализа, 29, 1976. – C. 11–39.
13Никитин А. А. О сложности реализации функций алгебры логики в некоторых классах автоматных
схем // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 1999.
№ 3. С. 41–49.
14Ложкин С. А. Асимптотические оценки высокой степени точности для сложности управляющих си-
стем. Диссертация на соискание ученой степени доктора физ.-матем. наук. Москва. 1997.
3

Заметим, что для любого из перечисленных выше классов схем соответ-
ствующая функция Шеннона L(n) асимптотически совпадает со сложностью
почти всех функций от n переменных.
Цель диссертации. Первой целью диссертации является разработка ме-
тодов синтеза схем контактного типа с некоторыми ограничениями на смеж-
ные контакты. Вторая цель диссертации состоит в получение асимптотиче-
ских оценок функций Шеннона, связанных с различными функционалами
сложности указанных схем.
Научная новизна. Все полученные в диссертации результаты являются
новыми. В данной работе впервые систематически исследованы вопросы реа-
лизации булевых функций схемами контактного типа с различными ограни-
чениями на смежные контакты. Предложены новые функционалы сложности
ориентированных контактных схем и двоичных решающих диаграмм, позво-
ляющие рассматривать различные виды ограничений на смежные контакты,
а также степень строгости их выполнения, и получены асимптотические оцен-
ки высокой степени точности функций Шеннона, связанных с указанными
функционалами сложности. Разработан метод синтеза ориентированных кон-
тактных схем с ограничением на полустепени исхода вершин, позволяющий
установить асимптотику первого остаточного члена асимптотического раз-
ложения соответствующей функции Шеннона. Разработан асимптотически
оптимальный метод синтеза итеративных контактных схем с ограничением
на степени вершин.
Теоретическая и практическая ценность. Работа носит теоретиче-
ский характер. Методы синтеза, разработанные в диссертации, могут, по мне-
нию автора, быть применены при решении задач синтеза различных видов
схем контактного типа, в том числе, КМОП-схем.
Методы исследования. В работе используются методы синтеза схем,
ориентированные на получение оценок высокой степени точности, мощност-
ные методы установления нижних оценок, методы теории графов.
Публикации и апробирование. По теме диссертации опубликовано 7
печатных работ [1–7], из которых статьи [5,6] – в изданиях, рекомендованных
ВАК. Результаты диссертации докладывались на семинарах кафедры мате-
матической кибернетики факультета ВМК МГУ, а также на семинаре ка-
4

федры дискретной математики механико-математического факультета МГУ
и, кроме того, докладывались и обсуждались на следующих конференциях и
семинарах:
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. Класс U ОКС всех ориентированных контактных схем (ОКС), то есть кон-
тактных схем из ориентированных контактов, проводящих только в со-
ответствующем направлении.
2. Класс U λ,ν -ОКС всех ОКС, в которых из каждой вершины исходит не
более λ дуг и для каждой вершины среди пометок исходящих из не¨
е
дуг встречается не более, чем ν, различных переменных.
3. Класс U BDD двоичных решающих диаграмм (BDD), прич¨
ем под BDD от
переменных x1, . . . , xn в диссертации понимается произвольная ацикли-
ческая схема Σ из класса U 2,1 -ОКС, граф которой содержит два стока,
помеченных 0 и 1 и являющихся выходами схемы, один или несколько
5

истоков, являющихся входами схемы, а из каждой вершины Σ, отлич-
ной от выходов исходит пара противоположных контактов вида xi и xi,
где 1
i
n.
4. Класс U k-OBDD (U k-SOBDD) упорядоченных (строго) k-считывающих дво-
ичных решающих диаграмм, то есть схем Σ из класса U BDD, в которых
произвольная простая цепь из входа в выход Σ разбивается на k сегмен-
тов, таких, что на каждом сегменте переменные встречаются в порядке,
одинаковом для всех сегментов и указанных цепей, и при этом на каж-
дом сегменте каждая входная переменная Σ встречается не более одного
раза (соответственно в точности один раз).
5. Класс U ИКС всех итеративных контактных схем (ИКС), где под итера-
тивной контактной схемой понимается схема Σ , полученная из некото-
рой контактной схемы Σ, имеющей один вход и m выходов b1, . . . , bm
и зависящей от переменных x1, . . . , xn, в результате применения опе-
рации присоединения различных переменных xi , . . . , x
к различным
1
ik
выходам bj , . . . , b соответственно. При этом накладывается ограниче-
1
jk
ние, связанное с тем, что переменные xi , . . . , x входят в схему Σ без
1
ik
отрицаний, а функции, реализуемые в выходах bj , . . . , b , не зависят
1
jk
существенно от переменных xi , . . . , x .
1
ik
Пусть схема Σ принадлежит одному из введ¨
енных классов схем, тогда
под сложностью L(Σ) схемы Σ понимается число контактов в Σ. Далее,
если схема Σ является ОКС или BDD, то для фиксированных положитель-
ных действительных чисел w и w , где w > w , дополнительно определим
вес Ww ,w (Σ) схемы Σ, как сумму весов вершин Σ, прич¨ем вес истока и вер-
шины с одной входящей дугой равен w , а все остальные вершины имеют
вес w .
Для булевой функции f в диссертации определяются следующие функ-
ционалы сложности:
1. Величина LA(f ), где U A – один из введ¨
енных классов схем, равна мини-
муму сложностей L(Σ), где минимум бер¨
ется по множеству всех схем Σ
из класса U A, реализующих f .
2. Величина W A
(f ), где U A – один из введ¨
енных классов ОКС или BDD,
w ,w
равна минимуму весов Ww ,w (Σ), где минимум бер¨ется по множеству
6

всех схем Σ из класса U A, реализующих f .
3. Величина LA(f, t), где t – натуральное, а U A – один из введ¨
енных клас-
сов ОКС или BDD, равна минимуму сложностей L(Σ), где минимум
бер¨
ется по множеству всех схем Σ из класса U A, реализующих f , та-
ких, что схема Σ содержит не более t вершин, в которые заходит более
одной дуги.
4. Величина LОКС(f ) (соответственно LИКС(f )) равна минимуму сложно-
λ
λ
стей L(Σ), где минимум бер¨
ется по множеству всех ОКС (соответствен-
но ИКС) Σ, реализующих f , таких, что степень вершин Σ ограничена
константой λ.
Для натурального n функции Шеннона вида LA(n), W A
(n), LA(n, t) и
w ,w
LA(n) традиционно определяются, как максимум величин LA(f ), W A
(f ),
λ
w ,w
LA(f, t) и LA(f ) соответственно, где максимум бер¨
ется по множеству булевых
λ
функций f от n переменных.
В первой главе вводится ряд определений и утверждений, используемых
в диссертации при описании методов синтеза схем.
Разбиение D множества переменных булевой функции ϕ(y1, . . . , yt) назы-
вается селекторным, если для каждой переменной y из произвольной компо-
ненты Y разбиения D можно подобрать набор булевых констант ˜
α, такой,
что переменные из одной компоненты разбиения D принимают на наборе ˜
α
одинаковые значения и что после подстановки в функцию ϕ констант набо-
ра ˜
α на места всех переменных, за исключением переменных компоненты Y ,
функция ϕ совпадает с y или y.
В §1.1 диссертации формулируются леммы 1.1 и 1.2, в которых описаны
способы получения «хороших» селекторных разбиений при суперпозициях
булевых функций. Формулировки леммы 1.2 в различных вариантах встре-
чаются у С. А. Ложкина10 14, а сама лемма 1.2 доказывается с использовани-
ем леммы 1.1, являющейся, по сути, более сильным утверждением. С содер-
жательной точки зрения лемма 1.1 позволяет упростить процесс получения
селекторных разбиений, сводя его к проверке некоторых свойств функций,
участвующих в суперпозиции.
В §1.2 вводится понятие ϕ-универсального множества функций поряд-
ка m, то есть такого множества функций G от переменных x1, . . . , xm, что
7

для любой функции g(x1, . . . , xm) в множестве G найдутся функции, которые
можно подставить в функцию ϕ так, что полученная в результате суперпози-
ции функция совпадает с g. Главным критерием «качества» универсального
множества является число функций в н¨
ем. В лемме 1.5 утверждается возмож-
ность построения «эффективного» ϕ-универсального множества при наличии
подходящего селекторного разбиения функции ϕ.
Некоторые вопросы суперпозиции ОКС изложены в §1.3. Там же вво-
дятся вспомогательные классы схем, с помощью которых удобно описывать
построение упорядоченных (строго) k-считывающих BDD, и приводятся про-
стейшие методы синтеза ОКС. В лемме 1.7 да¨
ется оценка сложности реали-
зации булевой функции посредством моделирования е¨
е совершенной ДНФ с
использованием контактного дерева. В лемме 1.8 приводится оценка слож-
ности реализации системы булевых функций с помощью одного шага разло-
жения по методу каскадов, после чего остаточные функции реализуются по
лемме 1.7.
Во второй главе диссертации описывается метод синтеза ОКС и BDD с
близким к оптимальному значением веса, а также близким к оптимальному
значением сложности при наличии ограничения на число вершин, в которые
заходит более одной дуги, для почти всех функций.
В §2.1 изучаются вопросы реализации схемами из класса U λ,ν -ОКС ряда
вспомогательных функций, для которых можно «эффективно» строить уни-
версальные множества. Отдельно рассматриваются два случая: случай ν = λ
и случай ν < λ. В обоих случаях указанные функции получаются в результа-
те многократной суперпозиции некоторых базисных функций, прич¨
ем мно-
жество переменных базисных функций условно разделяется на множество
прямых и множество итеративных переменных, а при суперпозиции базисных
функций подстановка одних функций осуществляется на места итеративных
переменных других функций. Для получения необходимых селекторных раз-
биений при суперпозиции функций в случае ν = λ используется лемма 1.2, а
в случае ν < λ – лемма 2.3, вытекающая из леммы 1.1.
Метод синтеза ОКС и BDD, основанный на специальных разбиениях еди-
ничного куба и универсальных множествах функций, описан в §2.2. Построе-
ние схемы, принадлежащей классу U λ,ν -ОКС и реализующей заданную булеву
8

функцию f от переменных x1, . . . , xn, включает в себя:
1. построение специальной схемы Σϕ, реализующей вспомогательную бу-
леву функцию ϕ, и построение ϕ-универсального множества G поряд-
ка m, где m < n;
2. построение специального разбиения ∆ множества наборов q-мерного
единичного куба, где m < q < n, от переменных x1, . . . , xq, такого, что
функции из множества G , где G ⊂ G, «моделируются» указанными
переменными или их отрицаниями на компонентах разбиения ∆;
3. моделирование значений каждой функции вида
f (x1, . . . , xq, σq+1, . . . , σn),
где σq+1, . . . , σn – булевы константы, на каждой компоненте разбие-
ния ∆ с помощью суперпозиции схемы Σϕ и схемы ΣG , реализующей
систему G = G\G .
4. «сборка» схемы Σf , реализующей f , из схем, построенных в п.3, на
основе разложения f по переменным xq+1, . . . , xn.
Метод синтеза схем класса U λ,ν -ОКС приводится в теореме 2.1. Метод синте-
за упорядоченных (строго) k-считывающих, где k
2, двоичных решающих
диаграмм описан в теореме 2.2 (соответственно теореме 2.3) и представля-
ет собой, по сути, незначительную модификацию метода синтеза схем клас-
са U 2,1 -ОКС.
В §2.3 доказываются верхние оценки числа схем определ¨
енного вида из
классов ОКС и BDD, которые затем используются при получении мощност-
ных неравенств для доказательства нижних оценок функций Шеннона, свя-
занных с классами ОКС и BDD и различными функционалами сложности
схем.
Из результатов §2.2 и §2.3 вытекают теоремы 1–4, сформулированные во
введении диссертации.
Теорема 1. Для любых натуральных λ и ν, где λ
2 и 1
ν
λ,
а также положительных вещественных величин w и w , где w
> w ,
9

при n = 1, 2, . . . справедливо15
w
2n
2λ−ν−2 log n ± O(1)
W λ,ν -ОКС(n) =
·
1 +
λ−1
.
w ,w
λ − 1
n
n
Теорема 2. Для любого натурального k
2, а также положительных
вещественных величин w и w , где w > w , при n = 1, 2, . . . справедливо
w 2n
log n ± O(1)
W BDD (n) =
1 +
,
w ,w
n
n
w 2n
log n ± O(1)
W k-OBDD(n) =
1 +
,
w ,w
n
n
w 2n
2 log n ± O(1)
W k-SOBDD(n) =
1 +
.
w ,w
n
n
Теорема 3. Для любых натуральных λ и ν, где λ
2 и 1
ν
λ,
при n = 1, 2, . . . и t = t(n), где16 log t(n) = Ω(n) и t(n) не превосходит 2n/n2,
справедливо
λ
2n
1
L λ,ν -ОКС(n, t) =
·
1 ± O
.
λ − 1
log t + ν log n
n
λ−1
Теорема 4. Для любого натурального k
2 при n = 1, 2, . . . и t = t(n),
где t(n) → ∞ при n → ∞ и t(n) не превосходит 2n/n2, справедливо
2n+1
1
Lk-SOBDD(n, t) =
1 ± O
,
log t
log t
и если, кроме того, log t(n) = Ω(n), то
2n+1
1
LBDD(n, t) =
1 ± O
,
log nt
n
2n+1
1
Lk-OBDD(n, t) =
1 ± O
.
log nt
n
15Равенство r(n) = p(n)±O(q(n)) означает, что |r(n)−p(n)| = O(q(n)). В данной работе основание 2 у ло-
гарифмов опускается.
16Равенство p(n) = Ω(q(n)) означает, что p(n) = O(q(n)) и q(n) = O(p(n)).
10

В §2.3 также установлено, что если в определении веса Ww ,w (Σ) ОКС Σ
учитывать с весом w вершины, в которые заходит более d дуг, где d – на-
туральная константа, а все остальные вершины учитывать с весом w , то
асимптотика функций Шеннона по-прежнему составляет w 2n/n для клас-
λ−1
са U λ,ν -ОКС и w 2n/n для классов BDD соответственно.
В третьей главе диссертации приводятся методы синтеза схем из клас-
са U λ,λ -ОКС и BDD, близких по сложности к оптимальным для почти всех
функций. Построение схемы, реализующей заданную булеву функцию f от n
переменных, включает в себя:
1. разбиение множества наборов n-мерного единичного куба на два под-
множества A1 и A2, прич¨ем A1 является n1-мерным единичным кубом,
где n1 < n, а A2 = {0, 1}n\A1.
2. построение специальных схем Σϕ и Σ , реализующих вспомогательные
1
ϕ2
булевы функции ϕ1 и ϕ2 соответственно;
3. построение множества функций G, такого, что на наборах каждого из
множеств A1 и A2 функции из G совпадают с функциями некоторых
ϕ1-универсальных множеств, а на наборах множества A2 на промежу-
точных входах схем Σϕ , определ¨енным образом соедин¨енных со схе-
1
мой Σ , реализующей часть функций из G, реализуются функции неко-
торого ϕ2-универсального множества;
4. построение для i = 1, 2 специального разбиения ∆i множества набо-
ров Ai, такого, что некоторые функции системы G можно «промоде-
лировать» переменными или их отрицаниями на компонентах разбие-
ния ∆i;
5. моделирование значений функции f на каждой компоненте разбиения ∆1
с помощью суперпозиции схемы Σϕ и схемы Σ ;
1
6. моделирование значений функции f на каждой компоненте разбиения ∆2
с помощью суперпозиции схем Σϕ и промежуточных входов схем, по-
2
строенных в п.5;
7. «сборка» схем, построенных в пп.5–6 в схему Σf , реализующую f .
Метод синтеза схем класса U λ,λ -ОКС приводится при доказательстве тео-
ремы 3.1, а метод синтеза упорядоченных k-считывающих, где k
4, дво-
ичных решающих диаграмм – при доказательстве теоремы 3.2. В §3.2 также
11

делается замечание к теореме 3.1 об одном свойстве схемы Σf , построенной
при доказательстве этой теоремы. В замечании приводится оценка суммар-
ной полустепени захода тех вершин схемы Σf , в которые заходит более одной
дуги.
Из теорем 3.1 и 3.2, из соотношений между классами схем U 2,1 -ОКС, U BDD,
U k-OBDD, а также из нижних оценок функций Шеннона, доказанных в §2.3,
вытекают теоремы 5 и 6, сформулированные во введении диссертации.
Теорема 5. Для любых натуральных λ и ν, где λ
2 и 1
ν
λ,
при n = 1, 2, . . . справедлива нижняя оценка
λ
2n
λ−ν−1 log n − O(1)
L λ,ν -ОКС(n)
·
1 + λ−1
,
λ − 1
n
n
а также в случае ν = 1, λ = 2 и в случае ν = λ при n = 1, 2, . . . справедлива
верхняя оценка
λ
2n
λ−ν−1 log n + log log n + O(1)
L λ,ν -ОКС(n)
·
1 + λ−1
.
λ − 1
n
n
Теорема 6. Для любого натурального k
4 при n = 1, 2, . . . справедливы
оценки
2n+1
1
2n+1
log log n + O(1)
1 − O
LBDD(n)
1 +
.
n
n
n
n
2n+1
1
2n+1
log log n + O(1)
1 − O
Lk-OBDD(n)
1 +
.
n
n
n
n
Четв¨
ертая глава диссертации посвящена методам синтеза итеративных
контактных схем и ориентированных контактных схем с ограничением на
степени вершин.
Построения для класса итеративных контактных схем приводятся в п. 4.1.1.
В н¨
ем описывается подход А. Д. Коршунова7 к построению контактных схем
с ограниченной степенью вершин для функций вида yσf , где σ ∈ {0, 1}, если
известна контактная схема для функции f . Этот подход сформулирован в
лемме 4.2 и сводится к добавлению в схему для f необходимого количества
12

контактов вида yσ. Также в п. 4.1.1 формулируется следствие из теоремы
Холла, которое заключается в том, что в двудольном графе, таком, что сте-
пень вершин одной доли равна d, а степень вершин второй доли не превосхо-
дит d, существует паросочетание, насыщающее вершины первой доли.
Построение итеративной контактной схемы, реализующей заданную бу-
леву функцию f от переменных x1, . . . , xn и имеющую вершины степени не
более λ, происходит следующим образом. Функция f представляется в ви-
де f = xnf0 ∨ xnf1, где fγ = f (x1, . . . , xn−1, γ), γ ∈ {0, 1}. Для γ = 0, 1
строится схема Σf , реализующая функцию f
γ
γ , из которой с использованием
леммы 4.2 получается схема Σ , реализующая функцию xγ f
f
γ с вершинами
γ
n
степени не более λ. Схема Σf , реализующая f , получается в результате па-
раллельного соединения схем Σ
и Σ . Метод синтеза схемы Σ , γ ∈ {0, 1},
f
f
0
f1
γ
включает в себя:
1. построение специальной схемы Σϕ, реализующей вспомогательную бу-
леву функцию ϕ, и построение ϕ-универсального множества G поряд-
ка m, где m < (n − 1), прич¨
ем множество G имеет вид G = G1 ∪G2 ∪G3,
а его функции зависят от переменных x1, . . . , xm;
2. построение схемы Σi, реализующей функции множества Gi, i = 1, 2, 3;
3. построение по функции fγ специальных двудольных графов и получе-
ние по следствию из теоремы Холла в каждом из графов паросочетания,
насыщающего вершины одной из долей;
4. присоединение схем C1, . . . , Ck, представляющих собой цепочки контак-
тов, к выходам схемы Σ1;
5. выбор в соответствии с правилами, определяемыми построенными па-
росочетаниями, для каждого контакта схем C1, . . . , Ck функции из си-
стемы G2 для «управления» указанным контактом;
6. реализация каждой функции вида
fγ(x1, . . . , xm, σm+1, . . . , σn−1),
где σm+1, . . . , σn−1 – булевы константы, с помощью суперпозиции схе-
мы Σϕ и некоторых выходов цепочек C1, . . . , Ck, прич¨ем контакты схе-
мы Σϕ «управляются» функциями системы G3;
7. «сборка» схемы Σf из схем, построенных в п.6, на основе разложения
γ
13

fγ по переменным xm+1, . . . , xn−1.
Метод синтеза ориентированных контактных схем, имеющих вершины
степени не более λ, излагается в п. 4.1.2 и заключается в незначительной
модификации схемы из класса U λ−1,λ−1 -ОКС, построенной при доказатель-
стве теоремы 3.1 с уч¨
етом замечания к ней.
Из результатов §4.1 и §4.2 вытекают теоремы 7 и 8, сформулированные
во введении диссертации.
Теорема 7. Для любого натурального λ
3 при n = 1, 2, . . . справедливы
оценки
λ
2n
2
log n + O(1)
LОКС(n)
·
1 − λ−2
,
λ
λ − 2
n
n
λ
2n
− 1 log n + log log n + O(1)
LОКС(n)
·
1 +
λ−2
.
λ
λ − 2
n
n
Теорема 8. Для любого натурального λ
3 при n = 1, 2, . . . справедливы
оценки
λ
2n
log n − O(1)
λ
2n
log n
·
1 +
LИКС(n)
·
1 + O

.
2λ − 2
n
n
λ
2λ − 2
n
n
Заметим, что нижние оценки функций Шеннона, привед¨
енные в теоре-
мах 1–8, справедливы для сложности (относительно соответствующих функ-
ционалов) почти всех функций от n переменных.
Основные результаты работы
1. Предложена модель схем контактного типа и введены новые функци-
оналы сложности схем, позволяющие рассматривать различные виды
ограничений на смежные контакты, а также учитывать степень строго-
сти их выполнения.
2. В рамках предложенной модели разработаны методы синтеза ориенти-
рованных контактных схем и двоичных решающих диаграмм. Установ-
лены асимптотические оценки высокой степени точности для функций
14

Шеннона, связанных с введ¨
енными функционалами сложности указан-
ных схем.
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.
15

[5] Шиганов А. Е. О синтезе ориентированных контактных схем с некоторы-
ми ограничениями на смежные контакты // Вестник Московского уни-
верситета. Серия 15. Вычислительная математика и кибернетика. 2009.
№3. С. 46–52.
[6] Шиганов А. Е. О сложности ориентированных контактных схем с ограни-
ченной полустепенью исхода // Учен. зап. Казан. ун-та. Сер. Физ.-матем.
науки. – 2009. – T. 151, кн. 2 – С. 164–172.
[7] Ложкин С. А., Шиганов А. Е. Некоторые оценки сложности ориентиро-
ванных контактных схем с ограниченной полустепенью исхода // Мате-
риалы X Международного семинара "Дискретная математика и е¨
е при-
ложения"(Москва, МГУ, 1-6 февраля 2010 г.). – М.: Изд-во механико-
математического факультета МГУ, 2010. – С. 122–123.
16


Похожие:

Автореферат диссертации на соискание ученой степени icon  автореферат диссертации на соискание ученой степени  

Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени  

Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени

Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание учёной степени
Н. Г. Чернышевского по адресу: г. Саратов, ул. Астраханская, 83, 3-й корп., ауд. 34
Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени
Чулкова Н. В., Макаров В. К., Супрун С. Г., Макарова Т. В. Исследование концентрации кавита
Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени
Боголюбов Н. Н., Митропольский Ю. А. Асимптотические методы в теории нелинейных колебаний. М
Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени
Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени
С диссертацией можно ознакомиться в библиотеке им. А. М. Горького Санкт-Петербургского государственного
Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени
Защита состоится «4» июня 2009 г. в 10 часов на заседании Диссертационного совета в 
Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени
Санкт-Петербургский государственный университет информационных технологий, механики и оптики
Разместите кнопку на своём сайте:
TopReferat


База данных защищена авторским правом ©topreferat.znate.ru 2012
обратиться к администрации
ТопРеферат
Главная страница