Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

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

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

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

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

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

*) Следует иметь в виду, что этот термин отчетливого смысла не имеет.

13

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

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

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

с одним неизвестным (вообще же рассматриваются уравне­ ния с любым числом неизвестных). Уравнение может иметь целочисленное решение, а может и не иметь такового. Так, первое из приведенных уравнений имеет целочисленное ре­ шение л; = 3, г/ = 4, 2 = 5; второе же уравнение не име­ ет целочисленного решения, ибо для любого целого х легко устанавливается неравенство 6х1 8 > х — 3.

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

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

14

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

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

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

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

§ 2. АЛГОРИТМЫ ИГР

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

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

15

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

2.1. Одиннадцать предметов. В книге Б. А. Кордемского «Математическая смекалка» разбирается ряд игр, успеш­ ное проведение которых зависит не от случайного стече­

Первый играющий берет себе из этого количества по своему усмотрению 1, 2 или 3 спички. Затем второй играющий бе­ рет себе из числа оставшихся спичек также по своему усмо­

ся взять последнюю спичку. Может ли игрок А, начинаю­ щий игру, поставить своего партнера В перед необходимо­ стью взять последнюю спичку?

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

1.П е р в ы й х о д . Л берет 2 спички.

2.О ч е р е д н о й х о д . Если В при своем очередном ходе взял / спичек (/ <[ 3), причем еще остались неотобран­ ные спички, то А берет 4 — / спичек.

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

симо от того, как будет играть В. Проиллюстрируем это на примере следующих двух партий:

А берет одну или три спички, то В может вести игру так, чтобы наверняка ее выиграть.

16

2.2. Побеждает чет. Рассмотрим теперь игру «Побежда­ ет чет» из книги Б. А. Кордемского.

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

это невозможно, то при наличии 5 или 3 еще неотобранных спичек взять 4 или 2 соответственно.

3. О ч е р е д н о й - х о д А, е с л и В и м е е т не ­

17, 11,5). Если это невозможно, то оставить число спичек кратное шести; если и это невозможно, то при наличии не­

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

2.3. Дерево игры. Наша ближайшая цель заключается в описании алгоритма, применимого к любой игре из неко­ торого весьма обширного класса игр, который устанавли­ вает для каждого игрока «наилучшую» из возможных для него стратегий. Чтобы избежать чрезмерной формализа­ ции, вместо точных определений употребляемых понятий будем иногда ограничиваться лишь разъяснением их со­

17