Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Рекурсивные функции
Содержание
- 1. Рекурсивные функции
- 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=
- 10. Слайд 10
- 11. Операции конечного суммирования и конечного произведения
- 12. Оператор минимизации
- 13. Использование оператора минимизации Используя минимизацию можно
- 14. Слайд 14
- 15. Тезис ЧерчаФункция называется частично-рекурсивной (вычислимой по Черчу),
- 16. Слайд 16
- 17. Скачать презентанцию
Эта модель рассматривает алгоритм как способ формирования одних вычислимых функций из других, т.е. одни функции конструктивно определяются из других. Все элементарные функции - всюду определенные и алгоритмически вычислимые.
Слайды и текст этой презентации
Слайд 2 Эта модель рассматривает алгоритм как способ формирования одних вычислимых функций
из других, т.е. одни функции конструктивно определяются из других.
функции - всюду определенные и алгоритмически вычислимые.
Слайд 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]).
Примеры доказательства вычислимости
функций
Слайд 93. Умножение
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= I31 (x,y,f(x,y))+I33 (x,y,f(x,y))
x2 =R(Z,[+;I33,I13])
4. Симметрическая разность (абсолютная величина разности)
Одноместная функция усеченного вычитания
единицы определяется рекурсивно:![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. Симметрическая разность (абсолютная величина разности)Одноместная](/img/thumbs/2d0660b52dc93aefe0e8f5544e8d9491-800x.jpg "Рекурсивные функции 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")
Слайд 13
Использование оператора минимизации
Используя минимизацию можно получать частично –определенные функции из
всюду определенных функций.
Пример 2. Пусть g(x) = [x/2]. Найдем функцию
f(x), которая получается в результате применения оператора минимизации к этой всюду определенной функции. При каждом конкретном x значение f(x) равно минимальному корню уравнения [y/2] = x. Это уравнение имеет два корня: 2x и 2x+1. Поэтому f(x)=2x.
Слайд 15Тезис Черча
Функция называется частично-рекурсивной (вычислимой по Черчу), если она может
быть получена из простейших функций с помощью конечного числа операторов
суперпозиции, примитивной рекурсии и минимизации.Если такие функции оказываются всюду определенными, то они называются общерекурсивными функциями.
Указанные операции могут быть выполнены в любой последовательности и любое конечное число раз. Таким образом, мы не просто задаем функцию, но и точно знаем, как её вычислять.
Очевидно, каждая примитивно рекурсивная функция является частично
рекурсивной, но обратное неверно.
Введем обозначения:
KПРФ – класс примитивно рекурсивных функций;
KОРФ – класс общерекурсивных функций;
KЧРФ – класс частично рекурсивных функций.
Тогда между этими классами имеется соотношения:
KПРФ KОРФ KЧРФ.
