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

• Автор: Окольнишникова, Елизавета Антоновна
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2007
• Место защиты: Новосибирск
• Количество страниц: 185 с.

Глава 1. Обзор результатов по сложности ветвящихся

программ

§ 1.1. Определения, предварительные сведения

1.1.1. Контактно-вентильные схемы

1.1.2. Ориентированные контактно-вентильные схемы

1.1.3. Ациклические контактно-вентильные схемы

1.1.4. Недетерминированные ветвящиеся программы

1.1.5. Детерминированные ветвящиеся программы

1.1.6. Сравнение сложностей реализации булевых функций различными типами управляющих систем

§ 1.2. Нижние оценки сложности для недетерминированных

ветвящихся программ

1.2.1. Оценка Э. И. Нечипорука
1.2.2. Оценки для симметрических булевых функций
1.2.3. Оценки для характеристических функций двоичных кодов
§ 1.3. Нижние оценки сложности для детерминированных
ветвящихся программ
1.3.1. Оценка Э. И. Нечипорука
1.3.2. Оценки для симметрических булевых функций
1.3.3. Оценки для характеристических функций двоичных кодов
1.3.4. Оценки для ветвящихся программ ограниченной глубины

§ 1.4. Ветвящиеся программы ограниченной ширины
§ 1.5. Ветвящиеся программы ограниченной глубины
§ 1.6. Ветвящиеся ^-программы
1.6.1. Нижние оценки сложности для ветвящихся 1-программ
1.6.2. Нижние оценки сложности для ветвящихся ^-программ
1.6.3. Иерархия ветвящихся /с-программ
1.6.4. Нижние оценки для схем без ограничений
1.6.5. Упорядоченные бинарные деревья решений
Глава 2. Метод получения нижних оценок сложности ветвящихся ^-программ
§ 2.1. Идея метода получения нижних оценок сложности
ветвящихся ^-программ
§ 2.2. Определения и предварительные сведения
§ 2.3. Установление соответствия между множеством единиц булевой функции и подмножествами
вершин ветвящейся ^-программы
§ 2.4. Нижние оценки сложности ветвящихся ^-программ
§ 2.5. Нижние оценки сложности вычисления характеристических функций БЧХ-кодов ветвящимися
^-программами
Глава 3. Модификация метода получения нижних оценок сложности ветвящихся /с-программ. Сравнение
сложностей ветвящихся А:-программ
§ 3.1. Определение и свойства функции Рп
§ 3.2. Построение последовательности Ф(ТГ)
§ 3.3. Оценка мощности множества Ф_1(.В)
§ 3.4. Сравнение сложностей реализации булевых функций

Глава 4. Нижние оценки сложности ветвящихся программ
§4.1. Сведение нижних оценок сложности для программ без ограничений к оценкам сложности для
к-программ
§ 4.2. Нижние оценки сложности ветвящихся программ
без ограничений
§ 4.3. Нижние оценки сложности вычисления характеристических функций кодов Рида-Маллера
4.3.1. Подсчет числа единиц в подкубах для кодов Рида-Маллера
4.3.2. Нижние оценки сложности вычисления характеристических функций кодов Рида-Маллера, использующие теоремы, полученные с помощью подхода, предложенного в диссертации
4.3.3. Нижние оценки сложности вычисления характеристических функций кодов Рида-Маллера, использующие теоремы, полученные с помощью подхода А. Бородина, А. Разборова и Р. Смоленского
4.3.4. Нижние оценки сложности вычисления характеристических функций кодов Рида-Маллера
§ 4.4. Нижние оценки сложности вычисления характеристических функций двоичных кодов с большим числом
кодовых вершин
Глава 5. О некоторых операциях над булевыми
функциями
§ 5.1. Геометрическая проекция

(треллисы) (см. [93]). Эти схемы исследовались в работах [76, 85, 90]. Обзоры по упорядоченным бинарным деревьям решений имеются в [86, 119, 120].
В последнее время интенсивно изучаются вероятностные и квантовые ветвящиеся программы. Информацию об этих типах ветвящихся программы можно найти в [63, 64, 65, 82, 105, 107, 108, 115]).
При подготовке данного обзора использовались обзоры по сложности ветвящихся программ из работ П. Пудлака [101], И. Вегенера [117, 120], И. Вегенера и Д. Зилинга [112], А. А. Разборова [103], диссертации М. Зауерхоффа [105], а также из ряда работ других авторов.