Основные требования к алгоритмам.

1. Очевидно, что каждый алгоритм имеет дело с данными: входными, выходными и промежуточными. В этом плане уточнение понятия алгоритм требует и уточнения понятия данных, т.е. указать, каким требованиям должны удовлетворять объекты, чтобы алгоритмы могли с ними работать. Ясно, что эти объекты должны быть четко определены и отличимы как друг от друга, так и от «необъектов». В теории алгоритмов четкая определенность объектов обусловлена заданием их в формальном языке L=<A,S>, в котором символы конечного алфавита А рассматриваются как элементарные объекты для построения более сложных объектов конечными средствамиS(этот язык часто называется языком операндов в отличие от языка описания самого алгоритма – алгоритмического языка).

2. В дальнейшем будем различать:

• описание алгоритма (т.е. инструкции или программы);

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

• память данных алгоритма;

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

Пояснения:

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

2. Предполагается также, что память данных алгоритма однородна и дискретна, то есть состоит из одинаковых ячеек, каждая из которых может содержать только один символ алфавита данных. Вопрос о том, нужна ли одна память или несколько (в частности для входных, выходных и промежуточных данных алгоритма) может решаться по-разному.

3. Понятие задачи «в общем виде» уточняется при помощи понятия «массовая алгоритмическая проблема». Последняя задается серией отдельных единичных проблем и состоит в требовании найти единый алгоритм их решения (когда такого алгоритма не существует говорят, что рассматриваемая массовая алгоритмическая проблема неразрешима). Так, проблема численного решения уравнений данного типа и проблема автоматического перевода есть массовые алгоритмические проблемы: образующими их единичными проблемами являются в 1-м случае проблемы численного решения отдельных уравнений данного типа, а во 2-м случае - проблемы перевода отдельных фраз.

4. Алгоритмический процесс – есть процесс последовательного преобразование конструктивных объектов, происходящий дискретными шагами; каждый шаг состоит в смене одного конструктивного объекта другим. Так, при применении алгоритма вычисления (f:D²D) столбиком к паре <507, 38> последовательно возникают следующие конструктивные объекты:

_507 _507 _507 _507

38 38 38 38

469

Здесь возможными исходными данными служат пары чисел, возможными результатами – числа (все в десятичной системе счисления), а возможные промежуточные результаты суть трехэтажные записи вида , гдеq-

запись числа в десятичной системе, z- такая же запись или пустое слово, аp- запись числа в десятичной системе с допущением точек над некоторыми цифрами (точка означает заимствование из старшего разряда).