Математическая энциклопедия - схема из функциональных элементов

математич. модель реальных объектов, связанных с переработкой информации, в к-рых допускается многократное использование промежуточных результатов. К подобным объектам относятся, напр., электронно-ламповые схемы, сети нейронов, нек-рые виды вычислительных алгоритмов. Это один из основных классов управляющих систем. С. из ф. э. можно рассматривать как автомат без памяти.

Математически С. из ф. э. можно определить как ориентированный граф без циклов с помеченными ребрами и вершинами, множество вершин к-рого разбито на два подмножества. Вершины одного из них наз. входами С. из ф. э. Им не инцидентны входящие ребра, и каждой из них приписана буква из алфавита переменных Х = {х1, . .., х п}. Вершинам другого подмножества приписаны буквы из алфавита функциональных символов.

Алфавиту таким образом, соответствует однозначно множество функций Нек-рые вершины графа выделены и объявлены выхода-м и С. из ф. э. Вершина с входящими в нее (занумерованными) ребрами, к-рой приписан символ из (местность его равна числу входящих ребер), наз. функциональным элементом Другие концы инцидентных этой вершине входящих ребер суть входы функционального элемента а сама вершина есть выход функционального элемента Если на входы функционального элемента подать набор значений переменных из X, то на выходе (т. е. в вершине реализуется значение функции на этом наборе таким образом, функциональный элемент реализует функцию Всякая С. из ф. э. также реализует на своих выходах нек-рые функции. Набор функциональных элементов, соответствующий алфавиту из к-рого строятся С. из ф. э., наз. базисом Множество всех С. из ф. э., построенных при помощи функциональных элементов из наз. множеством С. из ф. э. в базисе Если полно, то полон, и С. из ф. э. в можно реализовать любую функцию. Далее предполагается, что переменные из . принимают значения 0, 1, и подмножество функций алгебры логики. Именно такого типа базисы изучены наиболее полно.

В качестве примера С. из ф. э. может служить изображенная на рис. С. из ф. э. в базисе Ее входы вершины х 1 и х 2. выход вершина на нем реализуется функция

Эквивалентное определение С. из ф. э. можно дать также в терминах равенств. Для рассмотренного на рис. примера такая система может быть записана следующим образом:

Обычно функциональным элементам из приписываются неотрицательные числа, именуемые весами (или сложностями) функциональных элементов базиса. Под сложностью С. из ф. э. понимается сумма весов всех функциональных элементов, присутствующих в этой С. из ф. э. Минимальная сложность, достаточная для реализации произвольной функции алгебры логики от ппеременных С. из ф. э. в произвольном конечном базисе (с ненулевыми весами), асимптотически равна (см. [1]), где r константа для рассматриваемого базиса (см. Синтеза задачи). Минимальная сложность, достаточная для реализации С. из ф. э. системы F функций, зависящих от одних и тех же переменных, асимптотически равна где |F|число функций F, а константа, вычисляемая по базису.

По числу входов, к-рые могут быть присоединены к выходу произвольного функционального элемента, из класса С. из ф. э. выделяются т. н. С. из ф. э. без ветвления выходов, или формулы (к выходу каждого функционального элемента такой С. из ф. э. может быть присоединен только один вход). В отличие от формул, С. из ф. э. общего вида можно рассматривать как схемы вычислений с запоминанием промежуточных результатов. Для класса формул минимальная сложность, необходимая для реализации произвольной функции алгебры логики от ппеременных формулой в произвольном конечном базисе (с ненулевыми весами), асимптотически равна где константа, зависящая от базиса (ср. с контактными -схемами, см. Контактная схема). Для базисов, содержащих элементы с нулевыми весами, сложности С. из ф. э. ведут себя иначе (см., напр., [5]).

Кроме того, интерес представляет задача о синтезе схем в бесконечных базисах. Наиболее полно исследован случай, когда элементы базиса реализуют пороговые функции. Функция алгебры логики f(x1, . . ., х п )наз. пороговой, если существуют действительные числа w1: . . ., wn, hтакие, что

тогда и только когда, когда f(x1, . . .,xn)=1. Функциональный элемент, реализующий пороговую функцию, наз. пороговым элементом. С. из ф. э. в базисе из пороговых элементов наз. схемами из пороговых элементов. Обычно рассматриваются два типа базисов из пороговых элементов: 1) веса пороговых элементов равны единице, 2) вес порогового элемента равен сумме модулей всех коэффициентов wi (при условии, что пороговые функции задаются целочисленным неравенством (*)). Для каждого из этих базисов получены асимптотические оценки сложности схем из пороговых элементов: 1)

Путь между входом и выходом С. из ф. э. наз. цепью. Число вершин цепи, отличных от входа, наз. длиной цепи. Максимальная длина цепи в С. из ф. э. наз. глубиной С. из ф. э. Минимальная глубина С. из ф. э. (и формулы), достаточная для реализации произвольной функции алгебры логики от ппеременных в базисе равна

Кроме весов, функциональным элементам базиса могут быть приписаны неотрицательные числа, именуемые задержками. Под задержкой цепи понимается сумма задержек присутствующих в ней функциональных элементов. Под задержкой С. из ф. э. понимается максимальная задержка цепей этой С. из ф. э. Понятия задержки (при единичных задержках базиса) и глубины С. из ф. э., вообще говоря, не совпадают (см. [9]). В качестве примера других определений сложности С. из ф. э. можно упомянуть мощность С. из ф. э.: мощностью С. из ф. э. на наборе наз. число ее функциональных элементов, выходы к-рых находятся в состоянии 1 при подаче на входы Sнабора Мощность С. из ф. э. S - максимум ее мощностей на множестве всех наборов. Минимальная мощность, достаточная для реализации произвольной функции алгебры логики от ппеременных С. из ф. э. в произвольном конечном базисе, по порядку не меньше пи не больше 2ⁿ/n.

Лит.:[1] ЛупановО. Б., лИзв. вузов. Радиофизика

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985