В § 2 было сказано, что в некоторых случаях нельзя считать, будто каждый алгоритм задает для каждого допустимого исходного данного вполне определенный процесс. Сейчас уже можно пролить некоторый свет на это обстоятельство. Если алгоритм допускает сразу нескольких исполнителей, то взаимное расположение во времени отдельных шагов процесса может зависеть от числа исполнителей и их индивидуальных особенностей.
При повторном выполнении алгоритма другим коллективом исполнителей (или тем же коллективом, но в других условиях) даже для одних и тех же исходных данных процессы могут быть различными. Свойство определенности будет проявляться в том, что алгоритм в целом и предписываемые им операции на каждом шаге будут однозначными.
Свойство определенности тесно связано со свойством понятности. Мы говорили выше (в § 4), что понятность заключается в том, что исполнителю известен алгоритм выполнения адресованных ему алгоритмов. Если такой алгоритм выполнения обладает определенностью, то (как следствие) и выполненные в соответствии с ним алгоритмы окажутся определенными.
Определенность алгоритма, его механический характер снова наводят нас на мысль о том, что исполнителями алгоритмов могут быть не только люди, но и животные, а также особые машины-автоматы. Этим подтверждается аналогичный вывод, сделанный нами в § 4; в гл. 9 это будет доказано.
§ 6. Выводы
Теперь мы уже можем точнее сказать, что такое алгоритм. Алгоритм — это правило, сформулированное на некотором языке и определяющее процесс переработки допустимых исходных данных в искомые результаты. Допустимыми исходными данными для этого правила являются предложения языка исходных данных. Правило характеризуется понятностью для исполнителя, массовостью (т. е. допустимостью для него всех предложений языка исходных данных) и определенностью. В тех случаях, когда оно применимо к допустимому исходному данному, оно потенциально осуществимо.
В приведенных выше примерах алгоритмы порождают четко видимые алгоритмические процессы, каждый шаг которых очень прост. Если алгоритм к какому-либо допустимому исходному данному неприменим, то алгоритмический процесс может для этого исходного данного либо продолжаться неограниченно (быть бесконечным), либо безрезультатно обрываться.
Теперь в «алгоритмических джунглях» уже можно в какой-то мере ориентироваться. Мы понимаем, что такое алгоритм и зачем он нужен. И все же, как читатель увидит в дальнейшем, это понимание еще очень неточно и не всегда достаточно. К понятию алгоритмического процесса нам придется еще в дальнейшем вернуться, а о некоторых его особенностях мы будем говорить уже в следующей главе. И прежде всего о такой особенности, как простота действий, выполняемых на каждом шаге.
Понятие алгоритма уже обрисовано довольно ясно, и читатель, встретившись с алгоритмом, сразу поймет, с чем имеет дело. И все же пока что сформировано лишь интуитивное представление об алгоритме. Если, опираясь на это представление, мы признаем какое-нибудь правило алгоритмом, то с точки зрения науки это будет «алгоритм в интуитивном смысле». Интуитивному понятию наука ставит в соответствие формальное определение, значительно более точное, но, вообще говоря, более узкое.
На первом этапе своего развития теория алгоритмов не стремилась дать достаточно широкого определения алгоритма, но соотношение между формальным и интуитивным понятиями алгоритма всегда было в центре внимания ученых.
В чем же неточность интуитивного понятия алгоритма? В неточности тех терминов, в которых мы его выразили. До сих пор идут споры о том, что такое язык. Неясен смысл таких слов, как «понятность» и «точность». Научный смысл неясен. А интуитивное значение этих слов ясно.
Глава 2
СОЗДАНИЕ АЛГОРИТМОВ
§ 1. Роль алгоритмов в науке и технике
Как и в повседневной жизни, роль алгоритмов в науке и технике очень велика. Мы знаем, что в каждой научной или технической области почетное место занимают всевозможные справочники. Каждый такой справочник — это в значительной его части сборник алгоритмов, накопленных данной научной или технической дисциплиной. Существуют справочники для конструкторов, для инженеров-производственников, для техников, для мастеров и квалифицированных рабочих; справочники для врачей, фельдшеров и медицинских сестер; справочники для архитекторов и строителей; для бухгалтеров и счетоводов и т. д. Алгоритмы — это богатство науки и техники.
Особое значение имеют алгоритмы, накопленные в математике, потому что математика пронизывает другие науки и ее богатство является богатством всех наук. Уже довольно давно ученые и инженеры заметили, что если удалось получить алгоритм решения какой-нибудь задачи, то можно создать машину, которая решала бы эту задачу, т. е. можно автоматизировать ее решение. Практика упрямо подтверждала этот факт. Наука его объяснила полностью только недавно. Читатель познакомится с этим в § 3 гл. 6.
Алгоритмы являются: 1) формой изложения научных результатов; 2) руководством к действию при решении уже изученных проблем и, как следствие: 3) средством, позволяющим экономить умственный труд; 4) необходимым этапом при автоматизации решения задач; 5) сред-ством (инструментом), используемым при исследовании и решении новых проблем (особенно это касается математических алгоритмов); 6) одним из средств обоснования математики (см. гл. 4); 7) одним из средств описания сложных процессов (см. гл. 9, 10).
Нужно сразу подчеркнуть, что алгоритмы составляют важную часть каждой науки, но не исчерпывают ее содержания. Не менее важны, конечно, понятия и определения, входящие в данную науку, установленные ею факты (в математике — это доказанные теоремы), выработанный наукой подход к изучаемым объектам и явлениям.
Большая ценность алгоритмов обусловливает интерес к ним. Естественно, что специалисты каждой отрасли науки и техники все время ищут алгоритмы решения различных задач. Каждый новый алгоритм немедленно включается в «золотой фонд» науки. При этом интересны как новые алгоритмы, так и алгоритмы для решения вновь поставленных проблем.
Несмотря на то, что алгоритмы очень важны для практики, все же утверждение, будто они изучаются и разрабатываются только в связи с требованиями практики, было бы искажением истины. Нередко создают или ищут алгоритмы для решения задач, которые сами по себе (по крайней мере в настоящее время) не имеют практического значения. Иногда причиной для изучения той или иной проблемы служит любопытство, иногда — эстетическое чувство (например, теория кажется недостаточно «изящной» без алгоритма решения какой-либо вычурной задачи, возникающей при ее разработке). Иногда большие силы ученых привлекает к себе некоторая проблема потому, что в ее решении ученые видят для себя «дело чести». Многие охотники за алгоритмами не задумываются над тем, нужны ли, и если нет, будут ли когда-либо нужны добываемые ими экземпляры. Жизнь показывает, что многие научные результаты, возникающие даже без учета нужд практики, рано или поздно находят важные практические применения. Охота за алгоритмами — это увлекательное и важное дело, которому отдают большую часть своего времени многие ученые.
§ 2. Как возникают алгоритмы
Одним из источников алгоритмов является практика, которая предоставляет нам две основные возможности: наблюдение и эксперимент (а также любые их комбинации).
Объектом наблюдения может быть какое-либо живое существо (в частности, человек), умеющее решать какую-либо из возникающих перед ним задач. Описывая его действия, анализируя их зависимость от изменяющихся условий, можно получить алгоритм для решения упомянутой задачи. Получаемые этим путем алгоритмы обычно называют имитирующими. В более сложном случае объектом наблюдения может быть коллектив совместно действующих живых существ.
В еще более сложных случаях наблюдают какой-либо процесс, протекающий в неживой природе, организме или в обществе, изучают влияние на него различных факторов; в конце концов может быть получен алгоритм управления этим процессом (который будет эффективным, если существует реальная возможность изменять определяющие процесс факторы). Алгоритмы, полученные таким образом (в том числе и имитирующие), принято называть эмпирическими. К их числу относятся приведенные в гл. 1 в виде примеров алгоритмы приготовления пищи, докорма щенят, приготовления лекарств.
Алгоритмы, приводящие к решению интересных для нас задач, иногда можно получить экспериментально, подбирая действия, приводящие к желаемому результату. Их мы не будем выделять в отдельную группу и условно отнесем к эмпирическим.
В качестве второго источника следует указать научную теорию, из основных положений и установленных фактов которой алгоритмы в некоторых случаях могут быть выведены. С такими алгоритмами мы еще встретимся в данной главе. Из числа приведенных в первой главе к этой группе относится алгоритм сложения положительных десятичных дробей.
Третьим источником новых алгоритмов может являться совокупность уже накопленных. Оказывается, с помощью специальных приемов из имеющихся алгоритмов можно получать новые.
Наконец, четвертым источником алгоритмов может быть изобретательность их разработчика. Алгоритмы кодирования и декодирования по заданному ключу происходят из этого источника.
Как бы ни был получен алгоритм, он должен быть обоснован; это означает, что если алгоритм создан для решения определенной задачи, то необходима уверенность в том, что для всех исходных данных, для которых эта задача может быть решена, алгоритм позволяет получить решение и ни для каких исходных данных не дает неправильного результата. Это называется корректностью алгоритма.