2. Элементы теории алгоритмов и рекурсивных функций

   1. Понятие алгоритма

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

Теория алгоритмов получила бурное развитие в 40-х годах прошлого столетия в связи с созданием быстродействующих электронных вычислительных и управляющих машин. Появление ЭВМ способствовало развитию теории алгоритмов, вызвало к жизни разделы этой теории (алгоритмические системы и алгоритмические языки), имеющие ярко выраженную прикладную направленность. Наконец, теория алгоритмов оказалась тесно связанной и с рядом областей лингвистики, экономики, физиологии мозга и психологии, философии, естествознания. Примером одной из задач этой области может служить точное описание алгоритмов, реализуемых человеком в процессе умственной деятельности.

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

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

• Дискретность.Преобразование начальных данных происходит пошагово. На каждом шаге из данных по правилам получается новая совокупность данных.

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

• Направленность.Для алгоритма есть критерий, позволяющий определить, что является результатом работы алгоритма.

• Элементарность шагов алгоритма.Описание действий на каждом шаге алгоритма должно быть достаточно простым.

• Массовость.Применимость алгоритма не к одной задаче, а к целому классу задач.

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

Каждый алгоритм предполагает наличие данных (входные, промежуточные, итоговые данные), с которыми производятся определенные действия. Будем считать, что все данные представлены натуральными числами. Каждое входное натуральное число должно быть конечным, тем не менее не предполагается верхняя граница размера этого числа. Так же нет верхней границы количества шагов для обработки конкретных данных, однако количество шагов должно быть конечным.