Тема 4. Примитивно-рекурсивные и частично-рекурсивные функции

План леции

1. Примитивно-рекурсивные и частично-рекурсивные функции

2. Типы рекурсивных алгоритмов

1. Примитивно-рекурсивные и частично-рекурсивные функции

Большинство вычислимых функций относится к классу примитивно-рекурсивных функций.

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

Если некоторые функции являются примитивно-рекурсивными, то в результате применения к ним операторов суперпозиции или примитивной рекурсии можно получить новые примитивно-рекурсивные функции.

Существует три возможности доказательства того, что функция является примитивно- рекурсивной:

а) показать, что заданная функция является простейшей;

б) показать, что заданная функция построена с помощью оператора суперпозиции;

в) показать, что заданная функция построена с помощью оператора примитивной рекурсии.

Тем не менее примитивно-рекурсивные функции не охватывают все вычислимые функции, которые могут быть определены конструктивно. При построении этих функций могут использоваться другие операции. Функция называется частично-рекурсивной, если она может быть получена из простейших функций с помощью конечного числа операторов суперпозиции, примитивной рекурсии и минимизации. Указанные операции могут быть выполнены в любой последовательности и любое конечное число раз. Если такие функции оказываются всюду определенными, то они называются общерекурсивными функциями. Частично-рекурсивные функции вычислимы путем определенной процедуры механического характера. Практически понятием частично-рекурсивных функций пользуются для доказательства алгоритмической разрешимости или неразрешимости проблем. Приведем тезис Черча, который связывает понятие алгоритма и строгое математическое понятие частично-рекурсивной функции. Тезис Черча: всякий алгоритм может быть реализован частично-рекурсивной функцией. Утверждение о несуществовании частично-рекурсивной функции эквивалентно несуществованию алгоритма решения соответствующей задачи.

Типы рекурсивных алгоритмов

Эффективность разработки рекурсивного алгоритма определяется наличием некоторых условий:

1) если исходные данные имеют рекурсивную структуру, то процедуры анализа таких структур будут более эффективны, если они сами рекурсивны;

2) если алгоритм обработки некоторого набора данных построить, разбивая данные на части и обрабатывая в отдельности каждую часть, то из частичных решений можно получить общее;

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

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

Рекомендуемая литература

1. Алферова З.В. Теория алгоритмов. - М.: Статистика, 1973.

2. Крючкова Е.Н. Теория алгоритмов. - Барнаул; 1995.

Контрольные задания для СРС (тема 2) [1, 2, 7]

1. Примитивно-рекурсивные и частично-рекурсивные функции

2. Типы рекурсивных алгоритмов

Дата добавления: 2015-07-26; просмотров: 173; Нарушение авторских прав

Мы поможем в написании ваших работ!