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

и рассмотрим подмножество алгоритмов ЛЛФ постоянной сложности.

. Алгоритмы, не являющиеся АПС, называются алгоритмами вариантной сложности.

ОО для АПС может быть задана путем указания множества пар индексов, каждый из которых характеризует класс эквивалентных для АПС задач:

Для АПС естественным образом конкретизируются способы построения операций сужения и сложения. Для построения операции распространения АПС в работе вводятся три базовых способа распространения АПС:

путем разбиения КИХ,

путем разбиения входного сигнала,

Доказывается, что этих трех способов достаточно для построения операции распространения АПС на произвольную ОО. Доказательство производится путем построения искомой операции распространения.

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

, где:

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

, будем в дальнейшем называть приведенным.

Доказываются следующие свойства приведенного и компетентного алгоритмов.

- конечное множество АПС, тогда:

справедливо:

Рассматриваются различные способы построения распространения ПКА:

Доказывается, что независимо от того, как именно построена операция распространения АПС, вычислительные сложности для следующих пар алгоритмов оказываются одинаковыми: 6 и 2, 7 и 3, 8 и 4. Для дальнейшего изложения вводится реализация операции распространения путем сложения со всюду определенным

Доказываются свойства такой реализации операции распространения:

вычислительные сложности следующих пар алгоритмов равны: 5 и 1, 3 и 2, 4 и 2;

Эти свойства позволяет устранить операцию распространения из процесса построения ПКА с заданной ОО: для этого в опорное множество АПС просто добавляется любой доступный АПС с необходимой в итоге ОО. На практике таким алгоритмом может быть алгоритм прямой свертки как наиболее простой в реализации.

Учитывая свойства АПС и ПКА, оказывается возможным указать структуру метода, который определяет параметры индуцированного алгоритма в том случае, когда в качестве опорного множества используется множество АПС.

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

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

Исходя из доказанных положений структура метода построения эффективного алгоритма оказывается следующей:

над предоставленным опорным множеством АПС {A}({ADC}U{AFC} (в опорное множество обязательно включен АПС с искомой ОО, то есть ADC({A});

Для заданного опорного множества АПС {A} первые две операции метода полностью формализованы и определены. Выполнение третьей операции рассматривается во второй главе диссертации. Несмотря на то, что на данный момент третья операция не определена, можно охарактеризовать гарантированный выигрыш от снижения сложности у индуцированного алгоритма. Учитывая соотношения

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

Первое направление исследования состояло в определении влияние операции приведения на сложность АПС. В качестве АПС использовались БА свертки без секционирования и с секционированием входного сигнала.

» –сложность приведенного АПС На рисунке 2 показаны сечения функции сложности БА вычисления свертки до и после операции приведения.

Общие выводы по этому направлению исследования следующие:

в общем случае функция сложности БА свертки не является корректной;

использование операции приведения к БА свертки позволяет уменьшить сложность решения для более чем 50% задач из его ОО;

максимальное снижение сложности составляет 12.6 раз.

среднее снижение сложности составляет 1.5 раза.

Второе направление исследования состояло в сравнении сложности ПКА со сложностью компетентного алгоритма (над одним и тем же множеством АПС). Общие выводы по этому направлению исследования следующие (в опорном множестве находилось от 2 до 5 алгоритмов ЛЛФ):

независимо от числа алгоритмов опорного множества можно рассчитывать на снижение сложности для более чем 30% задач из ОО;

для тех задач из ОО, в которых произошли изменения функции сложности в результате операции приведения, можно рассчитывать на снижение сложности по отношению к сложности компетентного алгоритма в среднем на величину от 10% до 30% в зависимости от числа алгоритмов ЛЛФ в опорном множестве.

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

, где v – частота появления во входном сигнале отсчетов с нулевыми значениями. Также приведено обобщение изложенного подхода построения эффективного алгоритма на случаи: изображений; задачи множественной корреляции, в которой вычисление свертки входного сигнала производится одновременно для нескольких КИХ; построения эффективного алгоритма, минимизирующего время решения задачи ЛЛФ.

рассмотрен в тексте диссертации).