10.2. Числовые функции

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

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

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

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

Алгоритмы, определяющие способы задания рекурсивных функций, часто называют алгоритмами, сопутствующими рекурсивным функциям. Выделяют три способа построения рекурсивных функций: на основе оператора суперпозиции; на основе оператора рекурсии и на основе оператора построения по первому нулю.

Функции, полученные без использования оператора построения по первому нулю, называются примитивно - рекурсивными.

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

Рассмотрим рекурсивную функцию (РФ).

В ней различают:

1. Имя, т.е. ее обозначение.

2. Запись (W = f(x₁, x₂, x₃) или F = f(x₁, ..., x_n)).

3. Значение функции.

Значение функции отвечает конкретным значениям аргумента. Например, в функции f(x₁, x₂, x₃), аргументы x₁, x₂, x₃ имеют следующие значения x₁ = 1, x₂ = 3, x₃ = 100. Эту же функцию можно эквивалентно представить в следующем виде: f(1, 3, 100).

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

1. Функции любого числа независимых переменных, тождественно равные нулю. Их обозначают f₀, ₀.

Если функция записывается в виде ₀ или f₀, то любой совокупности значений аргументов данной функции ставится в соответствие значение ноль. Например, ₀(0) = 0, ₀(3, 5, 7) = 0, ₀(4, 17) = 0.

2. Тождественные функции любого числа независимых переменных вида _n,i, причем 1  i  n.

Представляющий эту функцию алгоритм запишется: если функциональный знак имеет вид _n,i, то значением функции следует считать значение (слева направо) i - того независимого переменного. Пример, W = _3,2(X, Y, Z) = Y, _3,3(3, 4, 8) = 8. _3,4(3, 4, 8) = 0 — эта запись не имеет смысла, т.к. n = 3, i = 4 и не выполняется условие 1  i  n. Для тождественных функций n, i  0.

3. Функции следования.

Представляющий эти функции алгоритм запишется: если функциональный знак имеет вид , то значением функции следует считать число, непосредственно следующее за числом, являющимся значением алгоритма. Например, операцию получения значения функции следования обозначают “ ‘ ” т.е., 0’ = 1, 1’ = 2 ... ‘(5) = 6.

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

Рассмотрим оператор суперпозиции или подстановки. Оператор по функции F от n аргументов и по функциям f1, f2, ..., fn строит новую функцию Ф так, что справедливо выражение:

Ф  F(f₁, f₂, ..., f_n).

Алгоритм, представляющий данный оператор, запишется: значения функций f₁, f₂, ..., f_n принять за значения аргументов функции F и вычислить ее значение.

Пример. Если f₁ = (y), а F = (x) и x = (y), то на основе оператора суперпозиции получится новая функция r(y) = ( (y) ) = (y’) = y’’. Тогда получили новую функцию r(y)  Ф.

Иногда в алгоритмах вводится знак «::=», что означает «по определению» или «присвоить». Применение этого знака реализует оператор подстановки, который обозначается S.

Например, построение функции Ф из функций F и f_i с помощью оператора суперпозиции можно записать в следующем виде:

Ф ::= S[F; f₁, f₂, ..., f_n].

Для r(y) ::= S[(x), (y)].

Рассмотрим оператор рекурсии. Он реализуется на основе двух функций, одна из которых имеет (n-1) независимую переменную, а другая, кроме указанных, еще две, т.е. (n+1).

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

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

f ::= R[f₁, f₂, x(y)], где f — получаемая функция;

f₁ — функция (n-1) независимых переменных;

f₂ — функция (n+1) независимых переменных;

x — главный из дополнительных аргументов;

y — вспомогательный аргумент.

Оператор рекурсии задает функцию с помощью двух условий, в которые входят функции f₁ и f₂.

Например, построение функции предшествования.

f(0) = f₁, f(i’) = f₂(i, f(i)), пр(0) = 0, пр(1) = 0, пр(2) = 1, пр(3) = 2 ... Здесь пр - это обозначение функции предшествования.

Рассмотрим оператор построения функции по первому нулю. Он по заданной функции, зависящей от (n+1) аргументов, строит новую функцию от n аргументов. Здесь вспомогательный аргумент — исчезает. Например, для функции вида: f::=[f₁(x)], х — исчезающий аргумент.

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

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

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

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

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