Схемы из функциональных элементов: структура, функционирование, приведение и меры сложности

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

СФЭ функционирует по глубинам от входов к выходам. Приведённой называется схема без висячих вершин. Любую СФЭ можно сделать эквивалентной приведённой удалением вершин, не влияющих на выходы. Основные меры: \(L(\Sigma)\) — число функциональных элементов, \(D(\Sigma)\) — максимальная глубина, \(R(\Sigma)\) — число дуг, выходящих из входов схемы.1

Что важно запомнить
  • СФЭ — ориентированный ациклический граф из функциональных элементов.
  • Каждый ФЭ реализует функцию базиса. Его входные дуги упорядочены по аргументам.
  • Промежуточный результат в СФЭ можно подавать нескольким следующим элементам.
  • Приведённая СФЭ не содержит висячих вершин. Удаление таких вершин сохраняет функционирование.1
  • L — число ФЭ, D — глубина, R — число дуг из входных вершин.

Структура СФЭ

Для каждой базисной ФАЛ \(\varphi_i\) арности \(k_i\) вводится функциональный элемент \(E_i\) с \(k_i\) упорядоченными входами и одним выходом. СФЭ строится как ориентированная ациклическая сеть: источники являются входами схемы и помечаются входными переменными, каждая вершина, отличная от источника, помечается функциональным символом \(\varphi_i\) и имеет ровно столько упорядоченных входящих дуг, сколько аргументов у \(\varphi_i\). Отдельные вершины назначаются выходами.1

Формула является частным случаем СФЭ. Главное расширение состоит в том, что в графе схемы выход одного элемента может разветвляться и использоваться несколькими последующими элементами. Поэтому одинаковое промежуточное выражение не обязательно вычислять несколько раз.

Функционирование

Во входной вершине реализуется соответствующая переменная. Если в вершину v, помеченную \(\varphi_i\), приходят значения функций \(f_{1},\ldots,f_{k_i}\), то в v реализуется композиция \(\varphi_i(f_{1},\ldots,f_{k_i})\). Ацикличность гарантирует корректный порядок такого вычисления. Система функций в выходных вершинах является функционированием СФЭ.1

Приведение

Висячей называют вершину, которая является стоком, но не является выходом схемы. Она не может влиять ни на один выход. СФЭ без висячих вершин называется приведённой. Из любой СФЭ можно получить эквивалентную приведённую СФЭ последовательным удалением висячих вершин. В приведённой схеме каждая вершина лежит на некотором пути от входа к выходу.1

Меры сложности

\(L(\Sigma)\) — число всех функциональных элементов, \(D(\Sigma)\) — максимальная глубина вершин, \(R(\Sigma)\) — число дуг, исходящих из входных вершин. Для приведённой одно-выходной СФЭ в Б₀ выполняется цепочка оценок \(R(\Sigma)\le L_{\land,\lor}(\Sigma)+1\le L(\Sigma)+1\le 2^{D(\Sigma)}\).1

Эти параметры отражают разные ресурсы: L — объём аппаратной или последовательной работы, D — критический путь и параллельную задержку, R — число обращений к исходным входным данным.

Пример простыми словами

Пусть в выражении один и тот же результат A=x₁∧x₂ нужен двум последующим операциям. В формуле подвыражение A пришлось бы записать дважды. В СФЭ достаточно одного элемента ∧, а его выход разветвить к двум потребителям. Именно такое совместное использование результата отличает общую СФЭ от дерева формулы.

Частые ошибки
  • Считать любую ориентированную сеть СФЭ. Граф должен быть ациклическим и согласованным с арностями элементов базиса.
  • Путать приведённость с минимальностью. Удаление висячих вершин устраняет заведомо бесполезную часть, но не гарантирует минимальное L.
  • Считать \(R(\Sigma)\) числом различных входных переменных. В курсе R считает дуги, исходящие из входов, поэтому одна переменная может использоваться несколько раз.

Другие вопросы

Источники

  1. 1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 2, §4, определения СФЭ и лемма 4.1, МГУ, факультет ВМК