Каталог книг

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

Перейти в магазин

Сравнить цены

Описание

Брошюра знакомит читателя с алгоритмически вычислимыми функциями натурального аргумента - рекурсивными функциями. Вначале изучается простейший тип рекурсивных функций - примитивно рекурсивные функции. Затем происходит расширение круга вычислимых функций: рассматриваются частично определенные вычислимые функции, а также всюду определенные вычислимые функции, не являющиеся примитивно рекурсивными. В заключение определяются абстрактные вычислительные устройства - машины Тьюринга, и класс функций, вычислимых на машинах Тьюринга, связывается с классом частично рекурсивных функций. Для школьников старших классов и студентов вузов, знакомящихся с основами теории алгоритмов.

Сравнить Цены

Предложения интернет-магазинов
С. С. Марченков Рекурсивные функции С. С. Марченков Рекурсивные функции 289 р. ozon.ru В магазин >>
Н. К. Верещагин, А. Шень Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции Н. К. Верещагин, А. Шень Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции 172 р. ozon.ru В магазин >>
Д. Ш. Матрос, Г. Б. Поднебесова Теория алгоритмов Д. Ш. Матрос, Г. Б. Поднебесова Теория алгоритмов 286 р. ozon.ru В магазин >>
С. С. Марченков Элементарные рекурсивные функции С. С. Марченков Элементарные рекурсивные функции 114 р. ozon.ru В магазин >>
Вадим Дунаев Базы данных. Язык SQL для студента Вадим Дунаев Базы данных. Язык SQL для студента 69 р. litres.ru В магазин >>
В. Босс Лекции по математике. Том 6. Алгоритмы, логика, вычислимость. От Диофанта до Тьюринга и Гёделя В. Босс Лекции по математике. Том 6. Алгоритмы, логика, вычислимость. От Диофанта до Тьюринга и Гёделя 484 р. ozon.ru В магазин >>
Арбалет рекурсивный Арбалет рекурсивный "Man Kung", цвет: черный, 95 Lbs 5490 р. ozon.ru В магазин >>

Статьи, обзоры книги, новости

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

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

1. множество N натуральных чисел содержит 0 (нуль), т.е. N=<0,1,2,3. >;

2. рассматриваемые функции f=f(x1,x2,…,xn) определены только тогда, когда переменные принимают значения из N, т.е. xi∈N;

3. область значений функций D⊆N;

4. рассматриваемые функции f=f(x1,x2,…,xn) могут быть частично определенные, т.е. определенные не для всех наборов натуральных чисел.

Введём в рассмотрение простейшие функции:

Эти функции могут быть вычислены с помощью соответствующего механического устройства (например, на машине Тьюринга). Определим операторы, которые по одной или нескольким заданным функциям строят новые функции.

Мы говорим, что функция φ получается применением оператора суперпозиции S k+1 к функциям f,f1,…,fk, и пишем φ=S k+1 (f,f1,…,fk). Например, S 2 (s,o)=s(o(x)), т.е. функция, тождественно равная 1, а S 2 (s,s)=s(s(x)) - это функция у(x)=x+2.

Эти равенства определяют функцию f(x1,x2,…,xn+1) однозначно. Функция f называется функцией, полученной с помощью оператора R примитивной рекурсии. Используется запись f=R(g,h).

Индуктивное определение функции (продемонстрированное в операторе примитивной рекурсии) в математике не редкость. Например, индуктивно определяются:

1) степень с натуральным показателем: a 0 =1, a n+1 =a n ·a;

Определение.Функции, которые могут быть получены из простейших о(x)=0, s(x)=x+1, In m (x1. xn)=xm применением конечного числа раз операторов суперпозиции и примитивной рекурсии, называются примитивно рекурсивными.

Проверим, что функция u(x,y)=x+y является примитивно рекурсивной. Действительно, мы имеем: u(x,0)=0, u(x,y+1)=x+y+1=u(x,y)+1. Это есть схема примитивной рекурсии, так как x1 1 (x), а u(x,y)+1=s(u(x,y))=S 2 (s,u). Здесь g(x)=x1 2 , а h(x,y,u)=s(u)=S 2 (s,I3 3 ).

Аналогично доказывается, что функции m(x,y)=x·y, d(x,y)=x y (считаем по определению 0 0 =1), fact(x)=x! и многие другие являются примитивно рекурсивными.

Отметим; что примитивно рекурсивные функции всюду определены (т.е. определены для всех значений их аргументов). Действительно, простейшие функции o, s, In m являются всюду определёнными, а применение операторов суперпозиции и примитивной рекурсии ко всюду определённым функциям даёт также всюду определённые функции. Значит, такая функция, как

примитивно рекурсивной быть не может. Рассматривать функцию f(x,y)=x-y здесь мы не имеем права, так как значения функций должны быть натуральными числами (поэтому не отрицательными). Однако, можно рассмотреть функцию

Проверим, что она примитивно рекурсивна. Докажем вначале, что функция φ(x)=x÷1 примитивно рекурсивна. Действительно, φ(0)=0. φ(y+1)=(y+1)÷1=y, что служит схемой примитивной рекурсии для функции x÷1. Наконец, x÷0=x, x÷(y+1)=(x÷y)÷1=φ(x÷y) ? схема примитивной рекурсии для x÷y.

Существенно более широким классом функций, чем примитивно рекурсивные функции, является класс рекурсивных функций (определение см. ниже). В литературе эти функции называют также частично рекурсивными. Для их определения введём ещё один оператор.

Если такого y нет, то считаем, что f(x1,x2,…,xn,xn+1) не определено. Итак, возможны три случая:

Если имеет место 1-й случай, то g(x1,x2,…,xn,xn+1)=y, а если 2-й или 3-й, то g(x1,x2,…,xn,xn+1) не определено. Про функцию g полученную таким образом, говорят, что она получена из f применением оператора минимизации М. Мы пишем g=Мf.

Оператор минимизации - это очевидное обобщение оператора взятия обратной функции. Обобщение довольно глубокое, так как от функции f не требуется, чтобы она была взаимно однозначной (по переменной xn+1).

Определение. Функции, которые могут быть получены из простейших о(x)=0, s(x)=x+1, In m (x1. xn)=x применением конечного числа раз операторов суперпозиции, примитивной рекурсии и минимизации, называются рекурсивными.

Класс рекурсивных функций шире класса примитивно рекурсивных функций хотя бы по тому, что он содержит не только всюду определённые функции. Докажем, например, что функция

является рекурсивной. Действительно, f(x,y)=min(z|y+z=x), а ранее было установлено, что функция u(x,y)=x+y примитивно рекурсивна.

Рекурсивные функции отражают наше интуитивное представление о функциях, вычислимых некоторым механическим устройством. В частности, они вычислимы на машинах Тьюринга. Наоборот, всякая функция, вычислимая на машине Тьюринга является рекурсивной. Мы не будем проверять этот факт, так как это потребовало бы слишком много времени и места.

Отметим, что не всякая функция натуральных аргументов является рекурсивной, даже не всякая функция одного аргумента. Существование нерекурсивных функций и является "математической причиной" наличия алгоритмически неразрешимых задач.

Источник:

tablica-istinnosti.ru

Теория алгоритмов, Рекурсивные функции и алгоритмы

Теория алгоритмов Рекурсивные функции и алгоритмы Рекурсивные функции

а) Терминологическое введение

По сути один и тот же метод, применительно к различным областям носит различные названия – это индукция, рекурсия и рекуррентные соотношения – различия касаются особенностей использования.

Под индукцией понимается метод доказательства утверждений, который строится на базе индукции при n=0,1, затем утверждение полагается правильным при n=n b и проводится доказательство для n+1.

Под рекурсией понимается метод определения функции через её предыдущие и ранее определенные значения, а так же способ организации вычислений, при котором функция вызывает сама себя с другим аргументом.

Термин рекуррентные соотношения связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии.

Основной задачей исследования рекурсивно заданных функций является получение f(n) в явной или как еще говорят «замкнутой» форме, т.е. в виде аналитически заданной функции. В связи с этим рассмотрим ряд примеров:

б) Примеры рекурсивного задания функций

Последовательная подстановка дает – f(n)=1*2*3*…*n = n!

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

Эта рекурсивная функция определяет числа Фибоначчи: 1 1 2 3 5 8 13, которые достаточно часто возникают при анализе различных задач, в том числе и при анализе алгоритмов. Отметим, что асимптотически

f(n)= f(n-1)+ f(n-2)+…+1 = f(i)+1

Для получения функции в явном виде рассмотрим ее последовательные значения:f(0)=1, f(1)=2, f(2)=4, f(3)=8, что позволяет предположить, что f(n)= , точное доказательство выполняется по индукции.

Мы имеем дело с примером того, что одна и та же функция может иметь различные рекурсивные определения – f(n)= , как и в примере 4, что проверяется элементарной подстановкой.

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

Обозначив через Fn - n-ое число Фибоначчи, имеем: f(n)= .

Рекурсивная реализация алгоритмов

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

If n=0 or n=1 (проверка возможности прямого вычисления)

Источник:

th-algoritmov.narod.ru

Рекурсивные функции - значение слова, определение слова, слово означает, VseslovA

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

Рекурсивные функции (от позднелатинского recursio — возвращение), название, закрепившееся за одним из наиболее распространённых вариантов уточнения общего понятия арифметического алгоритма, т.е. такого алгоритма, допустимые исходные данные которого представляют собой системы натуральных чисел, а возможные результаты применения являются натуральными числами. Р. ф. были введены в 30-х гг. 20 в. С. К. Клини, в свою очередь основывавшимся на исследованиях К. Гёделя, Ж. Эрбрана и др. математиков.

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

Арифметические функции, для вычисления значений которых имеются какие-либо алгоритмы, принято называть вычислимыми. Вычислимые функции играют в математике важную роль. Вместе с тем, если понятию алгоритма здесь не будет придан точный смысл, то и само понятие вычислимой функции окажется несколько расплывчатым. Р. ф. уже в силу самого характера своего определения оказываются вычислимыми. В известном смысле верно и обратное: имеются серьёзные основания считать, что математическое по своему характеру понятие рекурсивности является точным эквивалентом несколько расплывчатого понятия вычислимости. Предложение считать понятие вычислимости совпадающим по объёму с понятием рекурсивности известно в теории Р. ф. под названием тезиса Чёрча по имени американского математика А. Чёрча, впервые (в 30-х гг. 20 в.) сформулировавшего и обосновавшего это предложение. Принятие тезиса Чёрча позволяет придать понятию вычислимой арифметической функции точный математический смысл и подвергнуть это понятие изучению при помощи точных методов.

Р. ф. являются частичными функциями, т. е. функциями, не обязательно всюду определёнными. Чтобы подчеркнуть это обстоятельство, часто в качестве синонима используют термин «частично рекурсивные функции». Р. ф., определённые при любых значениях аргументов, называют общерекурсивными функциями.

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

Оператор подстановки сопоставляет функции f от n переменных и функциям g1, . . ., gn от m переменных функцию h от m переменных такую, что для любых натуральных чисел x1, . xm

(здесь и ниже условное равенство @ означает, что оба выражения, связываемые им, осмыслены одновременно и в случае осмысленности имеют одно и то же значение).

Оператор примитивной рекурсии сопоставляет функциям f от n переменных и g от n + 2 переменных функцию h от n + 1 переменных такую, что для любых натуральных чисел x1, .. . xn, y

Оператор минимизации сопоставляет функции f от n переменных функцию h от n переменных такую, что для любых натуральных чисел x1, . xn

Важную роль в теории Р. ф. играют т. н. примитивно рекурсивные функции — Р. ф., получающиеся из исходных функций в результате конечного числа применений одних лишь операторов подстановки и примитивной рекурсии. Они образуют собственную часть класса общерекурсивных функций. В силу известной теоремы Клини о нормальной форме Р. ф. могут быть указаны такие конкретные примитивно рекурсивные функции U от одной переменной и Tn от n + 2 переменных, что для любой Р. ф. j от n переменных и для любых натуральных чисел x1, . . ., xn имеет место равенство j(x1, . xn) @ U(y), где у есть наименьшее из чисел z таких, что Tn(j, x1, . xn,z) = 0 (здесь j представляет собой т. н. геделев номер функции j — число, которое эффективно строится по системе равенств, задающей функцию j). Из этой теоремы, в частности, вытекает, что для Р. ф. от п переменных может быть построена универсальная Р. ф. от n+1 переменных, т. е. такая Р. ф. Фn, что для любой Р. ф. j от n переменных и для любых натуральных чисел x1, . . ., xn имеет место условное равенство

Это — один из центральных результатов общей теории Р. ф.

Теория Р. ф., являясь частью алгоритмов теории, представляет собой разветвленную математическую дисциплину с собственной проблематикой и с приложениями в др. разделах математики. Понятие «Р. ф.» может быть положено в основу конструктивного определения исходных математических понятий. Широкое применение теория Р. ф. нашла в математической логике. В частности, понятие примитивно рекурсивной функции лежит в основе первоначального доказательства знаменитой теоремы Гёделя о неполноте формальной арифметики, а понятие «Р. ф.» в его полном объёме было использовано С. К. Клини для интерпретации интуиционистской арифметики (исследование это составило целую эпоху в области семантики). Аппарат теории Р. ф. используется также в теории вычислительных машин и программирования.

Исследования показали, что все известные уточнения общего понятия алгоритма, в том числе Р. ф., взаимно моделируют друг друга и, следовательно, ведут к одному и тому же понятию вычислимой функции. Это обстоятельство служит серьёзным доводом в пользу тезиса Чёрча.

Лит.: Клини С. К., Введение в математику. пер.(перевод) с англ.(английский), М., 1957; Успенский В. А., Лекции о вычислимых функциях, М., 1960; Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; Роджерс Х., Теория рекурсивных функций и эффективная вычислимость, пер.(перевод) с англ.(английский), М., 1972.

Источник:

vseslova.com.ua

Лекция 3 Рекурсивные функции (РФ) Информационные структуры алгоритмов (ИСА) Рекурсивные функции

Лекция 3 Рекурсивные функции (РФ) Информационные структуры алгоритмов (ИСА) Рекурсивные функции

Рекурсивные функции. (РФ) Информационные

структуры алгоритмов (ИСА).

Рекурсивные функции это ещё одно уточнение понятия алгоритма. Определение рекурсивных функций (РФ) были введены Клини (1937) при решении проблемы формального представления функций, вычислимых алгоритмом. РФ Клини определяется на множестве натуральных чисел. При формальном определении РФ впервые были найдены способы построения (конструирования) всех возможных функций, вычислимых алгоритмами. Слова «всех возможных функций» должны пониматься так: если кто-то придумал некоторую (очень сложную) функцию, вычислимую «механическим способом»некоторым процессором(например, человеком), то такая функция может быть записана в виде формальной схемы по правилам РФ. Понятно, что все конструкторские механизмы (принципы и схемы) РФ так или иначе должны быть реализованы в языках программирования. Существует гипотезаЧёрча, что класс РФ совпадает с классом всех функций, допускающих алгоритмическое вычисление. Все механизмы конструирования функций, открытые Клини, универсальны и могут быть перенесены на функции любой природы.

Принцип конечного набора базовых функций. (БН)

Базовым набором может быть «объявлен» любой список функций, определённых на некотором множестве. Для начала познакомимся, как определял Клини конструкторский механизм для функций, определённых на натуральном множестве.

БН рекурсивных функций Клини = ,

а) (прибавление «1» объявляется операцией, которая известна процессору) – изначально вычислимая рекурсивная функция;

б) «0» – функция «константа нуль» – есть рекурсивная функция;

в) – функция проектирования есть рекурсивная функция;

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

Основной принцип конструирования сложных

функций – подстановка (суперпозиции).

а) Пусть уже построен (или задан) конечный набор функций

б) Пусть задана функция от «n» переменных.

в) определена схема подстановок R, как конечный список уравнений вида:

, где Zkj – некоторые переменные; . Такие уравнения заданы для всех переменных из или их части. Если для некоторых не заданы уравнения, то они считаются «терминальными», т.е. такими, что вместо терминальных переменных могут быть подставлены значения элементов множества, на которых они определены. Переменные в свою очередь могут определяться функциями, такие переменные носят название промежуточных переменных.

г) В случае задания схемы подстановок, говорят, что получается из F подстановкой согласно уравнений подстановокR.

Пример 1. ; определена схема подстановок . При последовательном вычислении по схеме подстановок .

Информационная структура алгоритма (ИСА) представляет собой ориентированный граф , где Х – множество вершин, интерпретированных именами переменных , и именами функций (операциями), которые вычисляют эту переменную ;

V – направленные дуги , каждая дуга интерпретируется, как элементарная подстановка (для вычисления «y» используется подстановка «х»).

Для примера 1 ИСА представляет собой цепочку , где y – выходная переменная, а входная переменная z2 – (терминальная переменная) принимает конкретное значение «5».

Пример 2. Для реализации функции задан набор уже построенных функций и схема подстановок Для определённости можно интерпретировать f1 как обычное арифметическое сложение, а f2 как умножение, х1 и х2 ? N. На рис.1 показана ИС алгоритма, реализующая схему подстановок R. Для вычисления может быть использована формула (ИСА в виде формулы) , либо древесный граф ИСА, соответствующий структуре формулы (см.рис.1б).

Представление ИСА в виде графа имеет ряд преимуществ.

а) Если в каждую вершину ИСА поставить специализированный процессор и соединить процессоры в соответствии с дугами проводами, передающими информацию, то алгоритм, заданный этой информационной структурой, вычисляет сложную функцию за один такт. Так работают схемные реализации алгоритма.

б) Если имеется в наличии только единственный, но универсальный процессор (умеет вычислять f1 и f2), то необходимо написать для него программу (последовательность вычисления вершин – переменных). Очевидно, что таких программ может быть несколько, но они эквивалентны между собой, т.е. дают одно и то же значение «y» при одних и тех же значениях х1, х2 (см. рис. 1в).

в)

Рис. 1. а) ИСА вычисления с подстановками

б) древесный граф ИСА, соответствующий

в) последовательности вычислений переменных

Рис. 2. ИСА вычисления функции Фибоначчи.

Примитивно-рекурсивные функции. Примитивно-рекурсивные схемы подстановок.

Существуют функции с ИСА, фрагменты которых могут повторяться бесконечно. Для описания таких схем подстановок вводятся специальные рекурсивные конструкции. Функции с такой ИСА называются примитивно-рекурсивными (ПРФ).

Примитивно-рекурсивная функция задаётся бесконечной схемой подстановок вида:

где f – функция, которую нужно сконструировать, g, h – ПРФ, которые уже были «сделаны» или являются базовыми, y – параметр рекурсии.

Пример 3. Арифметическое сложение натуральных чисел.

определяется как ПРФ схемой вида.

или

где х – терминальная переменная (в х подставляется значение из N), +1 – функция следования S, y – параметр рекурсии.

Пример 4. Функция Фибоначчи.

Схема ПРФ задаётся в виде рекуррентных соотношений (формул).

или

ИСА, вычисляющего Ф(n), представлена на рис.2. На этом рисунке выделен повторяющийся фрагмент структуры подстановок ?i и показана взаимосвязь пары фрагментов ?i и ?i+1.

Таким образом ПРФ может быть задана в виде схемы, которая называется рекуррентным выражением (рекуррентной формулой) или бесконечно повторяющейся ИСА.

Напомним, n-арное отношение есть подмножество декартового произведения множеств .

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

,

где конкретные значения из Х.

Примитивно – рекурсивным предикатом называется предикат, который определяется примитивно-рекурсивной функцией, распознающей его истинность.

Базовый набор предикатов. (БП) Базовыми могут быть объявлены любые отношения. Считается, что для таких отношений существует рекурсивная функция-предикат, заданная аксиоматически. Например для считается, что это равенство распознаётся автоматически и является базовым отношением, также базовое отношение. Считается, что мы можем вычислять (аксиоматически задан предикат) отношение и т.д. Тогда конструирование сложных предикатов определяется логическими операциями V, &, ? или бесконечной конъюнкцией «&» – квантором всеобщности ?x (для всех х), или бесконечной дизъюнкцией «?» квантором существования (существует х).

В теории РФ принят базовый набор отношений: . Все остальные предикаты получаются путём построения характеристической РФ или применением логических связок (операций).

Пример 5. Определение ПР – предиката для отношения , где и базовый предикат для отношения равенства задан аксиоматически.

Характеристическая ПРФ задаётся схемой

Рекурсивные функции с бесконечно изменяющейся

ИСА таких функций не содержат повторяющихся фрагментов, но порождается по определённому закону во время вычислений.

Понятно, что эти функции не описываются примитивно – рекурсивной схемой и поэтому не являются ПРФ. Первым примером такой РФ, которая задавалась рекуррентным выражением, но не была ПРФ построена Акерманом (1939 г.)

Функция Акермана (ФА).

На рис. 3 представлена ИС алгоритма, вычисляющего функцию Акермана, на двумерной плоскости для любой её точки. Важно, что ФА определена на любой паре аргументов . Во всех вершинах ИСА стоит единственная вычисляющая операция «отождествление», т.е. для любой дуги значение переменной «y» вычисляется отождествлением . ИСА функции Акермана на самом деле не содержат повторяющихся фрагментов и изменяется в зависимости от расположения на плоскости точки . ИСА на рис. 3 по существу является программой (для каждой определено значение ФА), реализующей подстановку значений точек в соответствующие точки . Каждая «трасса» подстановок уникальна и прокладывается своим алгоритмом.

ФА обладает рядом уникальных свойств.

а) ФА – чемпион среди быстрорастущих функций. Значение функции при и выходит за разрядную сетку представлений чисел в существующих трансляторах многих языков программирования.

б) ФА – чемпион по числу вызовов при использовании рекурсивных выражений трансляторами. Глубина рекурсии в зависимости от нарастает столь быстро, что вычисление останавливается при переполнении стека рекурсивных вычислений.

Рис. 3. Информационная структура алгоритма, вычисляющая функцию Аккермана.

3

A

,

A

3

A A A

,

2

,

5

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

1.

2.

3.

Все правила, суть замены слов, кроме правила «1», которое имеет вычисляющую функцию «+» (сложение).

Оператор минимизации. Итерационный процесс для

Существует класс функций, для которых не может быть определена схема подстановок и соответственно ИСА. Функция задаётся уравнением, а значение функции вычисляется перебором всех значений переменных, входящих в уравнение.

Функция задаётся своеобразной процедурой вычисления. Для определения функции в этом случае требуется, чтобы было задано конструктивно

а) отношение , где и , для которого существует рекурсивный предикат.

,

б) специальная итерационная процедура, которая для каждого значения последовательно, начиная с и далее проверяла истинность . Первое найденное значение такое, что будет значением функции и заметим, что такое значение будет минимальным. Так можно вычислять значении функции при любом значении аргумента. Этот способ в теории рекурсивных функций называется ? – оператором и обозначается , где y есть min значение , при котором при конкретном (заданном) значении аргумента «х».

Пример 6.

Итерационная процедура, вычисляющая значение y по х.

а)

б)

в)

г)

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

Частично рекурсивные функции (ЧРФ).

ЧРФ такая функция, которая определена не на всех возможных наборах аргументов. Оказывается, большинство практических задач требуют вычисления именно таких функций. Сложность вычисления ЧРФ связана с алгоритмом поиска области определения функции в декартовом пространстве её аргументов и результатов. Программная реализация ЧРФ обладает в этой связи определённой спецификой. А.П. Ершов ввёл специальный термин «Частичное программирование» для обозначения методов и алгоритмов вычисления ЧРФ.

Пример 7. ЧРФ «Червяк» с бесконечной и изменяемой ИСА. На рис. 5 ИСА ЧРФ «Червяк» , представлена номограммой с выделенными точками на двумерной плоскости . Каждая вершина (выделенная точка) вычисляется функцией следования , где – соседние вершины в графе ИСА.

В настоящее время рекуррентное выражение для ЧРФ «Червяк» неизвестно. В этом случае приходится переходить к более сложным структурам данных нежели двумерный массив. На рис.6 показана стековая структура данных, которая состоит из двух стеков: стек А отслеживает вертикальное движение «Червяка», стек В отслеживает горизонтальное движение «Червяка». Логику работы алгоритма (ЛСА) определяет машина состояний на рис.7.

Рис.5. Номограмма ЧРФ «Червяк».

Рис. 6. Частичная рекурсивная функция «Червяк».

Стековая структура данных для порождения ЧРФ, на каждый

переход из стека в стек вычисляется значение функции.

Рис. 7. Частичная рекурсивная функция с изменяющейся ИСА

«Червяк». Машина состояний для управления вычислением

Процедура вычисления ЧРФ «Червяк» определяется ЛСА вида:

где ПА и ПВ процедуры (системы функций), управляющие перетеканием символов из стека в стек и вычисляющие значения . Состояния стеков показаны на номограмме «Червяка». Для «Червяка» нужно строить специальную процедуру поиска области существования функции (типа алгоритма Тезея). Если точка не принадлежит области значения функции (см. рис. 5, r(2, 5)), алгоритм останавливается (стек до конца не освобождается).

Реальные ИСА, с которыми приходится иметь дело физикам и биологам при моделировании сложных динамических процессов, практически всегда являются ЧРФ с бесконечными изменяющимися структурами. Обычно алгоритмы эффективно реализуются на хорошо подобранных структурах данных. Но подбор таких структур является весьма сложным делом.

ЧРФ со случайно изменяющейся ИСА.

Такие ЧРФ часто встречаются при моделировании случайных процессов. Далее приводится пример очень простой ЧРФ со случайной информационной структурой.

На рис.8 показан процесс бросания монеты (О – орёл, Р – решка), ИСА функции в вершинах, куда идут дуги, помеченные Р, накапливается премия ?. Функция ? определяется рекурсивной схемой:

. Выбор «Р» или «О» случаен.

На рис.8 показаны различные сценарии, по которым развивается процесс бросания монеты. Для вычисления ? используется древесная структура данных.

Рис. 8. Информационная структура функции накопления

Источник:

textarchive.ru

Рекурсивные функции в городе Ульяновск

В этом интернет каталоге вы можете найти Рекурсивные функции по доступной цене, сравнить цены, а также посмотреть иные предложения в категории Наука и образование. Ознакомиться с характеристиками, ценами и рецензиями товара. Доставка производится в любой город России, например: Ульяновск, Хабаровск, Ростов-на-Дону.