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

• Автор: Седелев, Олег Борисович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 85 с. : ил.

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

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

Вложение единичных кубов в /с-зггачные кубы

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

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

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

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

единичных кубах

Глава 2. Реализация функций схемами из некоторых классов, вложенными в единичные кубы
§ 2.1. Вложение некоторых логических схем в единичные кубы и верхние оценки функции Шеннона для размерности этих
кубов. Нижние мощностные оценки
§ 2.2. Верхняя оценка функции Шеннона для размерности единичного куба при вложении ВБО, построенных на основе моделирующих разложений
§ 2.3. Улучшенная верхняя оценка функции Шеннона для ВОБ 61 § 2.4. Верхняя оценка функции Шеннона для СФЭ
Литература

Введение
Постановка задачи и общая характеристика работы
Основной задачей теории синтеза управляющих систем (см., например, [11,23,36]) является изучение вопросов оптимальной структурной реализации дискретных функций и, в частности, функций алгебры логики (ФАЛ) или, иначе, булевских функций в различных классах схем. Важным направлением теории синтеза является асимптотический синтез, связанный с изучением поведения так называемой функции Шеннона, которая равна сложности оптимальной реализации с помощью схем из рассматриваемого класса самой сложной ФАЛ от заданного числа переменных, являющегося аргументом этой функции и стремящегося к бесконечности.
Во многих случаях схема, вычисляющая заданную функцию, подвергается дальнейшей "геометрической" реализации, то есть вложению в некоторую геометрическую структуру. При этом критерием оптимальности схемы, как правило, является не ее "обычная" сложность, а функционал, отражающий минимальную размерность геометрической структуры, в которую данную схему удалось вложить.
Основными классами схем, в которых обычно реализуются ФАЛ, являются контактные схемы и схемы из функциональных элементов (СФЭ) [11], а в последнее время — двоичные решающие диаграммы (ВБО) [33]. В качестве структур, в которых происходит геометрическая реализация схем, выступают, как правило, 2-х и 3-х мерные прямоугольные решетки [9], и, в частности, клеточные схемы [1,22], а в последнее время - единичный бу-
лев куб или, иначе, гиперкуб, С геометрической точки зрения единичный куб представляет собой прямоугольную решетку, значиость которой равна 2, а размерность может расти. Обобщением единичного куба являются /с-значные кубы (к = 3,4
В настоящей работе рассматривается задача асимптотического синтеза, которая связана с реализацией ФАЛ с помощью СФЭ и ВББ, вложенных в прямоугольные решетки ограниченной значности, разрабатываются методы решения этой задачи и исследуется поведение соответствующих функций Шеннона.
Имеется большое число работ посвященных вложениям различных графов в гиперкубы (см., например, [2,12,31]). Так, исследовано вложение одномерных (линейка, кольцо) [21] и двумерных (решетка, тор) [27] структур параллельных программ в регулярные структуры и в частности, в гиперкуб. Показано, что в гиперкуб размерности к могут быть эффективно вложены многие типы графов со степенями вершин, равными константе и количеством ребер порядка 0(2к) [32]. Одной из самых активно изучаемых задач” в области вложения графов является задача вложения различи ных видов деревьев в единичные кубы. Так, было показано, что полное двоичное п-ярусное дерево можно гомеоморфію вложить в единичный куб размерности (п + 1) [26].
Рассматриваются и вложения гиперкубов в различные графы. В работах [25,29,30], например, получены оценки некоторых параметров прямоугольных решеток, допускающих вложение в них гиперкубов, и рассмотрена проблема вложения п-мерного куба в прямоугольные решетки с 2п вершинами.
Геометрическая реализация заданного графа (схемы) (7, то есть его вложение в ту или иную структуру (граф) 5, происходит, как правило, в два этапа (см., например, [9]). На первом этапе — этапе "размещения — вершинам графа О сопоставляются "моделирующие" их вершины или группы
§1.4. Построение систем одноцветных связывающих деревьев в единичных кубах
Для гиперкуба, часть вершин которого раскрашена в определенный набор цветов, рассмотрим задачу построения в нем системы одноцветных связывающих деревьев, то есть системы непересекающихся поддеревьев куба, каждое из которых содержит все раскрашенные вершины одного цвета среди своих листьев и, следовательно, не содержит вершин других цветов.
Т е о р е м а 1.4.1. Если в подкубе размерности п единичного куба Вп+5 каждая вершина раскрашена в один из п цветов, то в этом кубе суш,ествует система одноцветных связывающих деревьев.
Доказательство данной теоремы состоит из двух этапов. На первом этапе в единичном кубе Вп+5, подкуб К размерности п которого раскрашен произвольным образом в п цветов, пронумерованных числами отрезка [О, тт.), найдем два параллельных подкуба К' и К" размерности п, допускающие специальную раскраску своих вершин в цвета из отрезков [0,2к) и 2к, 2'+1), где к — [(п + 1)], соответственно, и систему V, состоящую из непересекающихся поддеревьев куба, такие, что:
1) листьями каждого дерева из V являются вершины подкуба К, раскрашенные в один и тот же цвет, а корнем — вершина подкуба К' или К", раскрашенная в цвет его листьев;
2) каждая вершина подкуба К принадлежит одному из этих поддеревьев.
Таким образом, мы "сведем" произвольную раскраску вершин подкуба К куба Вп+Ъ к специальной раскраске вершин его подкубов К' и К".
На втором этапе найдем в кубе Вп+Ь непересекающиеся подграфы-деревья Ц)> , Аг-1: такие, ЧТО ЛИСТЬЯМИ дерева Бг, г 6 [0, п) являются все корни поддеревьев из множества V, раскрашенные в цвет г. Тем самым, будет построена требуемая в условии теоремы система одноцветных