Задачи на построение алгоритмов

Можно было бы продолжить изложение и обоснование различных алгоритмов, накопленных в математике. Вза­мен этого мы лишь перечислим некоторые из них, для того чтобы создать у читателя правильное впечатление об их разнообразии и многочисленности. Алгоритмами являются правила для решения систем алгебраических линейных уравнений (существует большое число таких правил), правила дифференцирования функций и правила интегри­рования, изучаемые в курсе математического анализа, правило Штурма — Лиувилля нахождения приближенного значения корня произвольного уравнения f(х)=0. Алго­ритмами являются также и многие другие правила для решения различных задач с помощью циркуля и линейки, известные читателю из школьного курса. Если бы мы вздумали приводить здесь все эти алгоритмы и обосно­вывать их корректность, то, безусловно, не довели бы эту работу до конца из-за ее большого объема.

Читатель уже представляет себе, как появляются ал­горитмы. Обычно алгоритм разрабатывают, имея в виду какую-нибудь задачу. Для ее решения и создают алгоритм. При этом перед математиком возникает задача, коренным образом отличающаяся от той, для решения которой дол­жен быть создан алгоритм. Эту задачу можно сформули­ровать так: «Задан такой-то класс исходных данных и такая-то задача (проблема), для которой эти исходные данные допустимы. Требуется найти алгоритм, решающий указанную проблему», т. е. перед математиком возникает задача нахождения алгоритма.

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

В 1742 г. математик X. Гольдбах, петербургский ака­демик, в письме к Л. Эйлеру выдвинул проблему: доказать, что каждое целое число, которое больше или равно шести, может быть представлено в виде суммы трех простых чисел.

Этой проблеме можно придать следующий вид. Найти алгоритм, который позволил бы для любого целого числа, большего, чем 6, найти хотя бы одно разложение на три простых слагаемых. В ответном письме Л. Эйлер заметил, что для четных чисел эта проблема эквивалентна проблеме разложения числа на два простых слагаемых. В 1937 г. И. М. Виноградов доказал, что всякое достаточно большое нечетное число представляется суммой трех простых чи­сел; впоследствии была указана и нижняя граница, пред­полагаемая в доказательстве И. М. Виноградова, так что для нечетных чисел проблема Гольдбаха уже решена, но для четных чисел она не решена и до настоящего времени.

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

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

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

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

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

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

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

Это значит, что за счет расширения набора допусти­мых операций иногда можно часть проблем, для которых нет алгоритма, сделать разрешимыми. Конечно, если ничем не ограничиваться при определении допустимых операций, то многие проблемы станут разрешимыми (но все ли? об этом см. в § 1 гл. 5).

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

Глава 3