Теория дискретных управляющих систем является одним из центральных разделов математической кибернетики. Она рассматривает математические модели, в которых информационное преобразование описывается дискретной функцией, а способ реализации этой функции — некоторой структурой: формулой, схемой из функциональных элементов, контактной схемой, автоматной схемой и т. п.1, 2
Функция и структура
Важно разделять два уровня описания. Функционирование отвечает на вопрос, какое преобразование входных данных выполняет система. Структура показывает, из каких элементов и связей построена реализация. Разные по структуре системы могут реализовывать одну и ту же функцию, поэтому функциональная эквивалентность не означает структурного совпадения.
Две основные задачи
Задача анализа начинается с готовой схемы. Требуется определить её функционирование: например, вычислить булеву функцию, которую реализует схема. Анализ может быть индивидуальным, когда исследуется одна конкретная схема, или массовым, когда нужен алгоритм анализа целого класса схем.1
Задача синтеза формулируется в обратном направлении. Задано требуемое функционирование, и нужно построить систему, которая его реализует. Обычно подходящих реализаций много, поэтому возникает задача оптимизации. В качестве критерия используют, например, число или суммарную сложность элементов, а также задержку прохождения сигнала.1
Основные блоки курса
В действующей программе ВМК курс охватывает несколько связанных направлений. Сначала изучается представление булевых функций и минимизация ДНФ. Затем вводятся основные классы дискретных управляющих систем и их эквивалентные преобразования. Далее рассматриваются задача синтеза, функции сложности и асимптотически эффективные методы построения схем. Отдельный блок посвящён надёжности и контролю. В завершающей части обсуждаются модели, связанные с программно-аппаратной реализацией алгоритмов.2
Таким образом, логика курса движется от описания функции к её структурной реализации, затем к преобразованию и оптимизации этой реализации и, наконец, к вопросам её надёжной работы и практического использования.