Задача синтеза управляющих систем

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

Рассмотрим, как решается проблема сложности в одном из важнейших разделов математической кибернетики – синтезе управляющих систем.

Из раздела “Булева алгебра” известны функции алгебры логики (ФАЛ или булевы функции) от двух переменных. Любую ФАЛ можно задать таблицей истинности, в которой указано, какое значение функции соответствует тому или иному набору. Поскольку существует 2^п наборов длины п и на каждом наборе функция может принимать два значения, то число различных ФАЛ равно 2^2п . Особое место в кибернетике и математической логике занимают следующие шесть функций: константа 0, константа 1, равнозначность, отрицание, конъюнкция, дизъюнкция. Естественно попытаться представить любую булеву функцию в виде формулы от этих элементарных функций. Из теоремы Шеннона о предельном разложении следует, что любая ФАЛ представима в виде формулы, где участвуют лишь операции дизъюнкции, конъюнкции и отрицания. Часто бывает удобно представить формулу в виде дерева, где висячим вершинам поставлены в соответствие булевы переменные или их отрицания (первичные термы), а во внутренних вершинах указаны операции, которые следует выполнить над переменными или над формулами.

Пример. Пусть функция f имеет следующее представление в виде формулы

.

Изобразить ее в виде дерева.

□ Изображение заданной функции в виде дерева будет иметь вид:

■

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

Однако для каждой функции может существовать не одна реализующая ее схема. Поэтому требуется построить схему, наилучшую в том или ином смысле (например, схему с минимальным числом элементов). В связи с этим каждой схеме s ставится в соответствие некоторое число L(s), называемое ее сложностью.

Формулировка задачи синтеза с учетом сложности. Задачу синтеза можно теперь сформулировать следующим образом: для данной булевой функции f построить схему, на которой величина L(s) достигает минимума. Обозначим этот минимум через L( f ).

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

Формулировка Шеннона: найти для каждой ФАЛ схему , для которой L( f ) “близко” к , где максимум берется по всем булевым функциям.

Постановка задачи в таком виде принадлежит американскому инженеру и математику К. Шеннону, в связи с чем функция L(n) носит название функции Шеннона. Эта функция характеризует сложность всего множества функций с точки зрения реализации его функций минимальными схемами. В такой постановке задачи не требуется чтобы алгоритм для каждой функции f находил минимальную схему, необходимо только, чтобы простейшая схема, получаемая при помощи алгоритма, имела сложность сильно не превышающую .

Рассмотрим, как решается задача оптимального синтеза на примере контактных схем.

Булевой схемой называется граф, у которого выделены вершины – полюса, и каждому ребру приписана некоторая булева переменная или ее отрицание .

Ребро называется замыкающим, если , и размыкающим, если

Булевы схемы моделируют реальные физические устройства, у которых в некоторых точках имеются контакты и которые могут находиться в замкнутом или разомкнутом состоянии.

Цепь булевой схемы замкнута, если замкнуты все расположенные вдоль нее контакты, и разомкнута , если хотя бы один из ее контактов разомкнут.

ФАЛ, заданная для каждой пары полюсов и определенная на всех наборах переменных, которые приписаны ребрам, называется проводимостью схемы.

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

Таким образом, булева схема реализует булеву функцию.

Проводимость цепи равна конъюнкции , а проводимость схемы есть дизъюнкция всех таких конъюнкций.

(1,k)-полюсником называется булева схема, у которой один полюс считается входным, а остальные k – выходными .

(1,k)-полюсник называется разделительным, если проводимость между любыми двумя его выходами равна нулю.

(1,k)-полюснику можно поставить в соответствие систему k функций, которые он реализует. Аналогично можно определить (k,1)-полюсник.

Если булева схема s₁ реализует функцию f₁ , булева схема s₂ – функцию f₂ , то параллельное их соединение, очевидно, реализует функцию , а последовательное - .

(1,2^п)-полюсник называется булевым деревом и имеет вид:

NP - полнота

Суть проблемы NP-полноты заключается в следующем. В дискретной математике существуют задачи, для которых до сих пор не найдены алгоритмы, имеющие полиномиальную трудоемкость. Но если бы удалось отыскать эффективный алгоритм решения хотя бы одной из них, то из этого следовало бы существование таких алгоритмов для остальных задач данного класса.

Свойство детерминированности алгоритма означает, что для каждого имеющегося в данный момент состояния либо не существует никакого следующего (когда состояние заключительное), либо существует в точности одно следующее состояние.

Предположим, что алгоритму “разрешается” для каждого текущего состояния иметь больше одного следующего. Это, в частности, означает, что если в процессе вычисления алгоритм доходит до того места, где требуется выбрать одну из нескольких альтернатив, он не исследует их, как детерминированный алгоритм, последовательно друг за другом, а просматривает все их одновременно, копируя самого себя. В свою очередь, эти копии могут порождать новые. Полученные копии продолжают работать все вместе до тех пор, пока одна или несколько из них не найдет решение. После этого дается команда на остановку работы всех копий. Конечно, никакое реально существующее устройство не может вести себя как недетерминированный алгоритм, но такая абстракция позволяет избежать трудностей, возникающих при анализе алгоритмов.

Алгоритм называется полиномиальным, если время его работы с некоторой задачей ограничено сверху полиномом.

Все задачи, которые могут быть решены с помощью полиномиальных алгоритмов, объединяются в один класс, который обозначается буквой Р.

Класс задач, которые могут быть решены с помощью недетерминированного алгоритма за полиномиальное время, обозначается через NP.

Легко видеть, что Р NP.

Если любая задача из класса NP сводится к некоторой задаче из класса Р за полиномиальное время, то она называется NP – трудной. Если же при этом она принадлежит классу NP, то она называется NP – полной.

Вопрос о том, существует ли для какой-либо NP – трудной или NP – полной задачи детерминированный полиномиальный алгоритм ее решения, является чрезвычайно интересным.

Начальной, отправной точкой здесь является задача о выполнимости.