Рекурсивные функции - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Рекурсивные функции. Доклад-сообщение содержит 62 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

1. Вычислимые функции

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

Если область определения функции из X в Y совпадает с множеством X, то функция называется всюду определенной Если область определения функции из X в Y совпадает с множеством X, то функция называется всюду определенной

Слайд 6

Описание слайда:

Функция у (x1, х2, ..., хn) называется вычислимой, если существует алгоритм, позволяющий вычислить ее значение по известным значениям аргументов

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

Какие функции могут быть вычислимыми? Какие функции могут быть вычислимыми? Как описать такие алгоритмически вычислимые функции? Исследование этих вопросов привело к созданию в 30х годах ХХ века теории рекурсивных функций (исторически первый подход к формализации понятия алгоритм)

Слайд 9

Описание слайда:

2. Построение вычислимой функции

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

2.1 Базисные функции

Слайд 13

Описание слайда:

1) Тождественное равенство нулю: 1) Тождественное равенство нулю: On (x1, x2,…, xn)= 0 n-местная функция (функция от n аргументов), всегда возвращающая 0.

Слайд 14

Описание слайда:

2) Функция следования 2) Функция следования S1(x) = x+1 Одноместная функция, сопоставляющая любому натуральному числу x непосредственно следующее за ним натуральное число x + 1

Слайд 15

Описание слайда:

3) Функция тождественного повтора одного из аргументов (функция проекции): 3) Функция тождественного повтора одного из аргументов (функция проекции): n-местная функция, сопоставляющая любому упорядоченному набору натуральных чисел число xm из этого набора.

Слайд 16

Описание слайда:

Пример1 Вычисление простейших функций

Слайд 17

Описание слайда:

2.2. Операторы

Слайд 18

Описание слайда:

1) Оператор суперпозиции (подстановки) Оператором суперпозиции называется подстановка в функцию от n переменных n функций от m одних и тех же переменных. Суперпозиция дает новую функцию от n переменных. Пусть m-местные функции f1(х1,х2,…,хm), f2(х1,х2,…,хm), …, fn(х1,х2,…,хm) подставляются в n-местную функцию g(х1,х2,…,хn). В результате получается n-местная функция h(у1,у2,…,уn) = g(f1(х1,х2,…,хm), f2(х1,х2,…,хm), …, fn(х1,х2,…,хm))

Слайд 19

Описание слайда:

Говорят, что функция h получена из функций g, f1,..., fn суперпозицией (или подстановкой). Обозначение: h = S(g, f1,..., fn ) Если умеем вычислять функции g, f1,..., fn , то функция h также может быть вычислена.

Слайд 20

Описание слайда:

Пример 2 Найти значение S(S1, O1) g(x) = S1, f (x)= O1 -> h(у) = g(f (x)) = S1(O1) Для этого значение простейшей функции О1 должно быть подставлено в S1(x) = х + 1. Но O1(х) = 0, следовательно, h(у) = S(S1, O1) = S1(O1) = 0+1 = 1.

Слайд 21

Описание слайда:

Пример 3 Найти значение S (I22, I11 ,О1) В этом случае конечная функция будет двухместной следовательно h(x1,x2) = I22(I11 ,01) = 01 = 0 .

Слайд 22

Описание слайда:

2) Оператор примитивной рекурсии Оператор примитивной рекурсии определяет (n+1)-местную функцию f через n-местную функцию g и (n+2)-местную функцию h так: f(х1,х2,…,хn,0) = g(х1,х2,…,хn), f(х1,х2,…,хn, y+1) = h(х1,х2,…,хn,y,f(х1,х2,…,хn,y)) Приведенная пара равенств называется схемой примитивной рекурсии

Слайд 23

Описание слайда:

Независимо от числа переменных в f рекурсия ведется только по одной переменной у. Остальные n переменных x1, x2, ..., xn на момент применения схемы зафиксированы и играют роль параметров. Независимо от числа переменных в f рекурсия ведется только по одной переменной у. Остальные n переменных x1, x2, ..., xn на момент применения схемы зафиксированы и играют роль параметров. При у=0 f(х1,..., xn,0) = g(x1,..., хn), При у=1 f(х1,..., xn,1) = h(x1,…,xn, 0 , f(x1,…,xn, 0)), При у=2 f(х1,..., xn,2) = h(x1,…,xn, 1 , f(x1,…,xn, 1)), …. f(х1,..., xn,y+1)= h(x1,…,xn, у, f(x1,…,xn,у))

Слайд 24

Описание слайда:

Если умеем находить значения функций g и h, то значения функции f(x1,..., xn, у + 1) можно вычислять «механически», находя последовательно значения на предыдущих шагах. Операцию примитивной рекурсии обозначают f = R (g,h)

Слайд 25

Описание слайда:

Пример 4. Пусть g(x) = x – функция от 1 переменной (n=1), h - функция от n+2 = 3 переменных h(x,y,z) = x+y+z Найти функцию f от 2x аргументов- результат применения оператора примитивной рекурсии к паре функций g и h

Слайд 26

Описание слайда:

f (x, 0) = g(x) = x f (x, 1) = h (x, 0, f(x,0)) = x+0+x = 2x f (x, 2) = h (x, 1, f(x,1)) = x+1+2x = 3x+1 f (x, 3) = h (x, 2, f(x,2)) = x+2+3x+1 = 4x+3 f (x, 4) = h (x, 3, f(x,3)) = x+3+4x+3 = 5x+6 f (x, 5) = h (x, 4, f(x,4)) = x+4+5x+6 = 6x+10 f (x, 6) = h (x, 5, f(x,5)) = x+5+6x+10 = 7x+15 …. f (x, y) = h (x, y-1, f(x,y-1)) = x+(y+1)*x+(y^2-y)/2

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

Пусть заданы два множества X и Y. Если некоторым элементам X поставлены в соответствие однозначно определенные элементы Y, то говорят, что задана частичная функция из Х в Y

Слайд 29

Описание слайда:

Частичная функция f (х1,х2,…,хn) называется примитивно рекурсивной, если ее можно получить конечным числом операций суперпозиции и примитивной рекурсии, исходя лишь из простейших функций S1, On и Inm

Слайд 30

Описание слайда:

Пример 5. Покажем, что функция константа является примитивно-рекурсивной f(x) = m = S1(...(S1(O(x)))...) m раз

Слайд 31

Описание слайда:

Пример 6. Покажем, что двухместная функция f(х,у) = х + у является примитивно-рекурсивной Так как функция f является функцией 2х аргументов, то для использования операции примитивной рекурсии мы должны иметь функцию g , зависящую от 1 аргумента, и функцию h , зависящую от 3 аргументов. Определим эти функции. При у=0 fсум(x, 0) = x+0= х = g(x) = I12(x,у) - функция проекции При у=1 fсум(x, 1) = х+1 = h(x, y, z) =S1(z) - функция следования Используя схему примитивной рекурсии получаем:

Слайд 32

Описание слайда:

f сум (x,0) = g(x) = x, f сум (x,0) = g(x) = x, f сум (x, 1) = h(x,0, f (x,0)) = S1(fсум (x,0)) = x +1 f сум (x, 2) = h(x, 1, fсум(x,1)) = S1(fсум(x,1)) = x + 2 . . . fсум(x, y) = h(x, y-1, fсум(x, y - 1)) = S1(fсум (x, y - 1)) = (x + y-1)+1= х+у Функция f(x,y) образуется из простейших функций следования и проекции операцией примитивной рекурсии и, следовательно, она сама примитивно рекурсивна.

Слайд 33

Описание слайда:

Пример 7. Покажем, что двухместная функция f(х,у) = х*у является примитивно-рекурсивной Пример 7. Покажем, что двухместная функция f(х,у) = х*у является примитивно-рекурсивной Для этого мы должны показать, что функция f можно получить из базовых функций или функций, частичная рекурсивность которых уже доказана, путем применения операторов суперпозиции и примитивной рекурсии

Слайд 34

Описание слайда:

Определим функции g и h Определим функции g и h При у=0 fумн(x, 0) = x*0= 0 = g(x) = O1(x) - баз.функц. тожд. равен. нулю При у=1 fумн(x, 1) = х*1 = х = h(x,y,z)= h(x,0,0)= х+fумн(x, 0) - прим. рек ф-я сложения Используя схему примитивной рекурсии получаем:

Слайд 35

Описание слайда:

fумн(x,0) = g(x) = 0, fумн(x,0) = g(x) = 0, fумн(x,1) = h(x,0, fумн(x,0)) = x+ fумн(x,0) = x +0=x fумн(x,2) = h(x,1, fумн(x,1)) = х+ fумн(x,1) = х+х = 2*х fумн(x,3) = h(x,2, fумн(x,2)) = х+ fумн(x,2) = х+2х = 3*х . . . fумн(x, y) = h(x, y-1, fумн(x, y - 1)) = х+ fумн(x,y-1)= х+(y-1)*х = = х+х*у-х = х*у

Слайд 36

Описание слайда:

Функция f(x,y)=х*у образуется из простейшей функции тождественного равенства нулю и примитивно-рекурсивной функции сложения операцией примитивной рекурсии и, следовательно, она сама примитивно-рекурсивна. Функция f(x,y)=х*у образуется из простейшей функции тождественного равенства нулю и примитивно-рекурсивной функции сложения операцией примитивной рекурсии и, следовательно, она сама примитивно-рекурсивна.

Слайд 37

Описание слайда:

Пример 7. Покажем, что двухместная функция f(х,у) = х^у является примитивно-рекурсивной Так как функция f является функцией 2х аргументов, то для использования операции примитивной рекурсии мы должны иметь функцию g , зависящую от 1 аргумента, и функцию h , зависящую от 3 аргументов. Определим эти функции.

Слайд 38

Описание слайда:

При у=0 fст(x, 0) = x^0= 1 = g(x) =S1(O1(x)) - суперпозиция нуль-функции и функции следования При у=1 fст(x, 1) = х^1 = х* х^0 При у=2 fст(x, 2) = х^2 = x*(х* х^0) h(x, y, z) =х*z — функция умножения Используя схему примитивной рекурсии получаем:

Слайд 39

Описание слайда:

f ст (x,0) g(x) 1, f ст (x,0) g(x) 1, f ст (x,1) h(x,0, f ст(x,0)) х f ст (x,0)) x*1 = x^1 f ст(x, 2) = h(x, 1, f ст(x,1)) = х* f ст(x,1) = х*х^1 =x^2 f ст(x, 3) = h(x, 2, f ст(x,2)) = х* f ст(x,2)= х*х^2= x^3 . . . f ст(x, y) = h(x, y-1, f ст(x, y - 1)) = х*f ст (x, y - 1) = =х*х^(y-1) = х^у

Слайд 40

Описание слайда:

Функция f(x,y)=х^у образуется из суперпозиции простейших функции тождественного равенства нулю, следования и примитивно-рекурсивной функции умножения операцией примитивной рекурсии и, следовательно, она сама примитивно-рекурсивна.

Слайд 41

Описание слайда:

Слайд 42

Описание слайда:

Слайд 43

Описание слайда:

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

Слайд 44

Описание слайда:

Однако, не все вычислимые функции можно описать как примитивно-рекурсивные (пример ф-я Аккермана) т. е. понятие примитивно-рекурсивная функция не является точным формальным аналогом неформального понятия алгоритм, им является понятие частично-рекурсивная функция

Слайд 45

Описание слайда:

Функция f(х1,х2,…,хn) называется частично рекурсивной, если ее можно получить с помощью конечного числа операторов суперпозиции, примитивной рекурсии и μ- оператора, исходя лишь из простейших функций S1, On и Imn

Слайд 46

Описание слайда:

3) μ-оператор (оператор минимизации для функции n аргументов) Пусть задана функция f(х1,х2,…,хn-1, y). Зафиксируем значения х1,х2,…,хn-1, и выясним, при каких у значение f(х1,х2,…,хn-1 ,y) = 0. Можно найти наименьшее из тех значений у, при которых f(х1,х2,…,хn-1 ,у) = 0. Примем обозначение: F(х1,х2,…,хn-1) = μy[f(х1,х2,…,хn-1,y) = 0] (читается: «наименьшее y такое, что f(х1,х2,…,хn-1,y) = 0», a μy называют μ -оператором или оператором минимизации).

Слайд 47

Описание слайда:

Оператор минимизации “следит”, при каком значении выбранного аргумента наблюдаемая им функция впервые опустится до нуля. Это значение выбранного аргумента и будет значением оператора минимизации. Например, для функции x-y, при х = 5, значение оператора минимизации также будет равно 5, поскольку двигаясь в значениях игрека от нуля получим нулевое значение функции именно при игрек равном 5.

Слайд 48

Описание слайда:

Работа μ-оператора Рассмотрим F(х1,х2,…,хn-1) = μy[f(х1,х2,…,хn-1,y) = 0], где y - выделенная переменная. Работу μ-оператора можно описать следующим образом; Выделяется переменная (здесь - у). Затем фиксируется значение остальных переменных (x1, ... , xn-1). Значение y последовательно увеличивается, начиная с нуля. Значением μ-оператора будет значение y, при котором функция впервые обратилась в ноль. Значение μ-оператора считается неопределенным, если функция вообще не принимает значения ноль, либо она принимает отрицательное значение до того как примет значение ноль.

Слайд 49

Описание слайда:

Для вычисления функции F: Для вычисления функции F: Вычисляем f(х1,х2,…,хn,0); если значение равно нулю, то полагаем F (х1,х2,…,хn) = 0. Если f(х1,х2,…,хn,0) ≠ 0, то переходим к следующему шагу. Вычисляем f(х1,х2,…,хn,1); если значение равно нулю, то полагаем F (х1,х2,…,хn) = 1. Если f(х1,х2,…,хn,1) ≠ 0, то переходим к следующему шагу и т.д. Если окажется, что для всех y функция f(х1,х2,…,хn,0) ≠ 0, то функция F (х1,х2,…,хn) считается неопределенной.

Слайд 50

Описание слайда:

Пример 8. работа μ-оператора Пусть функция g(х, y) = х - у + 3. Зафиксируем х = 1 F(x,y) = μy[g(1, y) = 0] = μy[1 - у + 3= 0] = 4 так как 1 - 4 + 3 = 0.

Слайд 51

Описание слайда:

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

Слайд 52

Описание слайда:

Рассмотрим как выполняются основные требования к алгоритмам для алгоритмической модели „частично-рекурсивные функции“

Слайд 53

Описание слайда:

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

Слайд 54

Описание слайда:

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

Слайд 55

Описание слайда:

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

Слайд 56

Описание слайда:

Вопросы к лекции 1. Как понятие алгоритма связано с понятием вычислимой функции? 2. Перечислите простейшие функции и элементарные операторы. 3. Почему примитивно-рекурсивную функцию нельзя считать точным формальным определением понятия алгоритм? 4. Как можно получить частично-рекурсивную функцию? 5. Сформулируйте определение алгоритма с позиций теории ЧРФ?

Слайд 57

Описание слайда:

Семинар

Слайд 58

Описание слайда:

Задание 1. Применение оператора суперпозиции Даны 3 функции от двух переменных: f1(x1, x2) = 2 x1+3x2 f2(x1, x2) = x1*x2 f3(x1, x2) = x1* и функция g(z1, z2, z3) = z1+z2* z3 Найти функцию h - суперпозицию функций f в функцию g h = S(g,f)

Слайд 59

Описание слайда:

Задание 2 (самостоятельно) Даны три одноместные функции: f1(x) = O1(x) f2(x) = O1(x) f3(x) = S1(10) и трехместная функция g(y1, у2, у3) = h = S (g, f1,f2,f3) - ?

Слайд 60

Описание слайда:

Задание 3 Применение оператора примитивной рекурсии Пусть g(x) = 0 – функция от 1 переменной h(x,y,z) = x+z – функция от 3 переменных Найти функцию f (x, y) — функцию от 2 переменных, путем применения оператора примитивной рекурсии к функциям g и h h = R(g, h) - ?

Слайд 61

Описание слайда:

Задание 4 (самостоятельно) Пусть g(x1,x2) = x1*x2 – функция от 2 аргументов h(x1,x2,x3,x4) = x1*x2+x3*x4 – функция от 4 аргументов Построить выражения для функции f (x1, x2, x3) от 3 аргументов, путем применения оператора примитивной рекурсии к функциям g и h для первых 6 шагов рекурсии h = R(g, h) - ?

Слайд 62

Описание слайда:

Задание 5 Применение оператора минимизации Рассмотрим функцию F(x,y) = x - y, которая может быть получена с помощью применения оператора минимизации к функции f(x,y,z) = x-y-z: F(x,y) = μz [x-y-z=0] Вычислим, например, F(7,2), т.е. значение функции при y = 2 и х = 7. При z=5, μz [x-y-z=0] Таким образом, найдено значение функции F(7,2) = 5.

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

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