Алгоритм относится к основным понятиям математики, а поэтому не имеет определения. Часто это понятие формулируют так:

"точное предписание о порядке выполнения действий, из заданного фиксированного множества, для решения всех задач, заданного класса" .

Рассмотрим подробнее ключевые слова в этой формулировке:

1. "точное предписание” означает, что предписание однозначно и одинаково понимается всеми исполнителями алгоритма и при одних и тех же исходных данных любой исполнитель всегда получает один и тот же результат;

2. “из заданного фиксированного множества” означает, что множество действий, используемых в предписании, оговорено заранее и не может меняться в ходе исполнения алгоритма.

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

Эта формулировка требует знания таких понятий, как исходные данные, результат, действие, исполнитель, класс задач. Познакомимся с ними на примере алгоритма Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел:

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

Все исполнители должны “понимать”, что надо сравнить значения, представленные символами а и b, а не сами символы, и перейти к действию 3.

Означает, что в качестве текущего значения переменной а надо взять разность между значениями, представленными переменными а и b, вычисленную на предыдущем этапе, и перейти к действию 2.

Последовательность действий, выполняемых исполнителем, образуют процесс. Назовем этот процесс вычислительным процессом. Например, для случая исходных данных n=3, m=2 и алгоритма НОД этот процесс можно описать так:

Нетрудно видеть разницу между алгоритмом и вычислительным процессом, им порождаемым. Так, например, действие, которое встречается в алгоритме один раз, может быть выполнено вычислительным процессом несколько раз, а следовательно встретиться неоднократно в описании вычислительного процесса. Примерами такого действия может быть действие 3, либо действие 5, либо 6. В нашем алгоритме, как правило, экземпляры одного и того же действия будут различаться данными (операндами), над которыми совершается это действие. Однако, эти данные могут быть представлены одними и теми же именами.

По алгоритму не всегда можно предсказать вычислительный процесс. Например, не всегда можно предвидеть точно, как много действий будет в вычислительном процессе.

Примером тому может служить алгоритм вычисления НОД.

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

Обычно по умолчанию предполагают “естественный” порядок выполнения действий в алгоритме. Это означает, что если нет явного изменения порядка выполнения действий, то они выполняются последовательно одно за другим, а выполнение алгоритма начинают с первого по порядку действия. Поэтому, в дальнейшем слова “(следующий шаг)” мы будем опускать.

Рассмотрим подробнее понятие действия. В нашем примере присутствуют как минимум два вида действий:

1. действия над данными (например, сравни, вычти, положи);

2. действия, изменяющие “естественный” порядок вычислений (например, если - то - иначе; перейди к шагу #).

Если присмотреться внимательней, то мы увидим, что действия вида “сравни”, “вычти” и действия вида “положи ” - это разные действия. Разница между ними в том, что действия первого вида указывают, что делать с его операндами, но не указывают где “сохранить” полученный результат. Действия второго вида, наоборот “умалчивают” каким образом получено значение, которое надо “сохранить” в качестве нового значения переменной.

Теперь пристальнее рассмотрим правило окончания алгоритма и выбора результата. В алгоритме могут быть использованы десятки переменных, но результат будет храниться лишь в нескольких. Эти “результирующие” переменные должны быть явно указаны в алгоритме, т.к. в противном случае нет никакой возможности их выявить. Момент, когда в этих переменных сформированы нужные значения, определяет правило окончания алгоритма. Правило окончания всегда формулируется как некоторое условие на множестве текущих значений переменных. Достижение этого условия и означает, что в определенных переменных получен результат. В нашем примере таким условием является равенство текущего значения переменной а текущему значению переменной b.

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

Данные в алгоритме могут быть представлены переменными (в нашем примере именуемые a и b), либо явно, в виде постоянной величины - константы (в нашем примере n и m), которая не меняет своего значения в конце выполнения алгоритма.

Переменная - это имя, с которым связано конкретное множество значений . В каждый конкретный момент времени исполнения алгоритма каждая переменная принимает одно конкретное значение, из связанного с ней множества.

Типом переменной называется множество возможных ее значений .

Состоянием на множестве переменных называется набор значений этих переменных.

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

Вычислительным процессом, порожденным алгоритмом, называется последовательность шагов алгоритма, пройденных при исполнении этого алгоритма.

Состоянием вычислительного процесса, порожденного алгоритмом А, называется состояние на множестве переменных (, p ), где - набор всех переменных, используемых в алгоритме А .

Нетрудно видеть, что вычислительный процесс можно описать в виде последовательности его состояний.

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

Результат - это определенная совокупность значений из терминального состояния вычислительного процесса алгоритма .

Действительно, если действие связано с преобразованием каких-либо данных, то правильность этого утверждения очевидна. Если же действие связано с изменением “естественного” порядка выполнения действий в алгоритме, то состояние вычислительного процесса меняется все равно, т.к. изменяется значение специальной переменной p - индекс действия.

Рассмотрим еще один пример. Пусть нам надо построить алгоритм для решения следующего класса задач:

вычислить значение выражения , в точке x=b, где

Множество исходных данных: , где ai Î R, b Î R.

вектор из n+1 вещественных числа;

Результат b r: , где

Нетрудно видеть, что мы имеем дело с классом задач. Ниже приведен алгоритм для этого класса задач.

6. Положи r равным r+ ;

Организацию вычислений по этому алгоритму можно пояснить вот таким выражением:

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

Организацию вычислений по этому алгоритму описывает выражение

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

Сложностью алгоритма называется количество действий в вычислительном процессе этого алгоритма (именно в вычислительном процессе, а не в самом алгоритме!)

Для того, чтобы сравнивать сложность разных алгоритмов, надо чтобы она подсчитывалась для них в терминах одинаковых действий. Например, умножь, сложи, положи. Выразим сложность действия возведения в степень i как (i - 1) операций умножения. Тогда, сложность первого алгоритма (по схеме Горнера) в виде числа операций сложения и умножения будет равна 2п. Для прямого алгоритма она будет равна:

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

Для всякого ли класса задач существует алгоритм? Гедель дал отрицательный ответ на этот вопрос. Существуют проблемы, для решения которых нет алгоритмов. Примером одной из таких проблем является 10-я проблема Гильберта:

В 1969г. отечественный математик Ю.В. Матеясевич показал, что не существует алгоритма для решения произвольного диофантова уравнения.

Рассмотрим свойство массовости алгоритма, выражающееся в том, что алгоритм предназначен “для решения всех задач заданного класса”, т.е. множества задач. Здесь уместно вспомнить парадокс греческого философа Эвбулида "Что есть куча?" Один камень - это куча? Два - это куча? И т.д. В нашем случае наводящим соображением для решения возникшей проблемы является то, что все эти задачи различаются лишь исходными данными.

Массовость предполагает существование четко определенного класса объектов, которые могут быть исходными данными. Мощность этого класса - свойство класса объектов, а не алгоритма. Массовость означает существование языка данных, т.е. четких правил построения этих объектов, называемых данными, из некоторого, как правило, фиксированного множества базовых объектов, называемого алфавитом. Такие объекты в математике называются конструктивными объектами. Примерами конструктивных объектов могут служить слова в некотором фиксированном алфавите. Таким образом, данные - это слова в алфавите. В рассмотренных примерах исходными данными были числа. В данном случае мы можем рассматривать эти числа, как слова в алфавите <0,1,2,3,4,5,6,7,8,9,>. Итак, исходные данные - всегда конструктивные объекты.