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

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

Рассмотренные примеры показывают, что выполнение алгоритма разбивается на последовательность законченных действий-шагов. Каждое действие должно быть закончено исполнителем прежде, чем он приступит к исполнению следующего действия. Это свойство алгоритма называется дискретностью. Таким образом, дискретность означает, что алгоритм состоит из конечного числа описаний шагов и эти шаги выполняются в дискретном времени, то есть любые два последних шага разделены при исполнении конечным, ненулевым отрезком времени. Можно считать, что шаги выполняются в моменты времени t₀, t₁,…, а между этими моментами ничего не происходит.

Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма, называемое командой.

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

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

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

- Да пойми же, гайками прикрепляется рельса к шпалам!

- Это мы понимаем...

А.Чехов "Злоумышленник"

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

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

Отмеченное свойство называется свойством определенности, или детерминированности.

Замечание. Часто под свойством детерминированности алгоритма понимается одновременное выполнение свойств точности и понятности.

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

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

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

Проиллюстрируем свойства алгоритма на примере алгоритма Евклида.

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

Вопросы для контроля:

1. Интуитивное понятие алгоритма.

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

Раздел 10. Основная формализация (Машина Поста и МНР).

Дата добавления: 2014-01-06