Рекурсивная функция

ТЕОРИЯ АЛГОРИТМОВ

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

Алгоритм обладает следующими характеристиками:

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

2. Детерминированность. Система величин, получаемых в какой-то не начальный момент, однозначно определяется системой величин, полученных в предшествующие моменты времени.

3. Элементарность шагов алгоритмов. Закон получения последующей системы величин из предшествующих должен быть простым.

4. Массовость алгоритма. Начальная система величин может выбираться из некоторых потенциально бесконечного множества. Иначе говоря, алгоритм должен обеспечивать решение некоторому множеству (классу) задач с различными параметрами (коэффициентами).

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

Основная задача теории алгоритмов – это решение проблемы алгоритмическойразрешимости, а не поиск правила (способа/метода) ее решения. Теория алгоритмов дает ответ на вопрос «Данная задача имеет решение?», и не отвечает на вопрос «Как решается данная задача?»

В рамках такого подхода к определению понятия алгоритма можно определить три основных направления:

1. Первое направление связано с уточнением понятия эффективно вычисляемой функции. В результате был выделен класс так называемых рекурсивных функций.

2. Второе направление связано с машинной математикой. Здесь сущность понятия алгоритма раскрывается путем рассмотрения процессов, осуществляемых в машине. Впервые это было сделано Тьюрингом, который предложил общую и вместе с тем самую простую концепцию вычислительной машины. Ее описание было дано Тьюрингом в 1937 г. А это направление в теории алгоритмов получило название - машина Тьюринга.

3. Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским математиком А. А. Марковым. х Нормальные алгоритмы Маркова. Это направление получило название нормальные алгоритмы Маркова.

Основные понятия: элементарные функции, правила образования новых функций.

Простейшие функции:

1. Функция сохранения нуля (нуль-функция)

(4.1)

2. Функция сдвига

(4.2)

3. Функция-проекция

(4.3)

Правила преобразования функций

1. Правило подстановки (суперпозиции)

Пусть даны функции:

Тогда

(4.4)

где g и h являются или простейшими, или выведенными из простейших.

Правило вывода (4.4) означает, что функция получена из функций правилом суперпозиции

ПРИМЕР

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

, (4.5)

2. Правило примитивной рекурсии

Основывается на простейших или выведенных из простейших функциях g и h:

Пусть

Тогда новая функция может быть выведена по правилу:

(4.6)

Следует отметить, что функция зависит от аргументов, функция зависит от аргументов, функция зависит от аргументов. Иначе говоря, правило примитивной рекурсии позволяет получить n + 1 -местную функцию из n -местной и n + 2 - местной функций.

ПРИМЕР

Пусть некоторая функция задана правилом рекурсии

Нетрудно заметить, что функция , функция

Вычислим значение функции при .

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

3. m - оператор (оператор нахождения наименьшего корня у)

Оператор определяет наименьшее значение у, при котором при фиксированном значении. Принято обозначение

(4.7)

(Читается: «наименьшее такое, что »). Аналогично определяется функция многих переменных:

(4.8)

Для вычисления функции существует следующий алгоритм:

1. Вычисляется . Если это значение функции равно нулю, то . Если , то осуществляется переход к следующему шагу.

2. Вычисляется . Если это значение функции равно нулю, то . Если , то осуществляется переход к следующему шагу. И т. д.

Если окажется, что для всех функция , то функция считается неопределенной.

ПРИМЕР

Дана функция . Необходимо определить при

Таким образом,

Функция называется частично рекурсивной, если она получена из простейших функций за конечное число шагов на основе правил подстановки, примитивной рекурсии или m - оператора.

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

Функция называется общерекурсивно й, если она частично рекурсивная и всюдуопределенная.

Тезис А. Черча. Если функция является общерекурсивной, то она выполнима, т.е. имеет алгоритм решения.

Дата добавления: 2014-01-04