Синтез управляющих систем. Часть II

Трудности получения эффективных нижних оценок сложности для индивидуальных последовательностей функций. Теорема Яблонского о невозможности элиминации перебора при построении последовательности самых сложных функций. Нетривиальные линейные оценки в классе схем из функциональных элементов.
Контактные схемы. Физическая модель. Сложность контактных схем. Контактное дерево для системы конъюнкций. Минимальность контактного дерева в классе разделительных схем.
Метод каскадов. Наилучший по порядку метод синтеза схем на основе метода каскадов. Реализация линейной функции методом каскадов.
Разбиение наборов длины $2^m$ на непересекающиеся сферы. Асимптотически оптимальная реализация системы всех конъюнкций.
Мощностная нижняя оценка функции Шеннона сложности реализации булевых функций контактными схемами.
Асимптотически наилучший метод О. Б. Лупанова синтеза контактных схем. Корректирование одного замыкания или размыкания без асимптотического увеличения сложности.
Сложность формул как число символов переменных и как число функциональных символов. Мощностная нижняя оценка функции Шеннона сложности реализации булевых функций формулами (для двух определений сложности формулы).
Параллельно-последовательные контактные схемы, их связь с формулами в базисе $\{ \vee, \&, - \}$.Асимптотически наилучший метод О. Б. Лупанова синтеза параллельно-последовательных контактных схем.
Сложность реализации функции, принимающей единичное значение на наборах с одной единицей, контактными схемами. Теорема Кардо о сложности реализации линейной функции контактными схемами.
Метод Б. А. Субботовской получения нижних оценок сложности реализации булевых функций в классе параллельно-последовательных контактных схем. Нижняя оценка сложности линейных функций по методу Субботовской.
Метод В. М. Храпченко. Простые цепи и тупиковые сечения в параллельно-последовательных контактных схемах и их свойства. Теорема Храпченко о нижней оценке сложности реализации булевой функции в классе параллельно-последовательных контактных схем. Нижняя квадратичная оценка сложности реализации линейных функций.
Метод Э. И. Нечипорука получения нижних оценок сложности реализации булевых функций формулами в произвольном конечном базисе. Функция Нечипорука и нижняя оценка ее сложности при реализации формулами в произвольном конечном базисе.