Выбрать главу

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

Каждый встречается с алгоритмами со школьной скамьи. Правила, по которым выполняются арифметические действия с многоразрядными числами являются простейшими примерами алгоритмов. Сам термин "алгоритм" происходит от имени средневекового узбекского математика Мухаммеда бен Муса аль Хорезми, который еще в IX веке сформулировал такие правила. В своем развитии математика накопила огромное количество различных алгоритмов. Получая соответствующую интерпретацию в конкретных приложениях, они составляют значительную и наиболее существенную часть математического аппарата, используемого в технике.

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

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

2. Численные алгоритмы. Алгоритмы, которые сводят решение поставленной задачи к арифметическим действиям над числами, называются численными алгоритмами. Традиционным примером является известный алгоритм Евклида для нахождения наибольшего общего делителя двух заданных целых положительных чисел a и b.

Алгоритм Евклида состоит из следующей системы последовательных указаний:

1) обозревай a и b и переходи к следующему;

2) сравни обозреваемые числа (a = b, или a b, или ) и переходи к следующему;

3) если обозреваемые числа равны, то каждое из них дает искомый результат, если нет — переходи к следующему;

4) если первое обозреваемое число меньше второго, переставь

- 621 -

их местами и переходи к следующему;

5) вычитай второе число из первого и обозревай два числа — вычитаемое и остаток; переходи к указанию 2.

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

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

!!!!

Рис. 257. Поиск пути в лабиринте от точки a к точке f.

3. Логические алгоритмы. Существует другой тип алгоритмов, которые содержат предписания, относящиеся не к цифрам, а к объектам любой природы. Типичным примером логических алгоритмов может служить алгоритм поиска пути в конечном лабиринте.

Лабиринт удобно изображать в виде графа, вершины которого соответствуют площадкам, а дуги — коридорам (рис. 257). Пусть требуется выяснить, достижима ли площадка f из площадки a, и если да, то найти путь из a в f, а если нет — вернуться в a. Конечно, предполагается, что заранее ничего не известно об устройстве данного лабиринта.

Лицо, ищущее путь в лабиринте, располагает нитью, конец которой закреплен на площадке a, и, двигаясь по лабиринту, может разматывать клубок (Р) или наоборот наматывать на него нить (Н). Можно делать отметки на проходимых коридорах и различать затем коридоры, еще ни разу не пройденные (зеленые — З), пройденные один раз (желтые — Ж) и пройденные дважды (красные — К). Метод поиска может быть задан следующей схемой: