О мощностной сложности плоских схем Калачев, Глеб Вячеславович

brief description

Калачев, Глеб Вячеславович.
О мощностной сложности плоских схем : диссертация ... кандидата физико-математических наук : 01.01.09 / Калачев Глеб Вячеславович; [Место защиты: Моск. гос. ун-т им. М.В. Ломоносова]. - Москва, 2017. - 164 с. : ил.
Оглавление диссертациикандидат наук Калачев, Глеб Вячеславович
Оглавление
Введение
§1 Общая характеристика работы
§2 Краткое содержание работы
§2.1 Плоские схемы
§2.2 Меры мощности схем
§2.3 Общие обозначения
§2.4 Результаты
1 Общие оценки мощности плоских схем
§1 Связь переключательной мощности и потенциала
§2 Связь между мощностью и площадью плоских схем
§3 Универсальная нижняя оценка средней мощности плоских схем
§4 Общие вспомогательные утверждения
2 Оценки мощности частичных булевых операторов
§1 Нижние оценки
§1.1 Идея и схема доказательства для случая большого числа выходов
§1.2 Метод расслоения
§1.3 Общие оценки для частичных операторов
§1.4 Нижние оценки для всюду определенных операторов
§2 Верхние оценки
§2.1 План доказательства
§2.2 Вспомогательные блоки
§2.3 Реализация всюду определённой булевой функции
§2.4 Построение схемы частичной булевой функции
§2.5 Реализация частичного булева оператора
3 Оценки мощности для различных классов булевых функций
§1 Оценки для функций с малым числом единиц
§1.1 Нижние оценки
§1.2 Верхняя оценка
§2 Оценки мощности для замкнутых классов булевых функций
§2.1 Построение схемы, реализующей монотонную функцию
§3 Мощность схем, реализующих функции из остальных замкнутых классов
Заключение
Список литературы