§ 1. ЧИСЛЕННЫЕ АЛГОРИТМЫ

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

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

Простейшими алгоритмами являются правила, по которым выполняется то или другое из четырех арифметических действий по десятичной системе счисления (сам термин алгоритм происходит от имени средневекового узбекского математика Аль-Хорезми, который еще в IX веке дал такие правила). Так, например, действие сложения двух многозначных чисел разлагается на цепочку элементарных операций, при осуществлении каждой из которых вычислитель обозревает лишь 2 соответствующие цифры слагаемых (одна из которых может оказаться снабженной пометкой, напоминающей о переносе единицы). Эти операции бывают двух типов: 1) запись соответствующей цифры суммы, 2) пометка о переносе над соседней слева цифрой; при этом правило предписывает надлежащий порядок выполнения этих операций (справа налево). Формальный характер этих элементарных операций заключается в том, что они могут быть выполнены автоматически по раз навсегда заданной таблице сложения цифр, при полном отвлечении от их содержательного смысла.

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

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

Очевидно, различных задач такого типа существует столько, сколько различных пар чисел

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

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

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

Указание 1. Обозревай два числа: Переходи к следующему указанию.

Указание 2. Сравни обозреваемые числа или или переходи к следующему указанию.

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

Указание 4. Если первое обозреваемое число меньше второго обозреваемого числа, переставь их местами и продолжай обозревать их. Переходи к следующему указанию.

Указание 5. Вычитай второе из обозреваемых чисел из первого и обозревай два числа: вычитаемое и остаток. Переходи к указанию 2.

Итак, после того, как все 5 указаний выполнены, надо опять возвратиться ко второму, потом дальше к третьему, четвертому, пятому и опять ко второму, третьему и т. д., пока не получатся равные числа, т. е. пока не окажется выполненным условие, содержащееся в третьем указании; тогда процесс прекращается.

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

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

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

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

дается формулами

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

В частности, так обстоит дело и в случае алгоритма Евклида, где число вычитаний, могущих понадобиться, зависит от выбора той или иной пары чисел

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

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

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

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

Приведем пример такого класса однотипных задач, для решения которых современная математика не располагает алгоритмом.

Рассмотрим всевозможные диофантовы уравнения, т. е. уравнения вида

где является многочленом с целочисленными коэффициентами. Такими будут, например, уравнения

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

второе же уравнение не имеет целочисленного решения, ибо для любого целого х легко устанавливается неравенство

В 1901 году на международном математическом конгрессе в Париже знаменитый немецкий математик Давид Гильберт огласил список 20 трудных" проблем, на важность решения которых он обращал внимание математической общественности. Среди них была и следующая проблема (10-я проблема Гильберта): требуется выработать алгоритм, позволяющий для любого диофантова уравнения выяснить, имеет ли оно целочисленное решение.

Для частного случая диофантова уравнения с одним неизвестным такой алгоритм уже давно известен. Именно, установлено, что если уравнение

с целочисленными коэффициентами имеет целый корень то обязательно делится на В соответствии с этим можно предложить такой алгоритм:

1) найти все делители числа (их конечное число);

2) подставлять поочередно найденные делители в левую часть уравнения и вычислять численное значение ее;

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

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

Уже в рассмотренных до сих пор примерах довольно отчетливо выступают следующие черты численных алгоритмов, присущие и любому другому алгоритму:

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

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