Методы синтеза и оценки сложности схем, построенных из элементов предикатного типа

• Автор: Шуплецов, Михаил Сергеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 114 с.

Оглавление
Введение
Общая характеристика работы
Модель схем из предикатных элементов и способы её представления
Задача синтеза для модели схем из предикатных элементов, формулировка полученных результатов и описание структуры диссертации
Глава 1. Модель схем из предикатных элементов и её основные характеристики
1.1 Структурное моделирование управляющих систем из некоторых классов при помощи схем из предикатных элементов
1.2 Обобщенные переменные и их изменение при суперпозициях
1.3 Некоторые числовые характеристики базисных предикатов и полных базисов
1.4 Совпадение приведенного и обобщенного приведенного весов
для некоторых классов базисов
Глава 2. Асимптотика функции Шеннона, характеризующей сложность схем из предикатных элементов для почти всех базисов

2.1 Нижние оценки функции Шеннона для сложности схем из предикатных элементов
2.2 Построение предикатных универсальных множеств функций
для специальных систем обобщенных переменных
2.3 Верхние оценки функции Шеннона для сложности схем из предикатных элементов
Глава 3. Асимптотические оценки высокой степени точности функции Шеннона для сложности схем из предикатных элементов для обобщенно-проводящих базисов
3.1 Уточнение нижних оценок функции Шеннона для сложности схем из предикатных элементов
3.2 Селекторные разбиения множества переменных предикатов
3.3 Синтез схем из предикатных элементов с использованием селекторных разбиений переменных
Список литературы

Введение
Важную роль в теории анализа и синтеза схем играют задачи построения и изучения новых моделей управляющих систем, которые учитывают те или иные особенности структуры или функционирования этих систем. Не менее важной задачей является построение моделей, обобщающих уже существующие модели, что позволяет единообразно представлять различные виды известных ранее моделей. В диссертации исследуется специальный класс управляющих систем — класс так называемых предикатных схем, который обобщает многие известные классы управляющих систем (схемы из функциональных элементов, контактные схемы, неявные и параметрические представления булевых функций и др.). Данные схемы строятся на основе предикатных элементов, которые отличаются тем, что не имеют, в общем случае, заранее фиксированного направления протекания сигналов. Для рассматриваемой модели решается классическая асимптотическая задача синтеза, заключающаяся в разработке методов синтеза схем для произвольных предикатов и установлении асимптотики функции Шеннона для сложности предикатных схем в различных базисах, а также в получении для этой функции асимптотических оценок высокой степени точности.

этим свойством не обладает).
Таким образом, Ь^(г]в0) = 3, и, учитывая неравенство (1.1) теоремы
1.1, любую СФЭ 5 в базисе Бо можно промоделировать предикатной схемой в базисе ©0) сложность которой не более, чем в три раза, больше сложности исходной схемы Я. Отметим, что для базиса Бр = {&. -і} величина Ь<в0 (г]Б'о) равна 2.
В заключение приведем примеры применения моделирования схем из некоторых классов для получения верхних оценок функции Шеннона Ь% (л). Произвольный предикат ж (ад,..., хп) можно реализовать при помощи следующей формулы:
где Хщ (х) = т. а г]х_ — предикат от (п + 1) переменной, моделирующий характеристическую функцию Хп предиката п. Таким образом, моделируя схемы из различных классов и используя представление (1.3), можно получить верхние оценки для функции Шеннона Бщ (п) в произвольном базисе *В.
Напомним, что функция Шеннона Ьк (п) для сложности контактных схем и функция Шеннона £,икс (п) для сложности итеративно-контактных схем удолетворяют следующим асимптотическим неравенствам (см., например, [11, 13]):
При структурном моделировании контактных схем предикатными схемами в базисе ©о сложность схемы возрастает не более чем в 2 раза. Таким образом, с учетом представления (1.3) и соотношений (1.4) получаем, что для функции Шеннона справедлива следующая оценка:
ж (ад,..., хп) = (Эу) (тд (у) г]Х7г (у, ад,..., ж„))
(1.3)
(1.4)