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

§ 6. Выводы

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

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

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

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

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

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

Глава 2

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

§ 1. Роль алгоритмов в науке и технике

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

Особое значение имеют алгоритмы, накопленные в математике, потому что математика пронизывает другие науки и ее богатство является богатством всех наук. Уже довольно давно ученые и инженеры заметили, что если удалось получить алгоритм решения какой-нибудь задачи, то можно создать машину, которая решала бы эту задачу, т. е. можно автоматизировать ее решение. Практика упрямо подтверждала этот факт. Наука его объяснила полностью только недавно. Читатель познакомится с этим в § 3 гл. 6.

Алгоритмы являются: 1) формой изложения научных результатов; 2) руководством к действию при решении уже изученных проблем и, как следствие: 3) средством, позволяющим экономить умственный труд; 4) необходимым этапом при автоматизации решения задач; 5) сред-ством (инструментом), используемым при исследовании и решении новых проблем (особенно это касается математических алгоритмов); 6) одним из средств обоснования математики (см. гл. 4); 7) одним из средств описания сложных процессов (см. гл. 9, 10).

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

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

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

§ 2. Как возникают алгоритмы

Одним из источников алгоритмов является практика, которая предоставляет нам две основные возможности: наблюдение и эксперимент (а также любые их комбинации).

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

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

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

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

Третьим источником новых алгоритмов может являться совокупность уже накопленных. Оказывается, с помощью специальных приемов из имеющихся алгоритмов можно получать новые.

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

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

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

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

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

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

Перечислим наиболее часто применяемые приемы.

1) Конструирование алгоритмов. Этот прием заключается в том, что новый алгоритм получают комбинированием уже известных алгоритмов как составных частей.

2) Эквивалентные преобразования алгоритмов. Два алгоритма называют эквивалентными, если: а) всякий вариант исходного данного, допустимый для одного из них, допустим и для другого; б) применимость одного алгоритма к какому-либо исходному данному гарантирует, что и другой алгоритм применим к этому исходному данному; в) результаты, даваемые этими алгоритмами для одного и того же исходного данного, между собой одинаковы. Замечу, что совершенно неправильно эквивалентные алгоритмы называть различными формами одного и того же алгоритма.

Страницы: 1, 2, 3, 4, 5, 6, 7