Автоматная сложность булевых функций из классов Поста

• Автор: Кибкало, Мария Александровна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 139 с. : ил.

Оглавление
Введение
§ 1. Общая характеристика задачи § 2. Основные понятия и обозначения § 3. Основные результаты Глава 1. Методы построения сложных автоматов и функций
§1.1. Слияние прямого и обратного деревьев § 1.2. Вставка переменных § 1.3. Вставка д-ядра § 1.4. Вложение двоичного куба в множество монотонных функций § 1.5. Слияние ТУ-арных деревьев § 1.6. Зависимость высоты обратного дерева от числа переменных Глава 2. Точные значения и асимптотика функции Шеннона классов Поста
§2.1. Классы Сг, С2,С3, С4 всех булевых функций и функций, сохраняющих 0 и/или
§ 2.2. Классы 0г,03 самодвойственных функций § 2.3. Классы функций, обладающих свойством (Ат) и (а00)
§ 2.4. Классы Р2, функций, обладающих свойством {А2) и (а2)
§ 2.5. Классы А1,А2,А3,А4 всех монотонных функций и монотонных функций, сохраняющих 0 и/или 1 § 2.6. Классы Р/ монотонных функций, обладающих свойством (А2) и (а2)
§ 2.7. Класс 02 монотонных самодвойственных функций § 2.8. Классы Р/° монотонных функций, обладающих свойством (Л00) и (а00)
§ 2.9. Метод вставки переменных для множеств у = 1,4,5,
§ 2.10. Метод вставки д-ядра для множеств Д^+1, / = 1,4,5,8 § 2.11. Метод вставки переменных для множеств /ум^+1,) = 2,3,6,
§ 2.12. Метод вставки д-ядра для множеств /^Я^+1, _/ = 2,3,6,7 Глава 3. Сложность коллекций языков
§ 3.1. Сложность коллекций языков длины п § 3.2. Сложность коллекций языков длины не более п
Глава 4. Сравнение с другими мерами сложности
§ 4.1. Сложность покрывающих автоматов
§ 4.2. Сложность полиномов Жегалкина
§ 4.3. Коррелирующие меры сложности
§ 4.4. Результаты для упорядоченных диаграмм решений
Заключение
Приложение А. Алгоритмы и формулы
для вычисления высоты обратного дерева
Приложение В. Таблицы сложности классов Поста
Приложение С. Таблицы сложности
функций из множеств Р/уС+1
Список рисунков
Список литературы
Список составлен в порядке упоминания работ в тексте диссертации

Введение
§ 1. Общая характеристика задачи
Теоретическое осмысление вопросов программирования привело к необходимости измерять сложность подлежащих моделированию объектов. Ограниченная производительность вычислительных систем привела к преимущественному использованию для этих целей линейных методов распознавания, фильтрации, кодирования и предсказания поведения объектов. Действительно, линейные методы быстро суммируют вклады признаков, перекладывая качественную часть работы на исследователей, изобретающих эти удачные признаки. Заметим, что и сложность вычислений в линейных методах также линейно зависит от размерности задачи. Однако при таком подходе много времени затрачивается на творческие, интеллектуально сложные работы в предметной области, которые хотелось бы автоматизировать.
Понимание того, что линейных методов недостаточно привело к широкому использованию термина «нелинейные». При этом нелинейными часто называют либо пороговые методы, либо булевы функции, в полиноме которых присутствуют два-три члена второй степени. Широкому использованию произвольных нелинейных методов препятствует их высокая сложность. При их реализации приходится выполнять экспоненциально растущее от входных данных число операций.
При реализации вычислений в процессорах естественным образом происходит переход от математики непрерывной к математике булевой. За пару десятилетий процессоры прошли путь из 16-битных к 32-битным, а затем - к 64-битным. Какие затраты необходимы для 2к-битного процессора можно узнать, оценив в том числе и сложность булевых функций от 2К переменных, реализующих команды процессора.
Поскольку передача данных по каналам связи происходит последовательно, актуален вопрос о последовательном вычислении булевых

е0(уч) = тт{п,{>|Эг е ((г,а) = ах V ...V ап_г}} — минимальный
номер слоя, содержащего почти антитупиковое состояние.
Утверждение 1.2.9. V/ £ Р" выполнено § = §(/) + иР(/)+П.
Доказательство.
Рассмотрим приведенный автомат и { =
1, ...п + 1. Автомат Удд, представляющий 'К^'1 (/) можно построить из автомата Удд. Нужно добавить состояния, обеспечивающие представление элементарной конъюнкции у1 Л Л)«//-
При £; < п + 1 автомат Уд1(Е,51,Е1ф1,1р1,д')~Н'1(/), где 5Х =
и5В1 истроится следующим образом. Если > £, множество
дополнительных начальных единичных состояний 5В1 пусто. Если е1(У?) < £:, множество дополнительных почти тупиковых состояний 5ВД пусто. Если 5В1 = 5ВД = 0, автомат УчД строится из автомата УдД добавлением перехода по нулю начального единичного состояния гЬ1_11 слоя в почти тупиковое состояние гехд слоя Б[.
При Ьх < Ь добавляем цепочку начальных единичных состояний 5В1 = {гЬ ;Д,; = Ьг,... С - 1) в слои (}'ь±,... В слое есть начальное единичное состояние гй 1Д (если Ьг = 1, начальное состояние также будет начальным единичным). При ех > С добавляем цепочку почти тупиковых состояний 5В>1 = {ге ;д,у = £:, ...ех — 1} в слои Б[, (}[,... (}'е1-- В слое (}'е1 есть почти тупиковое состояние Ге±Д (если ех = п, тупиковое состояние также будет почти тупиковым). Функции перехода фг и выхода ф1 определяются так:
'гех< если Г = гъД_1Д
<Рх(.ЧЛ1), если г = гв С_1Д, £ =
(р1{(рх{яЛ}). о) если г = гй;д,у = Ьд — 1,.. С — 2, < С, 1 =
ГЬ,;'+1,1> если г = гйдд,у = - 1,.. Л — 2,Ьг < С, £ =
гп. если Г = ге;д,у = Ь,... ех — 1, > С, £ =
Ге,/+1Д< если Г = Гедд,у = £:,... — 1,ег > £ =
иначе