- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Prezentatsia_Chast2 презентация
Содержание
- 1. Prezentatsia_Chast2
- 2. Эта модель рассматривает алгоритм как способ формирования
- 3. Оператор суперпозиции
- 4. Примеры
- 5. Оператор примитивной рекурсии
- 6. Оператор примитивной рекурсии
- 7. Функция называется примитивно – рекурсивной, если она
- 8. Функция – константа f(x) = m
- 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);
- 11. Операции конечного суммирования и конечного произведения
- 12. Оператор минимизации
- 13. Использование оператора минимизации Используя минимизацию
- 15. Тезис Черча Функция называется частично-рекурсивной (вычислимой
Эта модель рассматривает алгоритм как способ формирования одних вычислимых функций из других, т.е. одни функции конструктивно определяются из других.
Все элементарные функции - всюду определенные и алгоритмически вычислимые.
Слайд 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]).
+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. Симметрическая разность (абсолютная величина разности)
Одноместная функция усеченного вычитания единицы определяется рекурсивно:
4. Симметрическая разность (абсолютная величина разности)
Одноместная функция усеченного вычитания единицы определяется рекурсивно:
Слайд 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ЧРФ.
Если такие функции оказываются всюду определенными, то они называются общерекурсивными функциями.
Указанные операции могут быть выполнены в любой последовательности и любое конечное число раз. Таким образом, мы не просто задаем функцию, но и точно знаем, как её вычислять.
Очевидно, каждая примитивно рекурсивная функция является частично
рекурсивной, но обратное неверно.
Введем обозначения:
KПРФ – класс примитивно рекурсивных функций;
KОРФ – класс общерекурсивных функций;
KЧРФ – класс частично рекурсивных функций.
Тогда между этими классами имеется соотношения:
KПРФ ⊆ KОРФ ⊆ KЧРФ.
