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


Лекция 4

Содержание

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

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

Слайд 1Лекция 4
Рекурсивные функции

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

Слайд 2Опр.
Пусть заданы два множества X и Y. Если некоторым элементам

X поставлены в соответствие однозначно определенные элементы Y, то говорят,

что задана частичная функция из Х в Y
(f: X -> Y)
Опр.Пусть заданы два множества X и Y. Если некоторым элементам X поставлены в соответствие однозначно определенные элементы

Слайд 3Опр.
Совокупность тех элементов множества X, у которых есть соответствующие элементы

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

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

Слайд 4Опр.
Если область определения функции из X в Y совпадает с

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

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

Слайд 5опр
Функция у(x1, х2, ..., хn) называется (эффективно) вычислимой, если существует

алгоритм, позволяющий вычислить ее значение по известным значениям аргументов

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

Слайд 6Простейшие числовые функции
S1(x) = х + 1 - это одноместная

функция следования;
0n(х1,х2,…,хn) = 0 - это n-местная функция тождественного равенства

нулю;
Inm (х1,х2,…,хn) = хm (1 ≤ m≤n; n = 1, 2, ...) - n-местная функция тождественного повторения значения одного из своих аргументов.
Простейшие числовые функцииS1(x) = х + 1 - это одноместная функция следования;0n(х1,х2,…,хn) = 0 - это n-местная

Слайд 7Суперпозиция частичных функций
Пусть 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))
Суперпозиция частичных функций Пусть m-местные функцииf1(х1,х2,…,хm), f2(х1,х2,…,хm), …, fn(х1,х2,…,хm) подставляются в n-местную функцию g(х1,х2,…,хn). В результате получается

Слайд 8Опр.
Говорят, что функция h получена из функций g, f1,..., fn

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

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

Слайд 9Пример 1
Найти значение S(S1, O1).
g(x) = S1, f

(x)= O1 -> h(x) = g(f (x)) = S1(O1)
Для

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

Слайд 10Пример 2

Найти значение S (I22, I11 ,О1).
В этом случае конечная

функция будет двуместной (n = 3 - 1 =2), следовательно

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

Слайд 11Примитивная рекурсия
Пусть заданы частичные функции:
g (х1,х2,…,хn)
h(х1,х2,…,хn, к,

y).
Говорят, что (n + 1)-местная частичная функция f образуется из

функций g и h посредством примитивной рекурсии, если для всех натуральных значений х1,х2,…,хn, у справедливо:
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))
Примитивная рекурсияПусть заданы частичные функции: g (х1,х2,…,хn) h(х1,х2,…,хn, к, y).Говорят, что (n + 1)-местная частичная функция f

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

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

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

Слайд 13Пример 3
Доказать, что двуместная функция f(х,у) = х + у

является примитивно-рекурсивной.
Данная функция может быть представлена:
x+0 = x= I11(x),
x+(y+

1) = (х+у)+1 = S1(x+y).
Следовательно, функция f(x,y) образуется из примитивно рекурсивных функций операцией примитивной рекурсии и, следовательно, она сама примитивно рекурсивна.
Пример 3 Доказать, что двуместная функция f(х,у) = х + у является примитивно-рекурсивной. Данная функция может быть

Слайд 14Пример 4
Найти значение функции f(2,3), если она задана следующими соотношениями:
f(х,0)

= 0,
f(x, y+1)=x + f(y,x)
В данном случае g(х) = 0,

h(x,y,z) = x + z.
Так как f(x,0) = g(х) = 0 при любом х, то и
f(2,0) = 0, а другие значения можно вычислить последовательно:
f(2,1) = h(2,0,0) = 2 + 0 = 2;
f(2,2) = h(2,1,2) = 2 + 2 = 4;
f(2,3) =h(2,2,4) = 2 + 4 = 6.

Несложно доказать, что в данном примере
f(x,y) = ху
Пример 4 Найти значение функции f(2,3), если она задана следующими соотношениями:f(х,0) = 0,f(x, y+1)=x + f(y,x)В данном

Слайд 15Операция минимизации для функции двух аргументов

Пусть задана некоторая функция f(x,y).

Зафиксируем значение x и выясним, при каких у

значение f(x,y) = 0.
Можно найти наименьшее из тех значений у , при которых f(х,у) = 0.

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

Слайд 16Операция минимизации функции многих переменных

Пусть задана функция 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»).
Операция минимизации функции многих переменных Пусть задана функция f(х1,х2,…,хn-1, y). Зафиксируем значения х1,х2,…,хn-1, и выясним, при каких

Слайд 17функция многих переменных: F( х1,х2,…,хn) = μy[f(х1,х2,…,хn,y) = 0]
Для вычисления функции

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) считается неопределенной.
функция многих переменных: F( х1,х2,…,хn) = μy[f(х1,х2,…,хn,y) = 0] Для вычисления функции F:Вычисляем f(х1,х2,…,хn,0); если значение равно

Слайд 18Пример 5
Рассмотрим функцию F(x,y) = x - y, которая может

быть получена с помощью оператора минимизации к функции f(x,y,z) =

x-y-z:
F(x,y) = μz [x-y-z=0 или y + z =x] = μz[ I23 (x, y, z) + I33 (x, y, z) = I13(x, y, z)]

Вычислим, например, F(7,2), т.е. значение функции при y = 2 и х = 7. Будем z придавать последовательные значения:
z=0, 2 + 0 = 2≠7,
z=1, 2 + 1 = 3≠7,
z=2, 2 + 2 = 4≠7,
z=3, 2 + 3 = 5≠7,
z=4, 2 + 4 = 6≠7,
z=5, 2 + 5 = 7 = 7.
Таким образом, найдено значение функции F(7,2) = 5.
Пример 5 Рассмотрим функцию F(x,y) = x - y, которая может быть получена с помощью оператора минимизации

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

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

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

Слайд 20тезис Черча
Класс алгоритмически вычислимых (частичных) числовых функций совпадает с классом

всех частично рекурсивных функций.

тезис ЧерчаКласс алгоритмически вычислимых (частичных) числовых функций совпадает с классом всех частично рекурсивных функций.

Слайд 21Контрольные вопросы и задания
Для чего необходимо формализовать понятие алгоритма?
Что

означает фраза: «Машины Поста и Тьюринга являются абстрактными машинами»?
Для

чего предназначены машины Поста и Тьюринга?
 Как «устроена» машина Тьюринга?
 Каков принцип исполнения программы машиной Тьюринга?
Контрольные вопросы и задания Для чего необходимо формализовать понятие алгоритма? Что означает фраза: «Машины Поста и Тьюринга

Слайд 22Вопросы
1. Дайте определение нормального алгоритма Маркова.
2. В чем состоит принцип нормализации

алгоритмов?
3.Перечислите простейшие функции.
4. Перечислите операторы.
5. Чем отличается

частично рекурсивная функция от примитивно-рекурсивной?
6. Дайте определение частично-рекурсивной функции
Вопросы1. Дайте определение нормального алгоритма Маркова. 2. В чем состоит принцип нормализации алгоритмов? 3.Перечислите простейшие функции. 4. Перечислите операторы.

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика