и вид КИХ;

, называемое далее опорным множеством, алгоритмов решения задач вычисления свертки (на практике алгоритмы опорного множества могут быть реализованы в виде программ);

гарантирует, что конструируемый алгоритм удовлетворяет требованию эффективности над опорным множеством (см. ниже);

допускает полностью автоматическое построение эффективного алгоритма без участия пользователя.

Требование эффективности над опорными множеством по отношению к алгоритму ЛЛФ означает, что этот алгоритм в вычислительном плане:

для любой задачи Z оказывается не хуже наилучшего алгоритма опорного множества (свойство эффективности),

для некоторых задач Z оказывается лучше наилучшего алгоритма опорного множества (свойство строгой эффективности).

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

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

- собственно алгоритм решения задач ЛЛФ, на практике реализованный в виде программы;

- область определения (ОО) алгоритма A, то есть множество задач, для которых алгоритм A применим;

- (полная) сложность решения задачи Z алгоритмом А, задаваемая в виде:

- число сложений и умножений, требуемых в алгоритме A для решения задачи Z. Удельная сложность алгоритма определяется выражениями:

Вводятся следующие отношения между алгоритмами:

- тождественность,

- подобие (для алгоритмов совпадают их аналитические описания),

- эквивалентность,

и т.д.

Вводятся следующие операции с алгоритмами:

(обратная операция к операции распространения).

- сумма алгоритмов, определяемая следующим образом:

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

В дополнении к указанным операциям в работе вводится понятие расширения множества алгоритмов, способ построения расширения задается определениями 2-3.

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

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

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

Модель CR алгоритма ЛЛФ:

Шаг 4 – Окончательная обработка и получение результата

алгоритмов ЛЛФ.

Иллюстрация к выполненному эквивалентному преобразованию и процессу вычисления, который реализует алгоритм модели CR, дана на рисунке 1.

Рисунок 1 – Вычисление свертки в рамках алгоритма модели CR

принимает значения “0” или “1”):

Окончательное определение способа построения расширения опорного множества алгоритмов ЛЛФ задается следующими двумя определениями.

на задаче Z называется множество алгоритмов модели CR следующего вида:

Везде далее под расширением понимается именно расширение по модели CR.

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

. Среди них:

. Основными вопросами, возникающими при решении этой задачи, являются:

способ нахождения параметров индуцированного алгоритма для конкретной задачи Z и заданного опорного множества алгоритмов;

: прямой, быстрой свертки и рекурсивных алгоритмов.