Глава 2. Фундаментальные алгоритмы

Два самых фундаментальных алгоритма — это алгоритм деления и алгоритм Эвклида. Оба они были известны математикам Древней Греции — они содержатся в «Началах» Эвклида, написанных около 300 г. до н. э. Алгоритм деления предназначен для вычисления неполного частного и остатка при делении двух целых чисел. Алгоритм Эвклида вычисляет наибольший общий делитель двух целых чисел. По мере чтения книги Вы убедитесь в их фундаментальности.

§ 2.1. Алгоритмы

Оксфордский словарь английского языка дает следующее определение понятия «алгоритм»:

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

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

Для начала проанализируем детально какой-нибудь простейший рецепт. Пусть мы печем пирог. В хорошей кулинарной книге за названием рецепта следует список используемых продуктов. Затем следуют инструкции, объясняющие, что следует сделать с продуктами, чтобы получился пирог. Инструкции могут иметь вид «просеять, смешать, взбить, выпечь». В конце концов получается готовый результат — пирог, пригодный к употреблению.

Похожим образом устроен и любой другой алгоритм. При описании алгоритма мы должны определить его «ввод» и «вывод». Ввод соответствует набору продуктов, используемых в рецепте, вывод — результату, который мы хотим получить; в приведенном выше примере таким результатом был пирог. Собственно алгоритм — это набор действий, которые нужно совершить над вводом, чтобы получить вывод.

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

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

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

Заканчивающийся алгоритм приводит к теореме: «при таком-то и таком-то вводе получается такой-то и такой-то вывод». Теоремы часто формулируют в виде «при данном предположении справедливо следующее заключение». Для теоремы, связанной с алгоритмом, ввод алгоритма соответствует предположению теоремы, а вывод — заключению.

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

• всегда ли при исполнении этих инструкций мы получаем какой-нибудь результат за конечное время?

• совпадает ли результат с ожидаемым?

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

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

Происхождение слова алгоритм (или алгорифм) столь необычно, что ему стоит уделить внимание. Раньше его писали в виде алгорисм, и происходит оно из латинизированного арабского имени Аль-Хорезми, то есть «рожденный в Хорезме». Так звали арабского математика девятого века Абу Джафара Мохаммеда ибн Мусу (Abu Jafar Mohamed Ben Musa). Именно из его «Краткой книги об исчислении ал-джабра и ал-мукабалы» арабские числа распространились по всей Европе. Алгорисм означает попросту «число», что по-гречески называется «арифмос». Затем, как любезно сообщает нам оксфордский словарь, эти два слова переплелись, и появилось слово алгорифм.

Не вполне понятно, каким образом словом алгоритм начал называться «рецепт проведения вычислений», однако, похоже, это значение родилось совсем недавно. В английском оно впервые появилось около 1812 года. Однако уже в семнадцатом веке значение этого слова заметно расширилось. Мы видели, что исходное слово «алгоритм» означало число, однако затем так стали называться и вычисления.

Похоже, что первым за пределы арифметики вывел это слово математик и философ Г. В. Лейбниц (G. W. Leibniz). В своем первом докладе о дифференциальном исчислении, опубликованном в 1684 г., Лейбниц называет правила нового исчисления алгоритмами. Столетие спустя оно обрело свое современное значение. Гаусс многократно использует слово алгоритм в своих «Арифметических исследованиях», написанных по латыни, обозначая им набор формул, составляющих метод нахождения решений какой-либо арифметической задачи.

Ибн Мусе принадлежит еще по крайней мере один вклад в терминологию современной математики: слово алгебра

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