Основные свойства и характеристики алгоритмов

Для алгоритма можно выделить семь характеризующих его параметров:
• совокупность возможных исходных данных;
• совокупность возможных результатов;
• совокупность возможных промежуточных результатов;
• правила начала;
• правило непосредственной переработки;
• правило окончания;
• правило получения результата;

Алгоритм имеет следующие свойства.

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

Определенность – выполнив очередную операцию, исполнитель должен то-чно знать, что ему делать дальше.

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

Понятность – алгоритм строится для конкретного исполнителя человеком и должен быть ему понятен. Это облегчает его проверку и модификацию при необходимости .

Результативность – алгоритм всегда должен приводить к результату.

Пример. Всегда ли алгоритм дает точное решение? На простом примере алгоритмов де-ления в столбик и вычисления квадратного корня можно видеть, что, например, при вычи-слениях 20:3 и , мы получаем только приблизительное решение.

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

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

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

Можно сделать следующие замечания, касающиеся свойств алгоритмов:
• Не для всякой массовой проблемы существует алгоритм;
• Для одной проблемы могут существовать разные алгоритмы разной сложности;
• Алгоритм и исходные данные определяют вычислительный процесс полностью;
• При одних и тех же исходных данных алгоритм всегда дает один и тот же результат;
• Алгоритм одинаково понимается всеми исполнителями.