О реализации функций алгебры логики схемами из некоторых классов, вложенными в гиперкубы

Седелев, Олег Борисович

О реализации функций алгебры логики схемами из некоторых классов, вложенными в гиперкубы тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Седелев, Олег Борисович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2008 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «О реализации функций алгебры логики схемами из некоторых классов, вложенными в гиперкубы»

Автореферат диссертации на тему "О реализации функций алгебры логики схемами из некоторых классов, вложенными в гиперкубы"

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

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

о/

Седелев Олег Борисович

О РЕАЛИЗАЦИИ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ СХЕМАМИ ИЗ НЕКОТОРЫХ КЛАССОВ, ВЛОЖЕННЫМИ В

ГИПЕРКУБЫ

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

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

00345 1262

Москва-2008

003451262

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

Научный руководитель: доктор физико-математических наук,

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

Официальные оппоненты: доктор физико-математических наук,

вед. научный сотрудник ИСА РАН Шоломов Лев Абрамовичу

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

Ведущая организация: Институт прикладной математики РАН

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

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

Автореферат разослан_ /у октября 2008 г.

Ученый секретарь диссертационного совета профессор

_Трифонов Н.П.

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

Актуальность темы.

Основной задачей теории синтеза управляющих систем

1 2 з

являет-

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

Во многих случаях схема, вычисляющая заданную функцию, подвергается дальнейшей "геометрической" реализации, то есть вложению в некоторую геометрическую структуру. При этом критерием оптимальности схемы, как правило, является не ее "обычная" сложность, а функционал, отражающий размерность геометрической структуры, в которую данную схему удалось вложить. Основными классами схем, в которых обычно реализуются ФАЛ, являются контактные схемы и схемы из функциональных элементов (СФЭ)3, а в последнее время - двоичные решающие диаграммы (BDD). В качестве структур, в которых происходит геометрическая реализация схем выступают, как правило, 2-х и 3-х мерные прямоугольные решетки4, и, в частности, клеточные схемы5, а в последнее время - единичный булев куб или, иначе, гиперкуб. С геометрической точки зрения единичный куб представляет собой прямоуголь-

IShannon С.Е. The syntesis of two-terminal switching circuits. Bell Syst. Techn. J. 1949. V. 28. №1. P. 59-98.

2Яблонский С.В. Основные понятия кибернетики - в кн. Проблемы кибернетики, вып. 2, М.: Наука, 1959, с.7-38.

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

4 Ложкин С.А. Ли Да Мин, О некоторых оптимальных вложениях двоичных и троичных деревьев в плоские прямоугольные решетки, Вестн. Моск. ун-та, сер. 15. Вычисл. матем. и киберн. 1995. №4. С 49-55.

6Шкаликова, Н. А. О реализации булевых функций схемами из клеточных элементов, Математические вопросы кибернетики, вып. 2, М.: 1982.- С. 177-197.

ную решетку, значность которой равна 2, а размерность может расти. Обобщением единичного куба являются fc-значные кубы (к = 3,4,...).

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

Имеется большое число работ, посвященных вложениям различных графов в гиперкубы. Так, исследовано вложение одномерных (линейка, кольцо) и двухмерных (решетка, тор) 6 структур параллельных программ в регулярные структуры и в частности, в гиперкуб. Показано, что в гиперкуб размерности к могут быть эффективно вложены многие типы графов со степенями вершин, равными константе и количеством ребер порядка 0(2к)7.

Одной из самых активно изучаемых задач в области вложения графов является задача вложения различных видов деревьев в единичные кубы. Так, было показано, что полные двоичные n-ярусные деревья можно гомеоморфно вложить в единичный куб размерности (n + 1) 8.

Рассматриваются и вложения гиперкубов в различные графы. Получены 9 10, например, оценки некоторых параметров прямоугольных решеток, допускающих вложение в них гиперкубов, рассмотрена проблема вложения n-мерного куба в прямоугольные решетки с 2" вершинами и

др.

Геометрическая реализация заданного графа (схемы) G, то есть его вложение в ту или иную структуру (граф) S, происходит, как правило, в

6М. Y. Chan. Embedding of Grids into Optimal Hypercubes, SIAM J. Computing 20(5): 834-864,1991.

7Ajay K. Gupta, Susanne E. Hambrusch. Multiple Network Embedding into Hypercubes, J. Parallel Distrib. Comput. 19(2): 73-82 (1993).

8S. Bhatt and I. C. F. Ipsen. How to Embed Trees in Hypercubes, Research Report YALEU/DCS/RR-443, Yale University, Dept. of Computer Science, 1985.

9Bezrukov, S.L., Chavez, J.D., Harper, L.H., Rottger, M., Schroeder, U.P. The Congestion of n-Cube Layout on a Rectangular Grid, Disc. Math., Vol. 213, 2000, pp. 13-19.

10Bezrukov, S.L., Chavez, J.D., Harper, L.H., Rottger, M., Schroeder, U.P. Embedding of hypercubes into grids, Proc. of the 23rd International Symposium on Mathematical Foundations of Computer Science, MFCS'98, Lecture Notes in Computer Science, Springer Verlag, Berlin, 1998.

два этапа. На первом этапе — этапе "размещения". — вершинам графа G сопоставляются "моделирующие" их вершины или группы вершин графа

з. На втором этапе — этапе "проведения соединений" — ребрам графа G сопоставляются моделирующие их цепи или другие специальные подграфы графа S. Заметим, что в ряде моделей геометрической реализации

и, в частности, в модели клеточных схем эти этапы могут не разделяться. В то же время при решении задачи топологического синтеза СБИС, которая сводится к вложению графа схемы в плоские прямоугольные решетки, эти этапы — этап размещения и этап трассировки, — как правило, отделяются друг от друга.

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

Исследование вопросов сложности реализации ФАЛ схемами, вложенными в гиперкубы, а также вопросов вложения в них различных графов интересно не только с теоретической точки зрения. Архитектура единичного куба хорошо подходит для моделирования различных параллельных алгоритмов. Вложения различных графов в гиперкубы могут быть полезны также в области топологического синтеза схем, химии и нанотехнологиях п. Так, например 12, исследованы вложения некоторых реализованных на плоскости планарных графов, применяемых в химии,

"S. Yanushkevich, V. Shmerko, S. Lyshevski. Logic Design of NanoICs, CRC Press, 2004.

12M. Деза, M. И. Штогрин. Вложение химических графов в гиперкубы, Матем. заметки, 2000, 68:3, 339-352.

в многомерные кубы или кубические решетки с сохранением или же удвоением всех расстояний.

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

Цель диссертации.

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

Для указанной меры сложности схем в классе ВББ и в классе СФЭ над произвольным конечным полным базисом вводится соответствующая функция Шеннона, равная минимальной размерности гиперкуба, допускающего вложение схемы из соответствующего класса для самой "сложной" ФАЛ от п переменных.

В работе ставятся следующие основные задачи:

• Разработка асимптотически оптимальных методов синтеза схем из

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

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

• Получение нижних и верхних оценок функции Шеннона в указанных классах схем.

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

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

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

• Получены нижние и верхние оценки функции Шеннона в указанных классах схем. Доказано, в частности, что эти функции с точностью до аддитивной константы равны п — [log log nj. 13

Аналогичные результаты получены и для fc-значных кубов.

Научная новизна.

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

"В работе через |aj (через [о]) обозначается ближайшее снизу (соответственно сверху) к числу а целое число, а все логарифмы берутся по основанию 2.

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

Теоретическая и практическая ценность.

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

Методы исследования.

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

Апробация работы и публикации.

По теме диссертации опубликовано 8 печатных работ. Результаты работы докладывались на семинарах кафедры математической кибернетики факультета ВМиК МГУ. Кроме того, результаты работы были представлены на следующих конференциях и школах-семинарах:

• XIV международная школа-семинар "Синтез и сложность управляющих систем" (Нижний Новгород, 2003)

• XV международная школа-семинар "Синтез и сложность управляющих систем" (Новосибирск, 2004)

• VI международная конференция "Дискретные модели в теории управляющих систем" (Москва, 2004)

• XVI международная школа-семинар "Синтез и сложность управляющих систем" (Санкт-Петербург, 2006)

• IX международный семинар "Дискретная математика и ее приложения" (Москва, 2007)

Структура и объем диссертации.

Диссертация состоит из введения, двух глав и библиографии. Объем диссертации составляет 85 страниц. Библиография включает 38 наименований.

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

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

Напомним основные понятия, связанные с реализацией ФАЛ с помощью ВББ или СФЭ и вложениями ВББ или СФЭ в гиперкубы. Для целых чисел а и Ь множество всех тех целых чисел для которых а<]<Ъ, называется отрезком и обозначается через [а, 6] = [а, Ь+1) = (а — 1,6] = {а, ...,Ь}.

Пусть В = {0,1} и Вп — п-ая декартова степень множества В, -единичный п-мерный куб (гиперкуб), являющийся областью определения ФАЛ /:Вп —*В от булевских переменных (БП) х = (ху,..., хп).

Множеству Вп соответствует граф, состоящий из 2" вершин и п2™-1 ребер, такой, что каждой вершине этого графа приписан один из двоичных наборов куба Вп, и две вершины соединены между собой ребром

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

Пусть <71, (72) ог - фиксированная система чисел из 0 и 1 и заданы целые числа ¿х,..., гг такие, что 1 < ¿1 < ¿2 < ... < гг < п. Множество всех вершин (аь ..., а„) куба Вп, для которых

= = с72,...,агГ = егг,

называется гранью или подкубом размерности (п — г), причем переменные называются при этом фиксированными, а остальные переменные - свободными переменными этой грани.

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

Обобщением единичного п-мерного куба является £-значный п-мерный куб ЕЦ = (Ек)п, где Ек = {0,..., к - 1}.

Двоичная решающая диаграмма от БП х = (хх,... хп) - это ориентированный ациклический граф £ = £(я) с одним истоком, в котором каждому стоку приписывается либо 0, либо 1, а каждой вершине, отличной от стока, приписывается БП х^ (г е [1, п]) и предполагается, что из такой вершины выходят два ребра, одно из которых помечено символом О, а другое символом 1.

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

Заметим, что любой набор а—{а\,. .. ап) из Вп задает в ВББ Е(х) путь Се (а), который начинается в истоке £ и, проходя через вершину с

пометкой Xi, следует дальше по дуге с пометкой o¡ до тех пор, пока не достигнет одного из стоков Е. Считается, что BDD £(ж) реализует ФАЛ f(x), которая принимает значение а, а ЕВ, на наборе а, а £ В", тогда и только тогда, когда путь Се (а) заканчивается в стоке с пометкой а. Легко видеть, что любая ФАЛ f(x) может быть реализована с помощью BDD Е/, получающейся из полного n-ярусного двоичного дерева ребра которого ориентированы от корня к листьям, в результате приписывания всем его вершинам г-го яруса (г € [1, гг]) БП a:¡, и нанесения на каждый его лист, соответствующий пути C-z{a), где а £ Вп, пометки f{a). Заметим, что указанная BDD, по существу, представляет собой контактное дерево от БП х и моделирует совершенную ДНФ ФАЛ /. Двоичные решающие диаграммы были введены в рассмотрение в 1959 г. Lee C.Y. 14

Традиционной моделью, в рамках которой чаще всего происходит реализация ФАЛ, являются СФЭ над тем или иным базисом3. В диссертации рассматриваются СФЭ над "стандартным" базисом Бо = { & , V, -■}, мультиплексорным базисом Бм = {fi(x, yo, yi), 0,1}, который тесно связан с понятием BDD, а также СФЭ над произвольным конечным полным базисом Б.

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

Гомеоморфным вложением графа G' в граф G" называется отображение, задающее изоморфизм некоторого подразбиения G' графа G' на

"Lee С. Y., Representation of switching circuits by binary decision programs, BSTJ. 1959. 38. N4. P. 985-1000.

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

Квазигомеоморфное вложение ориентированного графа С? без параллельных дуг в неориентированный граф Я понимается как инъективное отображение множества максимальных по включению пучков исходящих дуг графа С?, имеющих общую начальную вершину, во множество т. н. транзитных поддеревьев графа Н такое, что:

1) начальная вершина каждого указанного пучка переходит в корень, а конечные вершины его дуг т в листья соответствующего транзитного поддерева;

2)'различные транзитные поддеревья не имеют общих внутренних, то есть отличных от корня и листьев, вершин.

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

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

Заметим, что гомеоморфные вложения являются частным случаем квазигомеоморфных и что любую СФЭ всегда можно вложить квазиго-меоморфным образом в единичный куб достаточно большой размерности.

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

Di,...,Dn таких, что все вершины цвета г, г 6 [1, тг], являются листьями Д. Частным случаем этой задачи, рассмотренным в данной работе, является задача построения системы одноцветных связывающих деревьев в гиперкубе, подкуб которого раскрашен произвольным образом в различные цвета.

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

Обычным образом значение рассматриваемого функционала сложности определяется для произвольной ФАЛ /, а затем вводится функция Шеннона R(n) (соответственно Яв(п)), которая равна минимальной размерности единичного куба, допускающего для любой ФАЛ f(x 1,..., хп) гомеоморфное вложение реализующей её BDD (соответственно квазиго-меоморфное вложение реализующей ее СФЭ в базисе Б). Аналогично определяется функция Шеннона R(ktn) (соответственно R%(k,n)), которая равна минимальной размерности /с-значного куба, допускающего для любой ФАЛ f(xi,...,x„) гомеоморфное (соответственно квазиго-меоморфное) вложение реализующей её BDD (соответственно СФЭ в базисе Б).

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

В параграфе 1.1 вводится ряд определений, связанных с понятием

гиперкуба и построением в нем простых циклов, изучается вложение единичных кубов в Л-значные кубы.

Доказываются следующие леммы.

Лемма 1.1.1. Пусть единичный куб Вп разделен на 2т параллельных подкубов бь..., размерности (п — т). Тогда в кубе Вп найдутся 2п~т непересекающихся простых циклов длины 2т, каждый из которых последовательно проходит через все эти подкубы в одном и том же порядке.

Лемма 1.1.2. В к-значный куб ЕЦ: можно гомеоморфно вложить единичный куб

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

Лемма 1.2.1. Существует гомеоморфное вложение дерева в куб Вп+1, при котором в Вп+1 найдутся 2п таких не имеющих общих вершин ребер, что в каждом из них ровно одна вершина является образом некоторого листа .

Лемма 1.2.2. Для любого п и любых различных вершин VI,..., Уп,Уп+1 из Вп существует гомеоморфное вложение Zn в Вп, основными вершинами которого являются вершины VI,..., ьп,уп+\, причем вершина уп+1 является образом стока 20*.

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

Лемма 1.3.1. Вершины единичного куба В2*-1, к — 1,2,..., можно раскрасить в 2к цветов пронумерованных числами 0,..., [2к - 1) так, что все вершины любого шара радиуса 1 этого куба будут раскрашены в разные цвета.

Полученную при доказательстве леммы раскраску единичного куба размерности (2^ — 1), будем называть его стандартной раскраской, а стандартную раскраску и любую раскраску, полученную из нее путем

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

Лемма 1.3.2. Специальная раскраска вершин куба В2*-1 порождает специальную раскраску вершин любого из его подкубов размерности (21 - 1), 1 < I < к, свободными БП которого являются первые (21 - 1) БП исходного куба. При этом соседним подкубам указанного вида соответствуют различные (непересекающиеся) отрезки цветов.

Пусть единичный куб В2*-1 раскрашен специальным образом в цвета О,..., (2к — 1) и 1 < т < 2к. Присвоим вершинам куба, раскрашенным в цвета (т—1),..., (2к—1) цвет (т-1) и полученную раскраску куба В2к~1 будем называть его специальной раскраской в т цветов. Под специальной раскраской куба Вп в т цветов, где 1<т<2кик = [1о§(п + 1)], будем понимать раскраску, которая получается в результате его разбиения на параллельные подкубы размерности (2к — 1), и их специальной раскраски одинаковым образом (т. е. так, чтобы раскраска одного под-куба могла бы быть получена из раскраски другого параллельным переносом) в т цветов. При этом по умолчанию будем предполагать, что т = 2к.

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

Лемма 1.3.3. Пусть единичный куб Вп+2 разбит на 4 параллельных подкуба С?2, £?з, (?4 размерности пив подкубе С?1 имеется специальная раскраска его вершин, а в подкубе С?4, находящемся на расстоянии 2 от (?1, задана произвольная раскраска вершин в те же самые цвета. Тогда в графе Вп+2 найдется система из непересекающихся поддеревьев,, корнями которых являются вершины подкуба (?!, а множество листьев этой системы деревьев совпадает с множеством вершин подкуба Gi1 причем цвет листьев каждого дерева совпадает с цветом его корня.

Лемма 1.3.4. Пусть в единичном кубе Вп задана цепь из I параллельных подкубов С = ...,67) размерности г, где 1 < г < п и 1 < I < 2^п~Т\ одинаково раскрашенных специальным образом в цвета

О,..., (2к — 1), к = [1о§(г +1)]. Тогда для любого в, 1 < й < 2к~1, в графе этой цепи подкубов можно выделить т, то = з2Т~к, непересекающихся простых цепей куба Вп длины р, р = — 1\, каждая из которых начинается в подкубе С?1 с вершины раскрашенной в цвет с номером из отрезка [0, в — 1] и не проходит через вершины, раскрашенные в цвета с номерами (2к - в),..., (2к — 1).

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

Теорема 1.4.1. Если в подкубе размерности п единичного куба Вп+5 каждая вершина раскрашена в один из п цветов, то в этом кубе существует система одноцветных связывающих деревьев.

Доказательство данной теоремы состоит из двух этапов. На первом этапе в единичном кубе Вп+5, подкуб К размерности п которого раскрашен произвольным образом в п цветов, пронумерованных числами отрезка [0, та), находятся два параллельных подкуба К' и К" размерности п, допускающие специальную раскраску своих вершин в цвета из отрезков [0,2й) и [2Ь,2*+1), где к = + 1)_], соответственно, и систему Т>, состоящую из непересекающихся поддеревьев куба, такие, что:

1) листьями каждого дерева из V являются вершины подкуба К, раскрашенные в один и тот же цвет, а корнем — вершина подкуба К' или К", раскрашенная в цвет его листьев;

2) каждая вершина подкуба К принадлежит одному из этих поддеревьев.

Таким образом, произвольная раскраска вершин подкуба К куба Вп+Ь "сводится" к специальной раскраске вершин подкубов К' и К" этого куба.

На втором этапе в кубе Вп+Ь находятся непересекающиеся подграфы-деревья Д>,...,£)„_!, такие, что листьями дерева Д, г = 0, ...,(п - 1), являются все корни поддеревьев из множества Т>, раскрашенные в цвет г. Тем самым, построена требуемая в условии теоремы система одноцветных связывающих деревьев.

Для доказательства теоремы 1.4.1 используется следующая лемма.

Лемма 1.4.1. Пусть единичный куб В2*+2, к = 1,2,..., разбит, на 8 параллельных подкубов G\,..., Gs размерности (2fc — 1) и подкуб G\ раскрашен специальным образом. Тогда в кубе S2*+2 найдутся 2к непересекающихся поддеревьев Dq, D\,...., ZV-i таких, что любая вершина подкуба Gi, раскрашенная в цвет j, j 6 [0,2fc - 1], является листом дерева Dj.

В главе 2 разработаны оптимальные методы реализации произвольных ФАЛ вложенными в гиперкубы СФЭ и BDD и, в частности, получены оценки, устанавливающие поведение для введенных выше функций Шеннона R{n), Дв(п) с точностью до слагаемого 0(1).

В параграфе 2.1 устанавливаются некоторые предварительные, основанные на теореме 1.4.1, верхние оценки для функций Шеннона R(n) и Дв0(п)) доказываются соответствующие мощностные нижние оценки и изучается вложение BDD и СФЭ в fc-значные кубы.

Лемма 2.1.1. Для функции Шеннона Rb0(ti) справедлива следующая верхняя оценка:

RB0{n) <п - [loglognj + 8

Лемма 2.1.2. Для функции Шеннона R(n) справедлива следующая верхняя оценка:

R(n) <п - [log log nj +8.

Теорема 2.1.1. Для функций Шеннона R(n, к) и Rb(ti, к) справедливы следующие нижние оценки:

n-loglogn-Iog3-Q(l) log к

Г-Щ-

где ев — константа, зависящая от базиса.

Теорема 2.1.2. Для функций Шеннона R(n,k) и RB0(n,k) справедливы следующие верхние оценки:

п — [log log nj + 8

R(n, k) <

Дб„(М <

LbgfeJ

n - [log log nj + 8 [top] '

В параграфе 2.2 рассматриваются специальные представления, использующие моделирование ФАЛ с помощью переменных на компонентах разбиения единичного куба. На основе этих представлений разрабатываются методы синтеза BDD и их вложения в единичные кубы, доказывается соответствующая верхняя оценка функции Шеннона R(n).

Теорема 2.2.1. Для функции Шеннона R(n) справедлива следующая верхняя оценка:

R(n) <п - [log log nj + 4.

Доказательство данной теоремы состоит из 2 этапов. На первом этапе на основе специального формульного представления заданной ФАЛ строится реализующая ее BDD. На втором этапе осуществляется вложение этой BDD в единичный куб соответствующей размерности.

В параграфе 2.3 рассматривается метод получения улучшенной верхней оценки функции Шеннона для BDD.

Теорема2.3.1. Для функции Шеннона R(n) справедлива следующая верхняя оценка:

R(n) <n— [log log nj + 1

Для получения улучшенной верхней оценки используются вложения некоторых специальных типов графов в гиперкубы.

В параграфе 2.4 доказывается верхняя оценка функции Шеннона Дв(п) для СФЭ.

Сначала рассматривается СФЭ в мультиплексорном базисе Бм = {хуоV xyi, 0,1}, который тесно связан с понятием BDD.

Теорема 2.4.1. Для функции Шеннона справедлива

следующая верхняя оценка:

ДбДп) < п- [log log nj +8.

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

Теорема 2.4.2. При п > Cg, где dB - константа, зависящая от базиса В, для функции Шеннона R$(ri) справедлива следующая верхняя оценка:

Rb (п) <п - [log log nj + 15.

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

1. Седелев О.Б. Верхняя и нижняя оценки сложности реализации функций алгебры логики ВВВ, вложенными в п-мерный куб. Тезисы XIV Международной школы-семинара «Синтез и сложность управляющих систем». — Нижний Новгород: 2003. — С. 70-73.

2. Седелев О.Б. Сложность реализации функций алгебры логики схемами, вложенными в гиперкуб., Сборник тезисов лучших дипломных работ 2004 года. — М.: Издательский отдел факультета ВМиК МГУ. 2004.-С. 63-64.

3. Седелев О.Б. О сложности реализации функций алгебры логики схемами из функциональных элементов в мультиплексорном базисе, вложенными в единичный куб. Тезисы XV Международной школы-семинара «Синтез и сложность управляющих систем». — Новосибирск: Изд-во Ин-та матем. им. С.Л. Соболева. 2004.

4. Седелев О.Б. О сложности реализации функций алгебры логики схемами из функциональных элементов, вложенными в единичный куб. Дискретные модели в теории управляющих систем: VI международная конференция. Труды.— М.: Издательский отдел факультета ВМиК МГУ. 2004. - С. 73-76.

5. Седелев О.Б. О реализации функций алгебры логики Д£Ш, вложенными в единичный куб.. Тезисы XVI Международной школы-семинара «Синтез и сложность управляющих систем». — М.: Изд-во механико-математического факультета МГУ. 2006.

6. Ложкин С.А., Седелев О.Б. О реализации функций алгебры логики ВИБ, вложенными в единичный куб. Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2006. №4. С. 29-35.

7. Седелев О.Б. О реализации функций алгебры логики схемами из функциональных элементов, вложенными в единичные кубы. IX международный научный семинар "Дискретная математика и ее приложения". — М.: Изд-во механико-математического факультета МГУ. 2007.

8. Седелев О.Б. Реализация функций алгебры логики схемами из функциональных элементов, вложенными в единичный куб. Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2008. №1. С. 44-50.

Напечатано с готового ориганал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 13.10.2008 г. Формат 60x90 1/16. Усл.печл. 1,25. Тираж 70 экз. Заказ 571. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Седелев, Олег Борисович

Введение

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

§ 1.1. Единичные кубы, некоторые их подмножества и разбиения.

Вложение единичных кубов в fc-значные кубы.

§ 1.2. Гомеоморфные вложения деревьев и звезд в гиперкубы

§ 1.3. Специальная раскраска вершин гиперкуба на основе кодов

Хэмминга и ее свойства.

§ 1.4. Построение систем одноцветных связывающих деревьев в единичных кубах.

Глава 2. Реализация функций схемами из некоторых классов, вложенными в единичные кубы

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

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

§ 2.3. Улучшенная верхняя оценка функции Шеннона для BDD

§ 2.4. Верхняя оценка функции Шеннона для СФЭ

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

Постановка задачи и общая характеристика работы

Основной задачей теории синтеза управляющих систем (см., например, [11,23,36]) является изучение вопросов оптимальной структурной реализации дискретных функций и, в частности, функций алгебры логики (ФАЛ) или, иначе, булевских функций в различных классах схем. Важным направлением теории синтеза является асимптотический синтез, связанный с изучением поведения так называемой функции Шеннона, которая равна сложности оптимальной реализации с помощью схем из рассматриваемого класса самой сложной ФАЛ от заданного числа переменных, являющегося аргументом этой функции и стремящегося к бесконечности.

Основными классами схем, в которых обычно реализуются ФАЛ, являются контактные схемы и схемы из функциональных элементов (СФЭ) [11], а в последнее время — двоичные решающие диаграммы (BDD) [33]. В качестве структур, в которых происходит геометрическая реализация схем, выступают, как правило, 2-х и 3-х мерные прямоугольные решетки [9], и, в частности, клеточные схемы [1,22], а в последнее время - единичный булев куб или, иначе, гиперкуб. С геометрической точки зрения единичный куб представляет собой прямоугольную решетку, значность которой равна 2, а размерность может расти. Обобщением единичного куба являются Акзначные кубы (к = 3,4,.).

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

Имеется большое число работ посвященных вложениям различных графов в гиперкубы (см., например, [2,12,31]). Так, исследовано вложение одномерных (линейка, кольцо) [21] и двумерных (решетка, тор) [27] структур параллельных программ в регулярные структуры и в частности, в гиперкуб. Показано, что в гиперкуб размерности к могут быть эффективно вложены многие типы графов со степенями вершин, равными константе и количеством ребер порядка 0(2к) [32]. Одной из самых активно изучаемых задач в области вложения графов является задача вложения различи ных видов деревьев в единичные кубы. Так, было показано, что полное двоичное n-ярусное дерево можно гомеоморфно вложить в единичный куб размерности (п + 1) [26].

Рассматриваются и вложения гиперкубов в различные графы. В работах [25,29,30], например, получены оценки некоторых параметров прямоугольных решеток, допускающих вложение в них гиперкубов, и рассмотрена проблема вложения n-мерного куба в прямоугольные решетки с 2П вершинами.

Геометрическая реализация заданного графа (схемы) <7, то есть его вложение в ту или иную структуру (граф) S, происходит, как правило, в два этапа (см., например, [9]). На первом этапе — этапе "размещения — вершинам графа G сопоставляются "моделирующие" их вершины или группы вершин графа S. На втором этапе — этапе "проведения соединений - ребрам графа G сопоставляются моделирующие их цепи или другие специальные подграфы графа S. Заметим, что в ряде моделей геометрической реализации и, в частности, в модели клеточных схем эти этапы могут не разделяться. В то же время при решении задачи топологического синтеза СБИС, которая сводится к вложению графа схемы в плоские прямоугольные решетки, эти этапы — этап размещения и этап трассировки, — как правило, отделяются друг от друга.

Задачу проведения соединений в рассматриваемой структуре часто сводят к задаче построения в ней различных систем связывающих деревьев (см., например, [35]). В данной работе рассматривается один из возможных вариантов этой задачи — задача построения системы т. н. одноцветных свяt зывающих деревьев, состоящая в следующем. Для данного графа, часть вершин которого раскрашена в различные цвета, необходимо построить такую содержащую все раскрашенные вершины графа систему из непересекающихся подграфов-деревьев, что множество листьев каждого из них содержит все вершины" раскрашенные в один цвет. Эта "задача решается в диссертации для единичного куба, в котором вершины его подкуба размерности п раскрашены в п цветов.

Исследование вопросов сложности реализации ФАЛ схемами, вложенными в гиперкубы, а также вопросов вложения в них различных графов интересно не только с теоретической точки зрения. Архитектура единичного куба хорошо подходит для моделирования различных параллельных алгоритмов, а вложения различных графов в гиперкубы могут быть полезны в области синтеза схем, химии и нанотехнологиях [38]. Так, например, в [3] исследованы вложения некоторых реализованных на плоскости планарных графов, применяемых в химии, в многомерные кубы или кубические решетки с сохранением или же удвоением всех расстояний.

Целью данной работы является исследование вопросов синтеза схем из некоторых классов, вложенных в гиперкубы. В ней рассматривается задача вложения некоторых графов в гиперкубы и методы построения в гиперкубах систем одноцветных связывающих деревьев, а также задача реализации ФАЛ с помощью BDD и СФЭ, вложенных в единичный куб, которая является частным случаем задачи о геометрической (структурной) реализации дискретных функций. В качестве меры сложности такой реализации ФАЛ выбрана минимальная размерность единичного куба, допускающего гомеоморфное вложение некоторой BDD или СФЭ, реализующей эту ФАЛ. В работе вводятся функции Шеннона, которые равны сложности самой "сложной" ФАЛ от п переменных при их реализации указанным образом в классе BDD и классе СФЭ над заданным базисом. Доказано, что эти функции с точностью до аддитивной константы равны п — [loglognj.1

Аналогичные результаты получены и для /г-значных кубов. гВ работе через [aJ (через [а]) обозначается ближайшее снизу (соответственно сверху) к числу о целое число, а все логарифмы берутся по основанию 2.

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

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

Напомним основные понятия2, связанные с реализацией ФАЛ с помощью BDD или СФЭ и вложениями BDD или СФЭ в единичные кубы.

Пусть В — {0,1} и Вп — 71-ая декартова степень множества В, — единичный n-мерный куб {гиперкуб), являющийся областью определения ФАЛ f:Bn —>В от булевских переменных (БП) х = (rri,., жп). Обобщением единичного n-мерного куба является /г-значный n-мерный куб Е^ — где Ek = {0,к — 1}.

Известно, что в ориентированном ациклическом графе [24] всегда есть хотя бы один исток, то есть вершина без входящих в нее ребер и хотя бы один сток, то есть вершина без исходящих из нее ребер, а путь не имеет продолжения тогда и только тогда, когда он заканчивается в стоке.

Двоичная решающая диаграмма от БП х = (х\,. ,хп) - это ориентированная ациклическая сеть (схема) £ = Е(ж) с одним истоком, являющимся ее входом, в которой каждый сток является выходом £ и ему приписывается либо 0, либо 1, а каждой вершине, отличной от стока, при

2Те понятия, которые не определены в данной работе, могут быть найдены в [8,11,24]. писывается БП Xi (г £ [1>гс]), причем предполагается, что из такой вершины выходят два ребра, одно из которых помечено символом 0, а другое символом 1 3. Сложность L(Е) BDD Е равна числу вершин Е, отличных от ее выходов. Те BDD, которые имеют единственный сток с пометкой 1 и единственный сток с пометкой 0, будем называть приведенными по выходам BDD.

Напомним, что любой набор a=(ai,., ап) из Вп задает в BDD Е(х) путь Се(ск), который начинается в истоке Е и, проходя через вершину с пометкой Xi, следует дальше по дуге с пометкой aj до тех пор, пока не достигнет одного из стоков Е. Считается что BDD Е(х) реализует ФАЛ f{x), которая принимает значение <т, о £В, на наборе а, а £ Вп, тогда и только тогда, когда путь Се (а) заканчивается в стоке с пометкой и. Под сложностью L(f) ФАЛ / при реализации ее в классе BDD будем понимать минимальную сложность тех BDD, которые реализуют ФАЛ /.

Заметим, что BDD, по существу, представляют собой специальный частный случай контактных схем ( [8,11]), как с точки зрения их структуры, так и с точки зрения их функционирования. Две BDD, реализующие равные ФАЛ, будем называть эквивалентными. Легко видеть, что любая BDD эквивалентна приведенной по выходам BDD той же сложности.

Двоичные решающие диаграммы были введены в рассмотрение в 1959 г. Lee C.Y. [33]. Им же были получены следующие оценки для функции Шеннона L(n), которая равна сложности самой "сложной" ФАЛ от п БП при их реализации в классе BDD:

2 п 2п < L(n) <4--1.

2 п~ к J ~ п

Позднее Кузьмин В.А. установил [4], что:

3В том случае, когда эти ребра параллельны, то есть идут в одну и ту же вершину, допускается их замена одним непомеченным ребром , а также удаление БП с той вершины, из которой они выходят

L(n) = -( 1±5(1)), а Ложкин С.A. [6,7] получил для функции Шеннона L(ri) асимптотические оценки высокой степени точности: т( \ 2"(л л. -vlogn^

Традиционной моделью, в рамках которой чаще всего происходит реализация ФАЛ, являются СФЭ над некоторым конечным полным базисом Б. Под сложностью 1>б(/) ФАЛ / при реализации ее в классе СФЭ в базисе Б будем понимать минимальную сложность СФЭ в базисе Б, которые реализуют ФАЛ /. Известно [8,11], что для функции Шеннона Ьв(п), которая равна сложности самой "сложной" ФАЛ от п БП при их реализации в классе СФЭ в базисе Б, имеет место асимптотическое равенство

2 п

Ьв(п) ~ рв—, п где рв — константа, зависящая от базиса. В работах [6, 7] для функции Шеннона Ьв(п) были получены асимптотические оценки высокой степени точности. Аналогичные оценки были установлены и для функции Шеннона, характеризующей глубину СФЭ (см., например, [5,8])

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

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

G в вершины и простые цепи графа G: которые называются основными вершинами и транзитными цепями данного отображения (подразбиения) соответственно.

Гомеоморфным вложением графа G' в граф G" называется отображеN ние, задающее изоморфизм некоторого подразбиения G' графа G' и графа Gкоторый либо является подграфом графа G", либо может быть получен из такого подграфа в результате придания ориентации некоторой части его неориентированных ребер. При этом основными вершинами и транзитными цепями рассматриваемого вложения считаются те вершины и цепи графа G", которые при указанном изоморфизме являются образами основных вершин и транзитных цепей подразбиения G' соответственно. Остальные вершины графа G" называются свободными вершинами указанного вложения. Заметим, что любой граф G можно гомеоморфно вложить в единичный куб Вп при достаточно большом п.

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

1) начальная вершина каждого указанного пучка переходит в корень, а конечные вершины его дуг - в листья соответствующего транзитного поддерева;

2) различные транзитные поддеревья не имеют общих внутренних, то есть отличных от корня и листьев, вершин.

Пусть задан граф G, часть вершин которого раскрашена в цвета {1, .,п}. Будем говорить, что в графе G существует система одноцветных связывающих деревьев, если в нем найдутся п непересекающихся деревьев Di,., Dn таких, что все вершины цвета г, i £ {1,.,п}, являются листьями Di. Частным случаем этой задачи является задача построения системы одноцветных связывающих деревьев в гиперкубе, подкуб которого раскрашен произвольным образом в различные цвета (см. § 1.4).

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

Обычным образом значение рассматриваемого функционала сложности определяется для произвольной ФАЛ /, а затем вводится функция Шеннона R(n) (соответственно Rb(ti)), которая равна минимальной размерности единичного куба, допускающего для любой ФАЛ f(x 1,., хп) го-меоморфное вложение реализующей её BDD (соответственно квазигомео-морфное вложение реализующей ее СФЭ в базисе Б). Аналогично определяется функция Шеннона R(k,n) (соответственно Rb(k,n)) - которая равна минимальной размерности /г-значного куба, допускающего для любой ФАЛ f(xi,., хп) гомеоморфное (соответственно квазигомеоморфное) вложение реализующей её BDD (соответственно СФЭ в базисе Б).

Основными результатами работы являются:

1) разработка техники вложения некоторых графов в гиперкубы, а также методов построения в единичных кубах систем одноцветных связывающих деревьев и, в частности, доказательство того, что если в подкубе размерности п единичного куба Вп+Ъ каждая вершина раскрашена в один из п цветов, то в этом кубе указанная система существует;

2) разработка оптимальных методов реализации произвольных ФАЛ вложенными в гиперкубы СФЭ и BDD и, в частности, получение оценок, устанавливающих поведение для введенных выше функций Шеннона R(n), Re(tl) с точностью до слагаемого 0( 1).

Полученные при этом оценки имеют вид: п — log log п - log 3 — о(1)1 < R{n) <п — [log log nj + 1 (1) и n - [log log nj - сБ < Яв(п) <n - [log log nj + 15, (2) причем верхняя оценка (2) справедлива при п > Cg, где сб и с'в — некоторые константы, зависящие от базиса.

Так, для мультиплексорного базиса Бм = {/i(x, уа, yi), 0,1}, где fi(x, г/О) У\) = %Уо и стандартного базиса Бд = { & , V, ->} справедливы оценки: п - log log п - log 3 - о(I)] < ЛБДп) <п - [log log тт.J + 8 (3) п - log log 71 - log3 - o( 1)1 < RB0(n) <n - [log log 72 J + 8. (4)

Кроме того, для функций Шеннона, связанных с вложением BDD и СФЭ в базисе Б в &-значные кубы, получены следующие оценки: n-loglogw- log3-o(l)-. < га - LloglogwJ + 1 log/с [log &J и, в случае п> с'Б, п - log log n-cBl .D/, ч ™ ~ [log log nj + 15 г-i^k-1 ^ n) *-[Wfcj-• (6)

При этом для мультиплексорного базиса Бм и стандартного базиса Бо оценки (5) и (6) имеют вид: п - log log n- log 3-о(1)-, n- [log log nj +8 Г-l^k-1 - НВ^П) ~-[b^]- (?) и rn — log log n — log3 — o(l)1 . , n- [log log nj +8 r-ъ£к-1 - КбЛК n) ~-[iZ^ki-• (8)

Конструкции, с помощью которых реализованы вложения графов (BDD, СФЭ, цепей и звезд) в гиперкубы, а также методы построения в гиперкубах систем одноцветных связывающих деревьев и способы формульного представления ФАЛ, рассмотренные в данной работе, могут быть использованы для геометрической реализации ФАЛ или систем ФАЛ в том случае, когда в качестве геометрической структуры, в которую необходимо осуществить вложение, выступают графы, близкие к гиперкубу или допускающие "хорошее" вложение гиперкуба.

Основные результаты, полученные в диссертации, опубликованы в работах [10,14-20].

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Седелев, Олег Борисович, Москва

1. Альбрехт А. О. О схемах из клеточных элементов // Проблемы кибернетики. - 1975. — Вып. 33. - С. 209-214.

2. Деза М., Штогрин М. Изометрические вложения полуправильных многогранников, разбиений и им дуальных в гиперкубы и кубические решетки // УМН. 1996. - Т. 51, № 6. - С. 199-200.

3. Деза М., Штогрин М. Вложение химических графов в гиперкубы. // Матем. заметки. — 2000. — Т. 68, № 3. — С. 339-352.

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

5. Ложкин С. А. О глубине функций алгебры логики в некоторых базисах // Ann. Univ. Sci. Budapest. Sec. Comput.— 1983. — V. IV.— Pp. 113-125.

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

7. Ложкин С. А. Лекции по основам кибернетики. — ВМиК МГУ, 2004.

8. Ложкин С. А., Ли-Да-Мин. О некоторых оптимальных вложениях двоичных и троичных деревьев в плоские прямоугольные решетки // Вестн. Моск. ун-та, сер. 15. Вычисл. матем. и киберн. — 1995. — № 4. С. 49-55.

9. Ложкин С. А., Седелев О. Б. О реализации функций алгебры логики bdd, вложенными в единичный куб // Вестн. Моск. ун-та, сер. 15. Вычисл. матем. и киберн. — 2006. — № 4. — С. 29-35.

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

11. Никонов В. Г., Шевелев Д. С. Булевы графы и функции // Дискрет.матем. — 1991. — Т. 3, № 4. — С. 51-61.

12. Оре О. Теория графов. М.: Наука, 1982.

13. Седелев О. Б. Верхняя и нижняя оценки сложности реализации функций алгебры логики bdd, вложенными в n-мерный куб // Тезисы XIV Международной школы-семинара "Синтез и сложность управляющих систем". — Нижний Новгород, 2003. — С. 70-73.

14. Седелев О. Б. Сложность реализации функций алгебры логики схемами, вложенными в гиперкуб. // Сборник тезисов лучших дипломных работ 2004 года. — М.: Издательский отдел факультета ВМиК МГУ, 2004. С. 63-64.

15. Седелев О. Б. Реализация функций алгебры логики схемами из функциональных элементов, вложенными в единичный куб // Вести. Моск. ун-та, сер. 15. Вычисл. матем. и киберн. — 2008. — № 1. — С. 44-50.

16. Тарков М. С. Вложение структур параллельных программ в структуры живучих распределенных вычислительных систем // Автометрия. 2003. - Т. 39, № 3. - С. 84-96.

17. Шкаликова Н. А. О реализации булевых функций схемами из клеточных элементов j j Математические вопросы кибернетики, — 1989. — Вып. 2. С. 177-197.

18. Яблонский С. Основные понятия кибернетики // Проблемы кибернетики, вып. 2.— 1959.— С. 7-38.

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

20. Bezrukov S. L. Embedding complete trees into the hypercube // Discrete Appl. Math. 2001. - Vol. 110, no. 2-3. - Pp. 101-119.

21. Bhatt S. N., Ipsen I. C. F. How to embed trees in hypercubes: Research Report 443: inst-yale, 1985.

22. Chan M. Y. Embedding of grids into optimal hypercubes // SI AM J. Comput. 1991. - Vol. 20, no. 5. - Pp. 834-864.

23. Chen W.-K., Stallmann M. F. M. On embedding binary trees into hyper-cubes /7 J. Parallel Distrib. Comput. 1995. - Vol. 24, no. 2. - Pp. 132138.

24. The congestion of n-cube layout on a rectangular grid / Bezrukov, Chavez, Harper et al. // DMATH: Discrete Mathematics. 2000.- Vol. 213. — Pp. 13 - 19.

25. Embedding of hypercubes into grids / S. L. Bezrukov, J. D. Chavez, L. H. Harper et al. // Lecture Notes in Computer Science. — 1998. — Vol. 1450.

26. Fu W. S., Huang H. C.} Sengupta A. On ring embedding in hypercubes with faulty nodes and links // Information Processing Letters. — 1998. — Vol. 68. Pp. 207-214.

27. Gupta А. К., Hambrusch S. E. Multiple network embeddings into hyper-cubes // Journal of Parallel and Distributed Computing. — 1993. — Vol. 19, no. 2. Pp. 73-82.

28. Lee C. Representation of Switching Circuits by Binary-Decision Programs // Bell Systems Technical Journal— 1959.— July. — Vol. 38.— Pp. 985-999.

29. Ostergard P. R. J. On a hypercube coloring problem // J. Comb. Theory Ser. A. 2004. - Vol. 108, no. 2. - Pp. 199-204.

30. Parallel construction of optimal independent spanning trees on hyper-cubes / J.-S. Yang, S.-M. Tang, J.-M. Chang, Y.-L. Wang // Parallel Comput. 2007. - Vol. 33, no. 1. - Pp. 73-79.

31. Yanushkevich S., Shmerko V., Lyshevski S. Logic Design of NanoICs. — CRC Press, 2004.