ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5083
Скачиваний: 26
16
2.2
Элементы
теории
рекурсивных
функций
В алгоритмических проблемах речь обычно идет о существова-
нии алгоритма для вычисления целочисленных значений функции,
зависящей от целочисленных аргументов, т.е. числовой функции.
К алгоритму вычисления числовой функции может быть сведен ал-
горитм вычисления любой имеющей практическое значение функ-
ции. Приведем пример. В математике рассматриваются функции,
определенные на континуальных множествах, например на множе-
стве точек некоторого отрезка. Однако на практике любая величина
может быть измерена лишь с ограниченной точностью, причем это
ограничение точности является принципиальным: для осуществле-
ния измерения с нулевой погрешностью требуется затратить беско-
нечно большое количество энергии. Таким образом, на практике
всегда существует некоторый «порог различимости», определяемый
точностью измерений, из-за этого множество значений любой фи-
зической величины оказывается счетным. Путем нумерации элемен-
ты счетного множества превращаются в целочисленные номера,
следовательно, алгоритм вычисления функции, определенной на
отрезке, сводится к алгоритму вычисления числовой функции.
Числовые функции, значения которых можно вычислять с по-
мощью некоторого (единого для данной функции) алгоритма, назы-
ваются вычислимыми функциями. В этом определении использу-
ется интуитивное понятие алгоритма, поэтому и понятие вычисли-
мой функции оказывается интуитивным. Тем не менее, при переходе
от алгоритмов к вычислимым функциям возникает одно очень важ-
ное обстоятельство. Совокупность процессов, удовлетворяющих
интуитивному понятию алгоритма, весьма обширна и трудно обо-
зрима. В то же время совокупность вычислимых функций для самых
разных пониманий этих процессов, оказалась одной и той же и при-
том легко описываемой в обычных математических терминах. Эта
точно описанная совокупность, совпадающая с совокупностью всех
вычислимых функций при самом широком понимании алгоритма,
носит название рекурсивных функций.
17
2.2.1
Основные
понятия
Рассмотрим два каких-либо множества:
X = {x
1
, x
2
, ...}, Y = {y
1
, y
2
, ...}.
Если некоторым элементам множества X поставлены в соот-
ветствие однозначно определенные элементы множества Y, то гово-
рят, что задана одноместная частичная функция из X в Y. Сово-
купность тех элементов множества X, у которых есть соответст-
вующие элементы в Y, называется областью определения функции,
а совокупность тех элементов множества Y, которые соответствуют
некоторым элементам множества X, называется совокупностью
значений (областью значений) функции. Если область определения
функции из X в Y совпадает с множеством X, то функция называет-
ся всюду определенной, или просто функцией.
Функцию можно определить и как подмножество F
⊂ X ×Y, ес-
ли для каждого элемента x
∈X, найдется не более одного элемента
y
∈Y так, что пара (x, y) ∈ F. При этом если для каждого элемента x
имеется элемент y, образующий с х пару (x, y)
∈ F, то функция явля-
ется всюду определенной, в противном случае она называется час-
тично определенной или частичной функцией.
Сопоставим с декартовым произведением двух множеств пря-
моугольную решетку, узлы которой взаимно однозначно соответст-
вуют элементам декартова произведения. Приведем пример, пояс-
няющий введенные понятия для множеств X = {x
1
, x
2
, x
3
, x
4
} и
Y = {y
1
, y
2
, y
3
}(рис. 2.1). На рис. 2.1,а изображено подмножество
декартова произведения множеств X и Y, не являющееся функцией;
на рис. 2.1,б – являющееся всюду определенной функцией; на рис.
2.1,в – частичной функцией. Частичная функция из X
1
× X
2
× … × X
n
в Y называется частичной функцией от n переменных, или
n-местной
частичной
функцией.
Обозначим
через
N
множество всех натуральных чисел. Частичная функция из
N
(k)
= N
× N × … × N в N называется k-местной числовой частич-
ной функцией.
Математика не накладывает никаких ограничений на соответ-
ствие (закон) применяеемый для определения функции. Допускается
любой мыслимый закон. Таким законом может быть некоторый ал-
18
горитм. В этом случае функцию называют вычислимой, так как из-
вестен способ получения ее значений.
Рекурсивными называют один частный класс вычислимых
функций. Алгоритмы, являющиеся законами их задания, называются
алгоритмами, сопутствующими рекурсивным функциям.
Для построения четко выделенного класса вычислимых функ-
ций нужны некоторые упрощающие предположения. Ранее уже от-
мечалась возможность выразить разные математические понятия с
помощью целых неотрицательных чисел. Поэтому ограничимся слу-
чаем, когда и независимые переменные, и функции могут принимать
только целые неотрицательные значения (натуральные числа).
Следующие числовые функции называются простейшими:
- функция следования s (x) = x´ = x + 1;
- функция-константа C
a
n
(x
1
, …, x
n
) = a;
- функция тождества I
m
n
(x
1
, …, x
n
) = x
m
(1
≤ m ≤ n ,
n = 1, 2, …).
Сопутствующие этим функциям алгоритмы будут наиболее
простыми, «одношаговыми».
Для функции следования (иначе – получение последователя)
сопутствующий алгоритм гласит: если функциональный знак имеет
вид s, то значением функции считать число, непосредственно сле-
дующее за числом, являющимся значением аргумента.
Сопутствующий алгоритм для функции-константы гласит: если
функциональный знак имеет вид C
a
n
, то любой совокупности значе-
ний аргументов данной функции ставится в соответствие ее значе-
ние a. Например:
C
0
1
(2) = 0, C
1
3
(4, 6, 7) = 1, C
5
n
(7, 8, …, 110) = 5.
Рис. 2.1 – Примеры подмножеств декартова произведения Х
× У
19
Для функции тождества сопутствующий алгоритм гласит: если
функциональный знак имеет вид I, то значением функции считать
значение m-го (считая в функциональной записи слева-направо) не-
зависимого переменного. Например,
I
2
3
(5, 8, 6) = 8, I
1
1
(3) = 3.
А вот запись I
4
3
(x, y, z) не имеет смысла, так как в ней n = 3,
m = 4, следовательно, не выполнено условие 1
≤ m ≤ n.
2.2.2
Преобразования
функций
Преобразования функций называются операторами. Рассмот-
рим основные операторы, с помощью которых, исходя из рекурсив-
ных функций, можно подучить новые функции, которые по опреде-
лению тоже будем считать рекурсивными. Эти операторы, по сути,
будут алгоритмами, на их основе можно получать новые алгоритмы.
Оператор подстановки (суперпозиции)
Пусть задано n каких-либо m-местных частичных функций
ƒ
1
,
…,
ƒ
n
из A в B и пусть задана частичная n-местная функция
ƒ из B в
C. Введем частичную функцию g из A в B такую, что
g (x
1
, …, x
m
) =
ƒ (ƒ
1
(x
1
, …,x
m
), …,
ƒ
n
(x
1
, …,x
m
))
для любых x
1
, …, x
m
из A.
Преобразование, с помощью которого получена функция g из
ƒ
1
, …,
ƒ
n
, называется оператором подстановки или суперпозиции и
обозначается S
n+1
, где (n+1) – число функций.
Алгоритм, сопутствующий этому оператору, гласит: «Значения
функций
ƒ
1
, …,
ƒ
n
принять за значения аргументов функции и вы-
числить ее значение».
Оператор подстановки определен для функций
ƒ
1
, …,
ƒ
n
с оди-
наковым числом переменных. Затруднение при подстановке функ-
ций с разным числом переменных преодолевается введением фик-
тивных переменных с помощью функций тождества. Например,
ϕ (x
1
, x
2
) =
ϕ ( I
1
3
( x
1
, x
2
, x
3
), I
2
3
( x
1
, x
2
, x
3
)) =
ψ (x
1
, x
2
, x
3
).
Здесь переменная x
3
является фиктивной.
Обозначим через F
n
множество всех частичных n-местных чи-
словых функций. Оператор S
n+1
является всюду определенной
(n+1)-местной функцией из F
n
×F
m
×…F
m
в F
m
.
Если обозначить через F множество всех частичных числовых
функций от произвольного числа переменных, то оператор S
n+1
20
можно рассматривать как частичную (n+1)-местную функцию из
F
(n+1)
в F.
Оператор примитивной рекурсии
Пусть заданы какие-либо частичные числовые функции: n-
местная g и (n + 2)-местная h. (n + 1)-местная частичная функция
ƒ
возникает из функций g и h с помощью оператора примитивной
рекурсии (или просто примитивной рекурсией), если для натураль-
ных значений x
1
,…, x
n
, y
ƒ (x
1
,…, x
n
, 0) = g (x
1
,…, x
n
),
ƒ (x
1
,…, x
n
, y+1) = h (x
1
,…, x
n
, y,
ƒ (x
1
,…, x
n
, 0)).
Этот оператор обозначим через R:
ƒ = R (g, h). Найдем после-
довательно значения
ƒ.
ƒ (x
1
,…, x
n
, 0) = g (x
1
,…, x
n
),
ƒ (x
1
,…, x
n
, 1) = h (x
1
,…, x
n
, 0, g (x
1
,…, x
n
)),
ƒ (x
1
,…, x
n
, m+1) = h (x
1
,…, x
n
, m,
ƒ (x
1
,…, x
n
, m)).
Совокупность этих равенств для любых функций g и h одно-
значно определяет значения функции
ƒ. Итак, для каждых двух час-
тичных числовых функций g от n переменных и h от (n+2) перемен-
ных существует одна и только одна функция
ƒ от (n+1) переменной,
возникающая примитивной рекурсией (по данной переменной x
n+1
).
При описании сути оператора примитивной рекурсии удобно не
указывать аргументов из заданных функций ни в его функциональ-
ной записи, ни в записях двух других функций, подразумевая эти
аргументы. Тогда можно сказать, что оператор примитивной рекур-
сии задает функцию с помощью двух условий, в которые входят
функции g и h:
ƒ(0) = g,
ƒ ( i´) = h (i, ƒ (i)).
Для удобства формулировки алгоритма условимся, что один из
дополнительных аргументов, вошедший вместе с аргументами пер-
вой функции в число аргументов вновь получаемой функции, назы-
вается главным дополнительным аргументом, а другой аргумент,
играющий вспомогательную роль при выполнении оператора, –
вспомогательным аргументом. Тогда алгоритм, сопутствующий опе-
ратору примитивной рекурсии, гласит: «Значением получаемой
функции для нулевого значения главного дополнительного аргумен-
та считать значение исходной функции n-го аргумента. Значением