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

1. Алгоритм применяется к исходным данным и выдает результаты. Это означает, что алгоритм имеет входы и выходы. Кроме того, в ходе работы алгоритма появляются промежуточные результаты, которые используются в дальнейшем. Таким образом, каждый алгоритм имеет дело с данными: входными, выходными и промежуточными.

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

Эти объекты должны быть четко определены и отличимы как друг от друга, так и от не объектов. Во многих случаях понятно, что это значит. К алгоритмическим объектам относятся числа, векторы, матрицы, формулы. Изображение, например, рисунок, является менее естественным алгоритмическим объектом. Дело даже не в том, что в рисунке больше несущественных деталей, чем, например, в матрице смежности, а в том, что последняя легко разбивается на элементы всего двух видов (0 и 1) и такой вид данных является универсальным. Наконец, с такими объектами как «хорошая книга» или «осмысленное утверждение», с которыми легко справляется человек, алгоритм работать откажется, пока они не будут описаны как данные с помощью других, более подходящих объектов.

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

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

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

3. Алгоритм состоит из отдельных элементарных шагов, множество которых конечно.

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

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

5. Естественно предъявить алгоритму требование результативности, т.е. остановки после конечного числа шагов с указанием того, что считать результатом.

Следует различать:

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

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

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