'

Рекурсивные функции Простейшие функции Операция суперпозиции

Понравилась презентация – покажи это...





Слайд 0

Рекурсивные функции Простейшие функции Операция суперпозиции


Слайд 1

Алгоритмический процесс можно рассматривать как процесс вычисления значений некоторой функции f Такие функции называются вычислимыми


Слайд 2

Интуитивное понятие вычислимой функции заменим на точное понятие частично рекурсивной функции


Слайд 3

Рассмотрим некоторый набор простейших функций, вычислимость которых очевидна Простейшие функции Простейшими функциями называются следующие арифметические функции: 1) Нулевая функция Оn(x1, x2, … , xn) = 0 O(x) = 0 2) Функция следования ?(x) = x + 1, x ? N 3) Функция проецирования (выбора) Im n(x1, x2, … , xn) = xm Вспомните понятие арифметической функции


Слайд 4

Замечание Вычислимость функции проецирования обеспечивается нашей способностью найти в строке (x1, x2, … , xn) место с номером m и указать число на этом месте


Слайд 5

Пусть заданы арифметические функции: f1(x1, x2, … , xn), f2(x1, x2, … , xn), …, fm(x1, x2, … , xn), ?(y1, y2, … , ym) Операция подстановки (суперпозиции) Говорят, что функция ?(x1, x2, … , xn) получена из функций ? и f1, f2, …, fm операцией подстановки (суперпозиции), если: Обозначение:


Слайд 6

Пример 1 Операция подстановки (суперпозиции)


Слайд 7

Пример 1 Операция подстановки (суперпозиции)


Слайд 8

Правильное применение суперпозиции: необходимо соблюдать требования к набору аргументов каждой функции Операция подстановки (суперпозиции)


Слайд 9

Пример 1 Операция подстановки (суперпозиции) Преобразуем функции f1 и f2 так, чтобы они удовлетворяли требованиям к аргументам для применения суперпозиции Корректно


Слайд 10

Замечание Такое применение функции проецирования предложил К.Гёдель (1934) Все функции fi, i = 1,…m зависят от n переменных, а функция ? имеет m переменных (по количеству функций fi) Результат подстановки, функция ? зависит от n переменных


Слайд 11

Добиться выполнение условия на количество аргументов у функций можно введением фиктивных переменных и применения функции проецирования Im n


Слайд 12

Пример 2 Записать корректно подстановку Решение


Слайд 13

Пример 3 Вычислить функцию-константу: Решение


Слайд 14

Литература Ильиных А.П. Теория алгоритмов. Учебное пособие. – Екатеринбург, 2006. - 149 с. Теория алгоритмов / Электронный учебник http://ric.uni-altai.ru/Fundamental/teor-alg/ Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. - СПб.: Лань, 2009. - 288 с.


Слайд 15

Нельзя научить, можно научиться


×

HTML:





Ссылка: