Определенность алгоритма

Обратим внимание еще на одну особенность, присущую каждому алгоритму. Исполнитель алгоритма не только не нуждается в какой-либо фантазии или сообразительности, но, более того, алгоритм не оставляет места для проявления этих качеств, если исполнитель ими обладает. Выполняя алгоритм, действуют механически. Может быть, по мнению читателя это плохо? Может быть, эта черта алгоритма в какой-то мере подавляет творческие способности людей? Ни в коем случае! Люди могут в полной мере проявлять свои творческие способности, разрабатывая алгоритмы. Но после того как они созданы, такое проявление творческих способностей было бы неоправданным расходом психической энергии. Алгоритмы позволяют ее экономить. Таким образом, формулировка алгоритма так точна, что полностью определяет все действия исполнителя.

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

Читателю, настроенному критически, может показаться, что алгоритмы, приведенные в § 1, не очень точны. Например, результат посадки цветов при повторном выполнении алгоритма может не полностью совпадать с результатом первого выполнения (осуществленного, например, в прошлом году). Однако в пределах требуемой в данной области применения точности оба результата следует признать одинаковыми. Абсолютные точность и однозначность должны быть присущи математическим алгоритмам, а «практические» алгоритмы должны быть практически точны.

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

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

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

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

Определенность алгоритма, его механический характер снова наводят нас на мысль о том, что исполнителями алгоритмов могут быть не только люди, но и животные, а также особые машины-автоматы. Этим подтверждается аналогичный вывод, сделанный нами в § 4; в гл. 9 это будет доказано.

Выводы

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

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

Теперь в «алгоритмических джунглях» уже можно в какой-то мере ориентироваться. Мы понимаем, что такое алгоритм и зачем он нужен. И все же, как читатель увидит в дальнейшем, это понимание еще очень неточно и не всегда достаточно. К понятию алгоритмического процесса нам придется еще в дальнейшем вернуться, а о некоторых его особенностях мы будем говорить уже в следующей главе. И прежде всего о такой особенности, как простота действий, выполняемых на каждом шаге.

Понятие алгоритма уже обрисовано довольно ясно, и читатель, встретившись с алгоритмом, сразу поймет, с чем имеет дело. И все же пока что сформировано лишь интуитивное представление об алгоритме. Если, опираясь на это представление, мы признаем какое-нибудь правило алгоритмом, то с точки зрения науки это будет «алгоритм в интуитивном смысле». Интуитивному понятию наука ставит в соответствие формальное определение, значительно более точное, но, вообще говоря, более узкое.

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

В чем же неточность интуитивного понятия алгоритма? В неточности тех терминов, в которых мы его выразили. До сих пор идут споры о том, что такое язык. Неясен смысл таких слов, как «понятность» и «точность». Научный смысл неясен. А интуитивное значение этих слов ясно.

Глава 2

СОЗДАНИЕ АЛГОРИТМОВ