Об особенностях асимптотического поведения сложности реализации к-значных и автоматных функций схемами в произвольном конечном базисе

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

ГЛАВА 1. О СЛОЖНОСТИ РЕАЛИЗАЦИИ АГ-ЗНАЧНЫХ ФУНКЦИЙ СХЕМАМИ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ В ПРОИЗВОЛЬНОМ ПОЛНОМ КОНЕЧНОМ БАЗИСЕ
§ 1. Реализация булевых функций
§ 2. Реализация квазибулевых функций
§ 3. Реализация ^-значных функций
§ 4. Оптимальные базисы и сильно существенные системы
&-значных функций
§ 5 Оценки числа сильно существенных функций
§ 6 Об оптимальности почти всех &-значных базисов
§ 7 О сравнении булевых и &-значных базисов
ГЛАВА 2. О СЛОЖНОСТИ РЕАЛИЗАЦИИ АВТОМАТНЫХ ФУНКЦИЙ СХЕМАМИ В ФУНКЦИОНАЛЬНО ПОЛНЫХ БАЗИСАХ
§ 8. Основные определения и формулировка результатов
§ 9. Моделирование продукций Поста схемами в функционально
полных базисах
§ 10. Описание автомата О
§ 11. Свойства схем в базисе Вд
§ 12. Доказательства основных результатов главы
ГЛАВА 3. РЕАЛИЗАЦИЯ ФУНКЦИЙ СХЕМАМИ, В КОТОРЫХ ДОПУСТИМЫ СУЩЕСТВЕННЫЕ ЦИКЛЫ
§ 13. Реализация функций правильными схемами
§ 14. Реализация функций С-схемами
ЛИТЕРАТУРА

Оптимальная реализация дискретных функциональных отображений различными средствами является одной из основных областей математической кибернетики [39]. Актуальность этой задачи обусловлена все возрастающей потребностью построения оптимальных устройств обработки цифровой информации. В качестве отображений наиболее часто рассматривают функции алгебры логики (булевы функции), функции /г-значной логики (к-значные функции, функции из Рк) и ограниченно-детерминированные (автоматные) функции. Наиболее распространенными средствами реализации являются схемы различных видов: контактные и релейноконтактные схемы, схемы из функциональных элементов и схемы в автоматных базисах. В качестве критериев оптимальности схемы рассматривают сумму весов элементов (сложность), быстродействие и мощность.
В работе исследуются вопросы построения имеющих минимальную сложность схем, реализующих А;-значные и автоматные функции. Рассматриваются схемы, элементы которых имеют один выход.
Наиболее актуальной является реализация индивидуальных функций. Существует "переборный" алгоритм решения этой задачи. Однако, даже при малом числе переменных этот алгоритм практически нереализуем.
Ввиду сложности задачи построения схемы, реализующей произвольную функцию с минимальной сложностью, большая часть исследований посвящена изучению асимптотического поведения функции Шеннона, равной максимуму минимальной сложности схем, реализующих функции из заданного класса.

значения функций /„,с и /п^ на этом наборе различны. Аналогичным образом показывается существование таких наборов для последующих элементов цепочки.
Так как / не принадлежит множеству 1¥п, то существует набор Ут-іі3 значений входов, отличных от п-го, и значение 5от-і,у п-го входа (те — 1)-го элемента такие, что значение выхода (те — 1)-го элемента равно зту. Аналогичным образом показывается существование таких наборов и значений п-х входов для предыдущих элементов цепочки.
Доказательство существенности п-го входа первого элемента цепочки является более простым случаем рассмотренного выше.
Теорема 14 доказана.
Через Мг будем обозначать множество функций / таких, что Я/ = {0 г — 1} . Через Яг обозначим множество б'-функций из Мг, а через N Я Яг — множество функций из Яг. не являющихся сильно существенными. Пусть
л _лт к _а.
ІЯІ ’ — |5Г|'
Из соотношения
| Я і' | > гк" — ПГк" 1 — г(г — І)*“
следует, что кг быстро стремится к 1.
Для произвольного г оценим число функций из N Я Яг и их долю
(1Г.
Пусть
Тг =Т п Мг
Из теоремы 14 и определения множеств N Я Яг и Тг получаем следующее утверждение.