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

Сообщение №3235 от vyalyi@mccme.ru 08 апреля 2002 г. 12:20
Тема: Какая математика нужна для алгоритмов?

Какая математика нужна для алгоритмов? vyalyi@mccme.ru
«Понедельник начинается в субботу»

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

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

Статья не претендует на то, чтобы дать окончательный вариант ответа на поставленные вопросы, - будут приведены лишь некоторые характерные (с точки зрения автора) примеры.

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

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

Это, во многом условное, деление обладает двумя удобными свойствами:

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

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

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

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

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

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

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

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


Симплекс-метод

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

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

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


Умножение чисел и матриц

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

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

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


Алгоритмы на графах

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

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

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

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

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


Теория чисел

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

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


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

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


Заключение

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


--------------------------------------------------------------------------------
1 (обратно к тексту) - Обратим внимание читателя на то, что мы располагаем на хронологической шкале теории, а не факты. Ведь до сих пор появляются новые факты даже в элементарной геометрии, которая существует с древнейших времен. То же самое наблюдается и в других областях математики.
2 (обратно к тексту) - В точных науках это вообще очень популярное слово - «обобщенный», «обобщенные»… Когда физик или математик к какому-нибудь «нормальному» слову (например, «корова») добавляет «обобщенная», - знайте, это может быть все, что угодно, включая молокозавод. - Ю.Р.
3 (обратно к тексту) - Здесь опущены некоторые технические детали, не существенные для понимания сути.
4 (обратно к тексту) - Поскольку она лежит в основе алгоритмов дешифровки современных криптосистем.
5 (обратно к тексту) - Правильнее, конечно, говорить о кодах, допускающих исправление ошибок.
--------------------------------------------------------------------------------


Михаил Вялый
vyalyi@mccme.ru
Научный сотрудник Вычислительного центра РАН им. А. А. Дородницына, кандидат физико-математических наук. Научные интересы: комбинаторный анализ, дискретная оптимизация, вычислительная геометрия и квантовые вычисления. Хобби: научная фантастика.

«Компьютерра» Дата публикации: 18.03.2002
Михаил Вялый, vyalyi@mccme.ru


Отклики на это сообщение:

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


Прежде всего, надо тщательно разобраться с тем, что такое алгоритм. Определения нет и, я надеюсь, не будет никогда (речь, конечно, о сторогом определении). Посему понятие алгоритма может допускать как узкое толкование, так и весьма широкое. Даже в не очень широкое толкование подпадает понятие теории. Теория - это алгоритм (нестрогий, но алгоритм). Если бы это было не так, то не существовало бы задачников по матану, дифурам, линейной алгебре и т.д.
В свете сказанного, заглавный вопрос сам же на себя и отвечает: для алгоритмов нужна "теоретическая" математика.
Правильно было замечено: не знает народ математики. Мало у нас универсалов. Правда, то, что они алгоритмы не придумывают, это иллюзия. Профессионал только этим и занят на самом деле. Другое дело, что он редко занимается шлифовкой. Поговорите с Арнольдом, или с Новиковым на математические темы. Попробуйте их заставить что-нибудь шлифовать - они вам морду набьют или, в лучшем случае, сравняют с землей (морально). Придумывать удобные алгоритмы - это инженерия. Но инженеры редко знают даже сотую долю современной математики. Людей же, которых интересует обе упомянутых ипостаси проблемы, еще меньше, чем хороших математиков. Но у нас в России и они даром никому не нужны. Точнее, видимо, только даром их и хотят поиметь.
Резюме: были бы бабки, а математика всякая сгодится! (Даже для альхоривмоф).


> Умножение чисел и матриц

> Похожая ситуация наблюдается с алгоритмом перемножения матриц (ту же сложность имеет и алгоритм решения систем линейных уравнений).
> Известный со старых времен алгоритм Гаусса оказался не самым быстрым.

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


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

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

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


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100