Изменения

# Берётся всё из тех же лекций Ложкина: {{Скачать|Ложкин С.А. - Лекции по основам кибернетики 2004.djvu}}. ==== Асимптотически оптимальный метод синтеза схем из функциональных элементов==== * '''Опр.''' дискретно-универсальное множество функций.* '''Т.''' (Лупанова) о верхней оценке функции Шеннона в классе СФЭ.* '''Сл.''' (асимптотика функции Шеннона). # ==== Асимптотически оптимальный метод синтеза контактных схем==== * '''Опр.''' m-регулярное множество.* '''Т.''' (Лупанова) то же, но в классе КС.* Идея метода Лупанова: разложение функции по подфункциям и полосам, построение суперпозиции КС на основе m-регулярного множества. # ==== Инвариантные классы и их свойства==== * Берётся из {{Скачать|Сапоженко - Некоторые вопросы сложности алгоритмов.pdf}}.* '''Опр.''' инв.класс, характеристика ИК, сложная функция, правильный алгоритм.* Пример ИК с характеристикой 0.5.* '''Т.''' (Яблонского) о существовании ИК с заданной характеристикой.* '''Т.''' (Яблонского) о работе правильного алгоритма, строящего сложную последовательность функций. # ==== Синтез схем для функций из некоторых инвариантных классов==== * Из Сапоженко и Ложкина.# * '''Т.''' (Лупанова) о верхней оценке функции Шеннона для ИК с заданной характеристикой.* '''Т.''' о нижней мощностной оценке функции Шеннона для ИК с характеристикой, большей 1. ==== Нижние оценки сложности реализации булевых функций параллельно-последовательными контактными схемами==== * Соотношение между π-схемами и формулами с поднятыми отрицаниями.# * '''Опр.''' каркас.* Оценка числа формул данной сложности на основе количества каркасов и способов подстановки переменных.* '''Л.''' о верхней оценке количества π-схем данной сложности через число формул.* '''Л.''' об обращении степенного неравенства.* Принцип получения нижних оценок функции Шеннона.* '''Т.''' о нижней оценке функции Шеннона. ==== Нижние оценки сложности реализации булевых функций формулами в произвольном базисе==== * '''Опр.''' приведенный вес, каркас.* '''Л.''' о соотношении между рангом формулы, ее сложностью и приведенным весом.* Оценка числа формул данной сложности на основе количества каркасов и способов подстановки переменных.