Определение [9]. Функция называется алгоритмически вычислимой, если существует алгоритм нахождения значения функции при любом допустимом значении аргумента.

Очевидно, что функции ,  и  алгоритмически вычислимы. Можно доказать, что операции суперпозиции, рекурсии и минимизации сохраняют свойство вычислимости [10]. Значит, все частично рекурсивные функции вычислимы. Тезис Чёрча утверждает, что класс алгоритмически вычислимых функций совпадает с классом всех частично рекурсивных функций. То есть выполняется и обратное включение: все вычислимые функции частично рекурсивны. Принятие данного тезиса позволяет истолковывать доказательство, что некоторая функция не является частично рекурсивной, как доказательство отсутствия алгоритма вычисления ее значений.

Аппарат частично рекурсивных функций позволяет исследовать общие алгоритмические проблемы. Для этого используется метод характеристик. Он заключается в следующем. По конкретной задаче строится соответствующая характеристическая функция, которая затем изучается на вычислимость. Вычислимость её позволяет утверждать разрешимость исходной проблемы. Пусть, например, стоит проблема разрешения предиката [11]. То есть если задан -местный предикат , то необходимо указать алгоритм позволяющий получить значение предиката для каждого набора  или доказать, что такого алгоритма нет. Составляем характеристическую функцию:

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

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

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

Метрическая теория.

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

1.Умножение -разрядных двоичных чисел. Даны два -разрядных двоичных числа и требуется найти их произведение. «Наивный» алгоритм умножения «столбиком» требует  битовых операций. Предложим рекурсивный алгоритм для данной задачи. Пусть  и  - два -битовых числа и пусть , в противном случае дополняем числа слева нулями. Разобьем числа  и  на две равные части в виде  ,  и будем рассматривать каждую часть как -разрядное двоичное число. Тогда произведение  можно представить в виде

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

,

где , , . Ясно, что операции сложения и сдвига имеют сложность .

Заметим, что  и  имеют, вообще говоря,  разрядов. Тогда

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

Таким образом, число используемых операций  ограничено сверху

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

Ясно, что  и данный алгоритм лучше по порядку исходного «наивного» алгоритма. Заметим, что для данной задачи известны и более лучшие алгоритмы [12].

2. Умножение матриц. Даны две квадратные матрицы порядка  с элементами из некоторого кольца  и требуется найти их произведение. Стандартный алгоритм требует  умножений и сложений элементов К. На первый взгляд, кажется, что невозможно сколько-нибудь существенно уменьшить данное число операций, Однако, В. Штрассеном [13] был предложен следующий алгоритм.

Пусть . Тогда произведение матриц находится одним умножением.

Пусть  и даны матрицы , . Положим . Тогда матрица  может быть вычислена так. Пусть , , , , , , . Тогда находим , , , .

Заметим, в данном алгоритме использовано 7 умножений и 18 сложений и не использована коммутативность умножения.

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

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

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

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

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

Теперь можно доказать, что справедливо следующее утверждение [15]. Пусть дано рекуррентное соотношение

где , , , ,  - фиксированные константы. Тогда при , где , решением соотношения является выражение

Далее вытекает следствие [16], что в предположениях предыдущего утверждения справедливы соотношения

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

где , , , ,  - фиксированные константы. Например, такая ситуация возникает при решении графических задач. Для такого соотношения при , где , справедлива оценка [17]

В некоторых случаях для организации рекурсии используется «квадратичное» разбиение, при котором исходная задача размера  разбивается на  подзадач размера . Для сложности  рекурсивного алгоритма возникает следующее рекуррентное уравнение

где  , ,  - фиксированные константы. Оно определяет однозначно функцию  при   таким выражением [18]

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

Для задачи умножения матриц использование базового алгоритма умножения -матриц с  умножениями для построения рекурсивного алгоритма, сводящего умножение -матриц к умножению -матриц приводит к оценкам для сложности :

(в алгоритме Штрассена , ). В. Пан использовал алгоритм с параметрами  и  и получил . В настоящее время известны и более лучшие алгоритмы. Усилиями ряда математиков (Пан, Виноград, Романи, Шейхаге, Штрассен, Копперсмит) экспонента сложности матричного умножения последовательно принимала значения: , , , , , . Основная проблема - нахождение доказательства равенства  еще не решена [19].

Страницы: 1, 2, 3, 4