Свойства алгоритмов

В качестве содержательных свойств, характеризующих алгоритм, А. А. Марков отмечает следующие:

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

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

2. Массовость. Алгоритм предлагает всегда решение некоторой массовой проблемы, его исходные данные варьируются. Существует некоторое (заведомо не пустое и не единичное) множество наборов исходных данных, определяемое решаемой проблемой, для которых алгоритм обеспечивает получение искомого результата.

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >