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

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

Примитивно-рекурсивные функции, слайд №1

Примитивно-рекурсивные функции, слайд №2

Примитивно-рекурсивные функции, слайд №3

Примитивно-рекурсивные функции, слайд №4

Примитивно-рекурсивные функции, слайд №5

Примитивно-рекурсивные функции, слайд №6

Примитивно-рекурсивные функции, слайд №7

Примитивно-рекурсивные функции, слайд №8

Примитивно-рекурсивные функции, слайд №9

Примитивно-рекурсивные функции, слайд №10

Примитивно-рекурсивные функции, слайд №11

Примитивно-рекурсивные функции, слайд №12

Примитивно-рекурсивные функции, слайд №13

Примитивно-рекурсивные функции, слайд №14

Примитивно-рекурсивные функции, слайд №15

Примитивно-рекурсивные функции, слайд №16

Содержание ▲

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

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

Слайд 1

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

Примитивно-рекурсивные функции

Слайд 2

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

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

Слайд 3

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

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

Слайд 4

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

Простейшие базисные функции:

Слайд 5

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

Оператор суперпозиции из функций f(x1, . . . , xm), f1(x1, . . . , xn), . . . , fm(x1, . . . , xn) строит новую функцию g(x1, . . . , xn) = f(f 1(x1, . . . , xn), . . . fm (x1, . . . , xn)). Обозначим оператор суперпозиции через S(f, f1, . . . , f m) или, с явным указанием числа аргументов функций, Snm(f, f 1,…,f m).

Слайд 6

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

Пример Благодаря наличию функций выбора, стандартное представление суперпозиции с точным определением числа аргументов у всех функций f1, f2,..., fm не уменьшает возможностей самого оператора суперпозиции, т.к. любую подстановку функции в функцию можно выразить через оператор S и функцию I. Для функций h(x, y) = x + y, f(x) = 3x − 1, g(x, y, z) = x/(y + z) выражение h(f(y), g(x, y, z)) = 3y − 1 + x/(y + z) можно представить в виде стандартной суперпозиции h(f(I32 (x, y, z)), g(x, y, z)).

Слайд 7

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

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

Слайд 8

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

Вычисление рекурсивной функции Для того, чтобы в некоторой точке (x1, . . . , xn, y) вычислить значение функции, заданной оператором примитивной рекурсии, можно выполнить следующую конечную последовательность вычислений: f(x1, . . . , xn, 0) = g(x1, . . . , xn), f(x1, . . . , xn, 1) = h(x1, . . . , xn, 0, f(x1, . . . , xn, 0)), . . . f(x1, . . . , xn, y) = h(x1, . . . , xn, y − 1, f(x1, . . . , xn, y − 1)). Существенной характеристикой оператора примитивной рекурсии является такое его важнейшее свойство, что независимо от числа аргументов функции f рекурсия ведется только по одному аргументу, остальные аргументы зафиксированы на момент применения рекурсии.

Слайд 9

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

Слайд 10

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

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

Слайд 11

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

Теорема 1 Примитивно рекурсивные функции всюду определены. Доказательство. В соответствии с рекурсивным вариантом определения примитивно–рекурсивной функции достаточно рассмотреть три шага доказательства. Очевидно, что простейшие функции всюду определены. Из определенных всюду функций с помощью оператора суперпозиции можно получить только всюду определенные функции. Из определенных всюду функций в соответствии с алгоритмом вычисления функций, заданных оператором примитивной рекурсии, также получаем всюду определенные функции. ч.т.д.

Слайд 12

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

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

Слайд 13

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

Примеры ПРФ. Доказательство ПРФ по определению f(x)=k (функция-константа) f(x)=s’(s’(…s’(0(x)))), если применить функцию следования конечное число раз, равное константе k. f(x)=x Первый способ доказательства: f(x)= I11 (x) Второй способ доказательства: f(0)=0=const – что const – ПРФ – доказано f(x+1)=x+1=s’(x)=s’(f(x))=I22 (x, s’(f(x))) – получено с помощью конечного числа ПРФ, операторов ПР и суперпозиции f(x,y)=x+y f(x,0)=x – ПРФ f(x,y+1)=x+y+1=f(x,y)+1=s’(f(x,y))= I33 (x, y, s’(f(x,y)))