СИНТЕЗА ЗАДАЧИ

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

С каждым классом у. с. естественным образом связан определенный класс функций. Задача синтеза в ее исходной постановке состоит в том, чтобы по заданной функции из этого класса построить реализующую ее у. с. Напр.: 1) задана булева функция - требуется построить формулу, к-рая ее реализует; 2) задана система булевых функций - требуется построить многополюсную контактную схему, реализующую эту систему; 3) имеется точное описание поведения автомата - требуется построить такой автомат; 4) задана вычислимая функция - требуется найти алгоритм, к-рый ее вычисляет, либо составить соответствующую программу.

Приведенные примеры относятся к дискретной ветви математики. Однако аналогичные примеры характерны и для непрерывной ветви математики: 1) задана логарифмическая амплитудно-частотная характеристика системы автоматич. регулирования (или, в более общем случае, условия ее работы, т. е. возмущающие и управляющие воздействия, помехи, ограничения по времени работы и т. д.) - требуется синтезировать систему автоматич. регулирования, обладающую заданной характеристикой; 2) задана система линейных уравнений и неравенств, а также нек-рая линейная функция - требуется построить схему вычисления, к-рая максимизирует заданную линейную функцию на множестве решений заданной системы; 3) задана система дифференциальных уравнении и указана необходимая точность ее решения - требуется найти алгоритм численного решения этой системы с указанной точностью.

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

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

На самом деле столь определенная постановка задачи возможна лишь для конечных моделей у. с. Как следствие, для них и вся синтезная проблематика оказывается очерченной лучше. Поэтому ниже основное внимание уделено конечным моделям.

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

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

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

Шенноновский подход (по имени К. Э. Шеннона, к-рый впервые предложил его для контактных схем) связан с рассмотрением функции

L(n) = max L(f),

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

При более общей постановке задачи каждому функциональному элементу Есопоставляется положительное число L(E) -сложность этого элемента, к-рая зависит только от функции, реализуемой элементом Е, а каждой схеме Sприписывается сложность

L(S) =S L(E).

где суммирование производится по всем элементам схемы S. Для каждой булевой функции f определяется сложность ее реализации (в заданном базисе):

L(f) = minL(S).

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

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

r = min L(E)/(i -1),

где i - число входов элемента Е, а минимум берется по всем элементам, имеющим не менее двух входов. Тогда

Для других классов у. с. сложность L(S), а с ней и сложности L(f).и L(п).вводятся аналогичным образом. Обычно L(S).для контактной схемы Sесть число контактов в ней, а для формулы S - это число символов переменных в ней. Для автоматов и машин Тьюринга L(S).иногда вводится как число состояний автомата Sили машины Тьюринга S. Соответствующее асимптотическое поведение величины L(п).для этих классов показано в таблице 1.

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

Анализ нижней оценки для L(п).показывает, что на самом деле для почти всех булевых функций от ппеременных сложность реализации асимптотически не меньше L(n). Это означает, что данный метод синтеза для почти всех булевых функций дает почти самые простые схемы.

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

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

Эффективно решать такие задачи позволяет принцип локального кодирования. Этот принцип предполагает такое кодирование функций из рассматриваемого класса, при к-ром значение функции можно вычислять по сравнительно небольшой части кода.

Если при этом удается достаточно просто реализовать нек-рые вспомогательные операторы, то принцип локального кодирования дает асимптотически наилучший метод синтеза для рассматриваемого класса, причем в довольно широких пределах справедливо соотношение

,

где N_n - подмножество тех функций из рассматриваемого класса, к-рые зависят от заданных ппеременных, а

L(N_n) = mах L(f), где максимум берется по всем булевым функциям f из N_n. (здесь r=1).

Конкретный вид, который может иметь это асимптотическое соотношение, удобнее всего проиллюстрировать на классах булевых функций, принимающих значение 1 в заданном числе точек. Наиболее характерные примеры приведены в таблице 2.

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

Здесь возникают две проблемы: 1) построить для заданной конкретной функции f схему с возможно меньшим числом элементов и тем самым получить верхнюю оценку для L(f); 2) получить возможно лучшую нижнюю оценку для L(f). Среди этих задач первая обычно бывает легче, так как для ее решения достаточно, в конечном счете, построить одну схему, а вторая требует в каком-то смысле просмотра всех схем, реализующих функцию f. По этой причине возникло целое направление, связанное с поиском методов получения нижних оценок для конкретных функций.

Получение нижних оценок, линейных относительно п - числа аргументов функции (или в общем случае относительно объема входной информации), обычно все-таки не вызывает больших трудностей. Получение более сильных нижних оценок - значительно более сложная задача. Первыми примерами в этом направлении были нижняя оценка порядка п ^1,5 для формул в базисе , реализующих линейную функцию (сумму по модулю 2) паргументов, и нижняя оценка порядка для нормальных алгорифмов Маркова, к-рые обращают слова длины п. Наиболее высокие нижние оценки, к-рые к настоящему времени (1984) удалось получить, имеют порядок n², если не считать оценок, получающихся при очень сильных ограничениях на класс у. с. (напр., неполнота системы элементов) либо при использовании столь мощных средств для задания функции, что они фактически содержат в себе перебор всех функций.

О нетривиальности исследования сложности реализации конкретных функций говорит и то, что многие задачи, такие, как умножение целых чисел, умножение матриц, распознавание симметрии слова на многоленточных машинах Тьюринга, для к-рых ожидались сравнительно высокие нижние оценки, оказались на самом деле проще, чем предполагалось раньше.

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

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

Лит.:[1] Лупанов О. В., "Проблемы кибернетики", 1965, в. 14, с. 31-110; [2] Яблонский С. В., там же, 1959, в. 2, с. 75 - 121. В. М. Храпченко.