Главная | Обратная связь

Пример вычислений для класса рекурсивных функций.

Понятие алгоритма, классические алгоритмы.

Алгоритм – точное предписание о выполнении определенной последовательности действий, ведущей от варьируемых результатов к окончательным результатам.

«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)

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

Для разработки алгоритмов и программ используется алгоритмизация — процесс систематического составления алгоритмов для решения поставленных прикладных задач. Алгоритмизация считается обязательным этапом в процессе разработки программ и решении задач на ЭВМ. Именно для прикладных алгоритмов и программ принципиально важны детерминированность, результативность и массовость, а также правильность результатов решения поставленных задач. Алгоритм может быть записан словами и изображён схематически.

Для каждой задачи может существовать множество алгоритмов, приводящих к цели. Увеличение эффективности алгоритмов составляет одну из задач современной информатики.

 

Пример вычислений для класса рекурсивных функций.

Множество частично рекурсивных функции включает в себя множество общерекурсивных функции, а общерекурсивные функции включают в себя примитивно рекурсивные функции. Частично рекурсивные функции иногда называют просто рекурсивными функциями.

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

К числу базовых примитивно рекурсивных функций относятся функции следующих трёх видов:

S(x) = х+ 1 (функция следования);

О(х) = 0 (нуль-функция);

Функции , где , от n переменных, сопоставляющие любому упорядоченному набору натуральных чисел число x_m из этого набора. (функции-проекторы).

Операторы подстановки и примитивной рекурсии определяются следующим образом:

· Оператор подстановки. Пусть f — функция от m переменных, а — упорядоченный набор функций от n переменных каждая. Тогда результатом подстановки функций g_k в функцию f называется функция h от n переменных, сопоставляющая любому упорядоченному набору натуральных чисел число

.

· Оператор примитивной рекурсии. Пусть f — функция от n переменных, а g — функция от n + 2 переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций f и g называется функция h от n + 1 переменной вида

;

.

Множество примитивно рекурсивных функций — это минимальное множество, содержащее все базовые функции и замкнутое относительно указанных операторов подстановки и примитивной рекурсии.

Пимеры: