Некоторые вопросы синтеза параллельных схем Сергеев Игорь Сергеевич

Короткий опис

Сергеев, Игорь Сергеевич.
Некоторые вопросы синтеза параллельных схем : диссертация ... доктора физико-математических наук : 01.01.06 / Сергеев Игорь Сергеевич; [Место защиты: ФГБОУ ВО «Московский государственный университет имени М.В. Ломоносова»]. - Москва, 2021. - 287 с. : ил.
Оглавление диссертациидоктор наук Сергеев Игорь Сергеевич
Содержание
1 Общее введение
2 Сложность и глубина формул. Формулы
для симметрических булевых функций
2.1 Основные понятия и известные факты
2.2 Глубина и сложность монотонных формул
2.2.1 Расщепление монотонных функций
2.2.2 Нижняя оценка
2.3 Конструктивные верхние оценки для симметрических функций. Модулярный метод
2.3.1 Описание метода
2.3.2 Троичные компрессоры
2.3.3 Двоичные компрессоры
2.3.4 Оценки
2.3.5 Приложение. Доказательство технических лемм
2.4 Неконструктивные верхние оценки для симметрических функций. Метод приближений
2.4.1 Формулы для приближенного суммирования
2.4.2 Формулы для симметрических функций
2.5 Синтез формул для МОП-функции
2.5.1 Простые формулы в базисе Во
2.5.2 Простые формулы в базисе В2
2.5.3 Алгебраический метод
2.5.4 Формулы в расширенной кодировке
о
2.5.5 Оценка глубины оператора МОЦ; Во
2.5.6 Оценка глубины оператора моб; в базисе В2 ... ■
2.6 Сложность формул в к-арных базисах
2.6.1 Экспонента Храпченко и меры сложности двудольных графов
2.6.2 Оценки для экспонент сложности в общем случае
2.6.3 Уточнение нижней оценки экспоненты Храпченко при
к =
2.6.4 Верхние оценки сложности
3 Линейные схемы ограниченной глубины
3.1 Введение
3.2 Асимптотические оценки сложности для классов булевых и целочисленных матриц при ограничении глубины
3.2.1 Приближение
3.2.2 Схемы глубины
3.2.3 Схемы глубины
3.2.4 Вычисление матриц с быстро растущими коэффициентами
3.3 Экстремальные расхождения между линейными мерами сложности булевых матриц
3.3.1 Редкие множества. Погружение многомерного редкого множества в пространство меньшей размерности
3.3.2 Известные методы получения нижних оценок сложности
3.3.3 Оценки OR/XOR отношений в некоторых классах матриц
3.3.4 Пример последовательности матриц с растущим XOR/OR отношением в глубине
OR
3.4 Нижние оценки монотонной сложности функции T^
3.4.1 Общая нижняя оценка
3.4.2 Нижняя оценка в классе схем глубины
4 Параллельные префиксные схемы
4.1 Введение
4.2 Предварительные понятия
4.3 Нижняя оценка
4.3.1 Граф связей
4.3.2 Стоимость графа
4.3.3 Множество допустимых графов. Гиперпары
4.3.4 Стоимость множества подграфов композиции корневых деревьев
4.3.5 Стоимость множества подграфов гиперпары
4.3.6 Оптимальность гиперпары
4.3.7 Собственно нижняя оценка
4.4 Верхняя оценка
4.5 Реализация с почти минимальной глубиной
4.6 Префиксные XOR-схемы
4.7 Замечания о префиксных схемах с ограниченным ветвлением элементов
5 Схемы ограниченной глубины из
многовходовых элементов
5.1 Введение
5.2 Нижние оценки сложности
5.3 Простые методы синтеза
5.4 Специальные разбиения булева куба
5.5 Синтез с глубиной
5.6 Синтез схем над базисом Uж
5.6.1 Специальные системы функций
5.6.2 Многоярусное представление
5.6.3 Верхняя оценка
6 Сложность сортировки
6.1 Введение
6.2 Метод бинарных вставок
6.3 Предварительные сведения
6.4 Общий метод
6.5 Универсальная стратегия
6.6 Сортировка
7 Заключение
Список литературы
Работы автора по теме диссертации