Основные классы дискретных управляющих систем и меры их сложности

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

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

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

Почему существует несколько классов

Функционирование управляющей системы задаёт требуемую булеву функцию, но одну и ту же функцию можно структурно реализовать разными способами. Выбор класса фиксирует допустимые строительные элементы и способ соединения. Поэтому задача синтеза всегда формулируется относительно конкретного класса схем и конкретной меры сложности.1

КлассСтруктурная идеяОсновные меры
ДНФДизъюнкция элементарных конъюнкцийλ — число конъюнктов, R — суммарное число литералов
ФормулыКомпозиция операций без разделения результата одной подформулы между несколькими родителямиL — число функциональных символов, R — число вхождений переменных, D — глубина
СФЭОриентированная схема из функциональных элементовL — число ФЭ, D — максимальная глубина, R — число дуг из входов
Контактные схемыСеть, проводимость рёбер которой управляется входными переменнымиL — число контактов

1

Смысл функционалов сложности

В лекциях L для СФЭ связывается с количеством аппаратных элементов, стоимостью или размером схемы, а в программной интерпретации — с объёмом последовательной работы. Глубина D отражает задержку и естественно связана с параллельным временем. Ранг R характеризует количество обращений к входным данным. Это модельные интерпретации: конкретный физический показатель определяется тем, что именно моделирует выбранная схема.1

Поэтому числа сложности из разных классов нельзя сравнивать без дополнительного моделирования. Утверждение «эта реализация проще» имеет смысл только после указания класса, базиса и функционала.

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

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

Источники

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