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

Рекурсивные функции
1/16
Средняя оценка: 4.6/5 (всего оценок: 35)
Скачать (1221 Кб)
Код скопирован в буфер обмена
1

Первый слайд презентации

Рекурсивные функции

2

Слайд 2

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

3

Слайд 3

Оператор суперпозиции

4

Слайд 4

Примеры

5

Слайд 5

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

6

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

7

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

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

8

Слайд 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(I 3 3 ( x,y,f ( x,y ))) + 2 =R(I 1 1,[s 1 ;I 3 3 ]). Примеры доказательства вычислимости функций

9

Слайд 9

3. Умножение f ( x, y )= x * y f ( 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= I 3 1 (x,y,f(x,y))+I 3 3 (x,y,f(x,y)) x 2 =R(Z,[+;I 3 3,I 1 3 ]) 4. Симметрическая разность (абсолютная величина разности) Одноместная функция усеченного вычитания единицы определяется рекурсивно:

10

Слайд 10

11

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

12

Слайд 12

Оператор минимизации

13

Слайд 13: Использование оператора минимизации

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

14

Слайд 14

15

Слайд 15

Тезис Черча Функция называется частично-рекурсивной (вычислимой по Черчу), если она может быть получена из простейших функций с помощью конечного числа операторов суперпозиции, примитивной рекурсии и минимизации. Если такие функции оказываются всюду определенными, то они называются общерекурсивными функциями. Указанные операции могут быть выполнены в любой последовательности и любое конечное число раз. Таким образом, мы не просто задаем функцию, но и точно знаем, как её вычислять. Очевидно, каждая примитивно рекурсивная функция является частично рекурсивной, но обратное неверно. Введем обозначения: K ПРФ – класс примитивно рекурсивных функций; K ОРФ – класс общерекурсивных функций; K ЧРФ – класс частично рекурсивных функций. Тогда между этими классами имеется соотношения: K ПРФ  K ОРФ  K ЧРФ.

16

Последний слайд презентации: Рекурсивные функции

Похожие презентации

Ничего не найдено