О сложности мультиплексорных функций в некоторых классах схем

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

Оглавление
Введение
Общая характеристика работы
Основные определения и формулировка полученных результатов
Глава 1. Реализация стандартных мультиплексоров и квазимультиплексоров в некоторых классах схем, верхние оценки их сложности.
1.1. Некоторые понятия и конструкции, связанные с реализацией
мультиплексорных ФАЛ
1.2. Реализация мультиплексоров формулами с оптимизацией их
глубины
1.3. Реализация мультиплексоров 7г-схемами и формулами с опти-
мизацией их сложности
1.4. Реализация мультиплексоров схемами из функциональных эле-
ментов. Обобщение полученных ранее результатов на некоторый класс квазимультиплексоров
Глава 2. Нижние оценки сложности (глубины) мультиплексорных функций в некоторых классах схем.
2.1. Операция стандартной подстановки констант. Нижние оценки
глубины мультиплексорных функций

2.2. Канонические квазимультиплексорные схемы и формулы, осо-
бенности их структуры
2.3. Нижние оценки сложности реализации квазимультиплексор-
ных функций 7Г-схемами и формулами
2.4. Нижние оценки сложности реализации квазимультиплексор-
ных функций схемами из функциональных элементов
Литература

Введение.
Общая характеристика работы.
Теория синтеза управляющих систем является одним из основных разделов дискретной математики и математической кибернетики ([14, 24, 45]). Она возникла в 30-40-х годах прошлого века в связи с необходимостью проектирования и логического описания дискретных вычислительных устройств различного типа. К. Шеннон в работах [62, 63] дал строгую математическую постановку задачи синтеза управляющих систем, положив тем самым начало соответствующей теории, исследования в которой ведутся с тех пор непрерывно. В целом, в теории синтеза управляющих систем изучаются модели различных дискретных преобразователей сигналов, их сложность, надёжность и другие характеристики.
Интерес к этой области знания обусловлен, прежде всего, возможностью применения полученных результатов при проектировании оптимальных или близких к оптимальным по определённым характеристикам схем, при изучении их поведения и надёжности, при тестировании схем и т.д. Кроме того, результаты, полученные для решения задачи синтеза, находят применение в других областях дискретной математики.
Задача синтеза ставится для определённого класса управляющих систем. Количество таких классов довольно велико, что вызвано потребностью в исследовании разных моделей и характеристик реальных схем. Для каждого класса управляющих систем задаётся определённая структу-
1.2. Реализация мультиплексоров формулами с оптимизацией их глубины.
Докажем верхние оценки глубины мультиплексорной ФАЛ цп, п ^ 6, в стандартном базисе 7>о и в унимодальном базисе С/г для функционалов сложности (глубины) Р(/) и £>ц2(/). Напомним, что случай
1 ^ п ^ 5 был рассмотрен в лемме 3.
Лемма 6. Для мультиплексорной ФАЛ рп, где п > 5, справедливо: Р&д/(Ап(ж, 2/)) = Б>и2(цп(х, у)) ^п + 3, если 5 < п < 20,
А&д/(/Аг(ж,у)) = Ди2(цп(х,у)) < гг+ 2, если гг ^ 20.
Доказательство. Пусть т — максимальное натуральное число такое, что
771 ^ 2 и 2т + 2т”2 ^ п. (14)
Легко видеть, что указанное т всегда существует, если п > 5.
Разделим набор адресных БП х мультиплексорной ФАЛ рп на три части следующим образом:
X (ж 1, . . . , Хп) ) ?
2т с 2т~
где в соответствии с выбором значения т, удовлетворяющего (14), и его максимальностью
с = п-2т - 2т~2 и 0^с^5-2т-2.
Положим
д = 2т + С И ж' = (жЬ. ..,Ж,), х" = (ж9+х, . . . ,ЖП).
Разобьём единичный куб В2 от БП х,... , Ж2 на 22т~т непересе-кающихся единичных сфер в соответствии с леммой 4. Заметим, что в силу (12) произвольная ФАЛ, обращающаяся в единицу ровно в одной точке сферы, совпадает на этой сфере с некоторой БП или её отрицанием.