Какая математика нужна для алгоритмов?

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

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

Важное уточнение, которое нужно сделать, относится к классификации математических фактов и знаний. Здесь использована довольно грубая шкала, на которой математические теории привязаны к примерному времени их возникновения. Чтобы избежать ошибок детализации, разделим всю историю математики на пять больших периодов ¹: древнейшая математика (от ее зарождения и до конца XVI в.), древняя (XVII-XVIII вв.), старая (XIX в.), новая (первая половина XX в.) и наконец, современная математика (со второй половины XX в. по наши дни). Это, во многом условное, деление обладает двумя удобными свойствами:

• Во-первых, количество информации в математике, как и в других науках, растет по экспоненте. Так что фактический материал разделяется этими периодами в равных по порядку величины объемах.

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

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

Эти соображения очевидны, но обратим внимание, что они являются, по сути дела, применением тривиальной эвристики: «искать там, где светло». Иногда такая стратегия дает сбои, причем, как правило, в самых интересных случаях, но именно тогда появляются принципиально новые мысли.

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

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

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

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

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

Похожая ситуация наблюдается с алгоритмом перемножения матриц (ту же сложность имеет и алгоритм решения систем линейных уравнений). Известный со старых времен алгоритм Гаусса оказался не самым быстрым. В 1969 году Штрассен придумал новый алгоритм, ускоряющий перемножение матриц. Ни построение, ни обоснование этого алгоритма не используют идей, выходящих за рамки поставленной задачи! Создание ключевого соотношения здесь является не очень трудным упражнением в линейной алгебре (и фактически вошло в современные учебники в качестве учебной задачи). Почему же такой способ перемножения не был придуман еще Гауссом? Существует по крайней мере три ответа на этот вопрос. Предлагаем читателю самому выбрать тот, который больше понравится:

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

• Алгоритм Штрассена неудобен для ручного вычисления.

• Алгоритм Штрассена был придуман лишь в XX веке потому, что математика этого периода гораздо больше внимания уделяла некоммутативным операциям, чем старая математика XIX века (поскольку последнее утверждение спорно, сошлемся на мнение М. Атья, одного из крупнейших современных математиков).

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

Например, такая задача: нужно соединить две вершины графа как можно большим количеством попарно непересекающихся путей. Алгоритм ее решения основан на сведении проблемы к некоторой задаче линейного программирования. Делается это следующим приемом, ставшим уже классическим. Будем искать «обобщенные ² пути» и считать, что ребро может входить в «обобщенный путь» частично. Другими словами, поставим на ребрах графа числа, показывающие, с каким весом ребро входит в «обобщенный путь». Все это очень напоминает описание системы потоков: одна вершина - источник, другая - сток, а в каждую из остальных вершин сколько втекает, столько из них и вытекает ³. Задача нахождения максимального потока типична для линейного программирования. Есть, правда, один нюанс. Что делать, если в ответе вдруг получатся нецелые числа? Ведь по смыслу задачи они должны быть целыми (0, если ребро не входит в систему путей, 1 - если входит). Оказывается, в данном случае всегда можно получить целочисленный ответ. Это отдельная теорема.

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

Далее приведем еще два примера столь же сильного взаимодействия теорий.

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

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

Коды, исправляющие ошибки ⁵

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

Обращают на себя внимание два обстоятельства. Во-первых, примеров нетривиального использования математических идей в построении алгоритмов существует не много. Во-вторых, современная математика используется крайне ограниченно. Этому можно дать разные объяснения. Одно из них состоит в том, что людей, знающих математику, особенно современную, мало. И эти люди редко занимаются изобретением алгоритмов.