§ 12.2. Общие свойства алгоритмов

Из рассмотренных примеров отчетливо выступают общие свойства, которые естественно считать свойствами, присущими любому алгоритму:

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

б) Массовость алгоритма. Алгоритм служит не для решения какой-либо одной конкретной задачи, а для решения целого класса задач. Указания о методе действия применимы к начальным данным, которые могут варьироваться.

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

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

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

целочисленное решение.

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

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

Так, при применении алгоритма поиска к любому как угодно сложному (но конечному!) лабиринту, после конечного числа шагов обязательно наступит остановка либо на площадке F, либо на площадке А. По тому, где наступила остановка, мы делаем вывод о достижимости площадки .

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

Однако ничто не препятствует формально применить указания 1—5 алгоритма Евклида к числам и или же к любым целым (положительным или отрицательным) числам. На любом этапе при выполнении любого указания не может возникнуть никаких недоразумений, но может случиться так, что остановка алгоритмической процедуры никогда не наступит. Например, если (наибольший общий делитель равен 4), то, применяя указания 1—5, последовательно получаем пары

и так до бесконечности. Подобная картина будет наблюдаться и для пары .

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

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

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

Свойства детерминированности, массовости и результативности — свойства эмпирические; это те общие свойства, которые подмечены во всех до сих пор построенных алгоритмах. Выводы о них сделаны на основании богатого опыта.

Однако сами по себе эти свойства не могут являться точной математической формулировкой понятия «алгоритм» в силу их неточности, расплывчатости, и потому они не могут быть положены в основу математической теории алгоритмов.