Часть II

Алгоритмы

Глава 4

Алгоритмы

4.1. понятие алгоритма и вычислимой функции

Алгоритм - это точное предписание, определяющее вычислительный процесс, ведущий к искомому результату (А.А.Марков, 1954, [27]).

Данное определение возникло до появления ЭВМ и науки программирования. Но как только последние стали заметным явлением в сумме технологий XX века, стало возможным следующее определение алгоритма.

«Алгоритм - это раз и навсегда составленная программа, в которой все заранее предусмотрено. Выражаясь популярно, алгоритм - это точное, воспроизводимое, поддающееся исполнению предписание, определяющее - шаг за шагом, - каким путем надлежит решать данную задачу. Алгоритмом является любое формализованное доказательство математической теоремы, равно как и программа цифровой машины, переводящей с одного языка на другой» (С.Лем, 1967, [20, с.137]).

«Алгоритмом принято называть систему вычислений, которая для некоторого класса математических задач из записи А «условий» задачи позволяет при помощи однозначно определенной последовательности операций, совершаемых «механически», без вмешательства творческих способностей человека, получить запись В

«решения» задачи» (А.Н.Ксшмогоров, В.А.Успенский, 1958, [14]). Таким образом, алгоритм - это процедура 21, которая [13]:

1) Применяется к строго определенным исходным данным А. Ее нельзя применять к другому типу данных, она либо будет не способна с ними что-то сделать, либо может выдать бессмысленный результат, т.е. результат, не поддающийся анализу с точки зрения тех ожиданий, которые связывались с алгоритмом при его создании.

2) Расчленена на отдельные простые шаги; каждый шаг состоит в непосредственной обработке возникшего к этому шагу состояния S в состояние S* =iigi{S).

3) Непосредственная переработка S в S" = iigi{S) производится однозначно заданным способом лишь на основании информации о виде заранее ограниченной «активной» части состояния S и затрагивает лишь эту активную часть.

4) Процесс переработки Ао = А в Ai = Qsn{Ao), Ai в Аг = Qsn{Ai), Аг в Аз = Пд1(Аг) и т.д. продолжается до тех пор, пока либо не произойдет безрезультатная остановка (или оператор не определен для возникшего состояния), либо не появится сигнал о получении «решения». При этом не исключается возможность непрекращающегося процесса переработки.

Каждый алгоритм задает функцию, поскольку по набору исходных данных выдает результат применения алгоритма к этим данным. Естественно назвать функцию, значения которой могут находится с помощью некоторого алгоритма, - вычислимой функцией. Таким образом, вычислимая функция - это такая функция, для которой существует вычисляющий ее значения алгоритм [43, С.15].

4.2. рекурсивные функции

Какие функции могут быть вычислимыми? Хотелось бы иметь их описание, не связанное напрямую с понятием алгоритма.

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