Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 9 стр.

UptoLike

Составители: 

Данное определение записывается следующим образом:
f(x
1
, x
2
, ..., x
n
) = µ
z < U(x)
(P(x
1
, x
2
, ..., x
n
, z)).
Ограничение z в ограниченном операторе минимизации дает гарантию окончания
вычислений, поскольку оно оценивает сверху число вычислений предиката P. Возможность
оценить сверху количество вычислений является существенной особенностью примитивно-
рекурсивных функций.
2.3. Примитивно-рекурсивные и частично-рекурсивные функции
Большинство вычислимых функций относится к классу примитивно-рекурсивных
функций.
Функция называется
примитивно-рекурсивной, если она может быть получена из
простейших функций с помощью конечного числа операторов суперпозиции и примитивной
рекурсии.
Если некоторые функции являются примитивно-рекурсивными, то в результате
применения к ним операторов суперпозиции или примитивной рекурсии можно получить
новые примитивно-рекурсивные функции.
Существует три возможности доказательства того, что функция является примитивно-
рекурсивной:
а) показать, что заданная функция является простейшей;
б) показать, что заданная функция построена с помощью оператора суперпозиции;
в) показать, что заданная функция построена с помощью оператора примитивной
рекурсии.
Тем не менее примитивно-рекурсивные функции не охватывают все вычислимые
функции, которые могут быть определены конструктивно. При построении этих функций
могут использоваться другие операции. Функция называется
частично-рекурсивной, если
она может быть получена из простейших функций с помощью конечного числа операторов
суперпозиции, примитивной рекурсии и минимизации. Указанные операции могут быть
выполнены в любой последовательности и любое конечное число раз. Если такие функции
оказываются всюду определенными, то они называются общерекурсивными функциями.
Частично-рекурсивные функции вычислимы путем определенной процедуры механического
характера. Практически понятием частично-рекурсивных функций пользуются для
доказательства алгоритмической разрешимости или неразрешимости проблем. Приведем
тезис Черча, который связывает понятие алгоритма и строгое математическое понятие
частично-рекурсивной функции. Тезис Черча: всякий алгоритм может быть реализован
частично-рекурсивной функцией. Утверждение о несуществовании частично-рекурсивной
функции эквивалентно несуществованию алгоритма решения соответствующей задачи.
2.4. Типы рекурсивных алгоритмов
Эффективность разработки рекурсивного алгоритма определяется наличием некоторых
условий:
1) если исходные данные имеют рекурсивную структуру, то процедуры анализа таких
структур будут более эффективны, если они сами рекурсивны;
2) если алгоритм обработки некоторого набора данных построить, разбивая данные на
части и обрабатывая в отдельности каждую часть, то из частичных решений можно получить
общее;
3) если по условию задачи необходимо выбрать оптимальный вариант из некоторого
множества решений, то искомое решение может быть найдено через конечное число шагов.
При этом на каждом шаге удаляется часть информации, и далее задача решается на меньшем
объеме данных. Поиск решения завершается после окончания данных либо при нахождении
искомого решения на текущем наборе данных.