Методы синтеза и оценки сложности схем с некоторыми структурными ограничениями

• Автор: Коноводов, Владимир Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Москва
• Количество страниц: 109 с. : ил.

Содержание
Введение

1 Синтез формул с ограниченной глубиной альтернирования и схем

из функциональных элементов ограниченной ширины

1.1 Формулы с ограниченной глубиной альтернирования

1.1.1 Вспомогательные определения и утверждения

1.1.2 Верхняя оценка функции Шеннона

1.1.3 Нижняя мощностная оценка функции Шеннона

1.2 Реализация функций из некоторых классов, связанных с конечными грамматиками, формулами глубины альтернирования 3

1.3 Схемы с ограниченной памятью

2 Синтез формул в базисах с прямыми и итеративными переменными

2.1 Некоторые особенности задачи и порядок функции Шеннона
2.2 Сложность формул в базисах, итеративное замыкание которых содержит все монотонные функции
2.3 Асимптотические оценки высокой степени точности для некоторых базисов
Заключение
Литература

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

В диссертации в качестве управляющих систем рассматривается модель схем из функциональных элементов в некоторых конечных базисах и, как частный случай, модель булевых формул. Под сложностью схемы, если это специально не оговорено, понимается число входящих в нее элементов.
Первый результат о поведении функции Шеннона для сложности схем в конечных полных базисах был получен Мюллером в [5] с использованием метода Шеннона [6]. Было показано, что порядок роста указанной функции при стремлении натурального аргумента п к бесконечности равен 2п/п.
Затем О. Б. Лупановым [41 ] был предложен оптимальный метод синтеза схем в произвольных полных конечных базисах. Им же был получен первый результат об асимптотическом поведении функции Шеннона для сложности формул в таких базисах. А именно, была установлена асимптотика функции Шеннона вида

для сложности схем из функциональных элементов, и асимптотика для случая булевых формул [42] вида

Р ■ г1—,
где р — константа, зависящая от базиса, и одинаковая для случая формул и схем в одном базисе.
В дальнейшем в работах С. А. Ложкина [31] уточнялись оценки остаточного члена асимптотического разложения для некоторых функций Шеннона и устанавливались асимптотические оценки высокой степени точности, в которых указывалась асимптотика второго члена этого разложения. Такие оценки были получены для сложности некоторых основных классов схем.
При решении задач синтеза часто требуется учитывать различного рода ограничения на структуру и параметры управляющих систем. Постановка задач в
'Здесь к далее все логарифмы двоичные

Следовательно,
-f MWM =
H Y Y ,5 M !yl
t A pci, |x,| t , t A |X;| Л |^|, |v;|
^й^1ог«ХЬ8й5<-|,й"!й =
tfc IXjl ! Xj ^ t/c t 1^1 i 1^
= “M^~v°E~ j “Mm “,5,151 M =
= |||(Я№)-1оЕ*) + Я(Д).
Лемма доказана. П
Для любого натурального а определим величину Wa как наименьшее нату-

ральное число ж, при котором log1“1 х > 1, т. е. Wa = При этом положим
а раз
Щ) = 2.
Лемма 7. При любых натуральных aux, где ж ^ Wa+i, справедливо неравенство

fc*fc! ylog1“1 (|) y
Доказательство. Полагая ß = | и учитывая то, что /с! > (|)fc , ползшим

fc ^log1““111 ж^ ^xkek /к^“+11ж х /ж^ ß ^ log1“4-11 ж
kkk у logt“! J ^ k2k yiogW (I) j ßj log[a] ß J
Поделив на ж натуральный логарифм последнего выражения, легко убедиться в том, что для доказательства леммы достаточно показать справедливость неравенства

—ln/? + - - - ln ж + lnlog[a+1] ж - ln logt“1 ß 1Пе5 (! 3)

Найдем максимум левой части (1.3) как функции от ß. Если он достигается при ß — В', то из необходимого условия достижения максимума вытекает, что

—2nß' + 1 + 1пж — т-y г-------------------------------------= О,
(logt“1 ßrj (log1“-11 ßij _ (i0g ßi'j inß