Презентация на тему Рекурсивные функции

Содержание

2. Эта модель рассматривает алгоритм как способ формирования
3. Оператор суперпозиции
4. Примеры
5. Оператор примитивной рекурсии
6. Оператор примитивной рекурсии
7. Функция называется примитивно – рекурсивной, если она
8. Функция – константаf(x) = m s(s(s…s(Z(x))…))
9. 3. Умножениеf(x,y)=x*yf(x,0)=x*0=0;f(x,y+1)=x*(y+1)=x*y+x=f(x,y)+xДоказательство:f(x,0)=g(x)=0=Z(x);f(x,y+1) = h(x,y,z) = h(x,y,f(x,y)) =x+z=
11. Операции конечного суммирования и конечного произведения
12. Оператор минимизации
13. Использование оператора минимизации Используя минимизацию можно
15. Тезис ЧерчаФункция называется частично-рекурсивной (вычислимой по Черчу),
16. Скачать презентацию
17. Похожие презентации

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

Функция называется примитивно – рекурсивной, если она является элементарной или может быть

Функция – константаf(x) = m s(s(s…s(Z(x))…)) m-раз2. Сложение f(x,y)=x+y f(x,0)=x; f(x,y+1)=x+(y+1)=(x+y)+1=f(x,y)+1Доказательство:f(x,0)=g(x)=x=I(x);f(x,y+1) = h(x,y,z)

3. Умножениеf(x,y)=x*yf(x,0)=x*0=0;f(x,y+1)=x*(y+1)=x*y+x=f(x,y)+xДоказательство:f(x,0)=g(x)=0=Z(x);f(x,y+1) = h(x,y,z) = h(x,y,f(x,y)) =x+z= I31 (x,y,f(x,y))+I33 (x,y,f(x,y)) x2 =R(Z,[+;I33,I13])4.

Операции конечного суммирования и конечного произведения

Использование оператора минимизации Используя минимизацию можно получать частично –определенные функции из

Тезис ЧерчаФункция называется частично-рекурсивной (вычислимой по Черчу), если она может быть получена

Слайды презентации

Слайд 2 Эта модель рассматривает алгоритм как способ формирования одних

Эта модель рассматривает алгоритм как способ формирования одних вычислимых функций из

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

из других.

Все элементарные функции - всюду определенные и алгоритмически вычислимые.

Слайд 3 Оператор суперпозиции

Слайд 4 Примеры

Слайд 5 Оператор примитивной рекурсии

Слайд 6 Оператор примитивной рекурсии

Слайд 7 Функция называется примитивно – рекурсивной, если она является

Функция называется примитивно – рекурсивной, если она является элементарной или может

элементарной или может быть получена из элементарных функций с

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

Оператор примитивной рекурсии

Слайд 8 Функция – константа
f(x) = m s(s(s…s(Z(x))…))

m-раз
2. Сложение
f(x,y)=x+y
f(x,0)=x;
f(x,y+1)=x+(y+1)=(x+y)+1=f(x,y)+1
Доказательство:
f(x,0)=g(x)=x=I(x);
f(x,y+1) = h(x,y,z) = h(x,y,f(x,y)) = s(I33 (x,y,f(x,y)))
+2

=R(I11,[s1;I33]).

Примеры доказательства вычислимости функций

Слайд 9 3. Умножение
f(x,y)=xy
f(x,0)=x0=0;
f(x,y+1)=x(y+1)=xy+x=f(x,y)+x
Доказательство:
f(x,0)=g(x)=0=Z(x);
f(x,y+1) = h(x,y,z) = h(x,y,f(x,y)) =x+z= I31

3. Умножениеf(x,y)=x*yf(x,0)=x*0=0;f(x,y+1)=x*(y+1)=x*y+x=f(x,y)+xДоказательство:f(x,0)=g(x)=0=Z(x);f(x,y+1) = h(x,y,z) = h(x,y,f(x,y)) =x+z= I31 (x,y,f(x,y))+I33 (x,y,f(x,y)) x2

(x,y,f(x,y))+I33 (x,y,f(x,y))
x2 =R(Z,[+;I33,I13])
4. Симметрическая разность (абсолютная величина разности)

Одноместная

функция усеченного вычитания единицы определяется рекурсивно:

Слайд 10

Слайд 11 Операции конечного суммирования и конечного произведения

Слайд 12 Оператор минимизации

Слайд 13 Использование оператора минимизации
Используя минимизацию можно получать частично –определенные

Использование оператора минимизации Используя минимизацию можно получать частично –определенные функции

функции из всюду определенных функций.

Пример 2. Пусть g(x) =

[x/2]. Найдем функцию f(x), которая получается в результате применения оператора минимизации к этой всюду определенной функции. При каждом конкретном x значение f(x) равно минимальному корню уравнения [y/2] = x. Это уравнение имеет два корня: 2x и 2x+1. Поэтому f(x)=2x.

Слайд 14

Слайд 15
Тезис Черча
Функция называется частично-рекурсивной (вычислимой по Черчу), если

Тезис ЧерчаФункция называется частично-рекурсивной (вычислимой по Черчу), если она может быть

она может быть получена из простейших функций с помощью

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

Введем обозначения:
KПРФ – класс примитивно рекурсивных функций;
KОРФ – класс общерекурсивных функций;
KЧРФ – класс частично рекурсивных функций.

Тогда между этими классами имеется соотношения:
KПРФ ⊆ KОРФ ⊆ KЧРФ.