malkovsky Jul 4 at 05:00

Лучшие алгоритмы 20 века по версии SIAM

Medium

19 min

7.7K

History of ITMathematics*Algorithms*Programming*

Review

The Best of the 20th Century: Editors Name Top 10 Algorithms

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

Выбор редакции SIAM
Алгоритмы, отмеченные хабровчанами
Поддержать автора
Пройти опрос

Метод Монте-Карло

Аннотация к оригинальной статье по методу Монте-Карло

Основные статьи по этому методу датированы 1949 и 1953 годами, но были придуманы скорее всего гораздо раньше, во время Манхэттенского проекта. Очень кратко о сути метода: представьте, что у вас есть обычный 6-гранный игральный кубик, вы хотите понять "честный" ли он? Имеется в виду, что внутри точно нет никакой электроники, но возможно был допущен брак и у него смещен центр тяжести, из-за чего он на одну сторону будет падать чаще, чем на другие. Николас Метрополис противопоставлял два подхода к этой задаче:

Сделать какой-то комплексный анализ кубика, например просветить его рентгеном и составить карту плотности
Просто подкинуть этот кубик много раз и посмотреть сколько раз выпадет каждая из сторон

Первый способ часто более дешевый, но сложный. Второй — простой, неточный и затратный, второй вариант как раз и есть метод Монте-Карло, название отсылает к уже известному на тот момент крупнейшему казино, а алгоритм по сути предлагает в качестве решения задачи "сыграть в рулетку". Во всех известных мне простых академических примерах метод Монте-Карло совершенно неэффективен, вот например метод Бюффона для вычисления числа пи: рисуем на доске параллельные линии на расстоянии R и кидаем на них иголку длины . Для вероятности попадания иголки на одну из прямых в этом случае верна формула $p = 2L/(R\pi)$ . мы знаем, можем оценить из эксперимента. Чтобы получить таким способом приближение лучше чем нужно кинуть иголку ~500 раз, ну такое. Но всё меняется когда задачи усложняются. В физике ядра, свойства которых изучали в Манхэттенском проекте, уравнения были гораздо сложнее, и они практически не поддавались точным решениям в виде математической формулы. В этой ситуации метод Монте-Карло оказался просто единственным хоть как-то работающим. Другим фактором успешности метода стало появление первых компьютеров — он идеально подходил для компьютеров, которые хорошо умеют повторять однотипные действия, генерировать псевдослучайные числа тоже тогда уже умели.

Интересно, что при реализации метода в Лос-Аламосе для генерации случайных чисел был использован метод "средних квадратов" фон Неймана, имевший существенный изъян. В методе Неймана возникала неприятная ситуация: в какой-то момент этот алгоритм начинал выдавать одинаковые значения и повторял его до бесконечности. Чуть менее деструктивная ситуация (но и менее отслеживаемая) состояла в раннем "зацикливании" — последовательность пробегала лишь малую часть возможных значений, а потом начинала повторять себя. Позднее эти недочеты были исправлены линейными конгруэнтными генераторами с правильно подобранными параметрами. Подробности в "Искусство программирования" Д. Кнут, том 2, раздел 3.1.

Вернемся к теме, посмотрим на два особо важных примера применения метода Монте-Карло, между которыми больше полувека:

Первый пример — это уже упомянутый манхэттенский проект. Там использовался Markov Chain Monte-Carlo — с помощью марковской цепи моделировался процесс распада ядра в виде последовательности состояний группы ядер. Вопрос, который интересовал физиков — при каких исходных параметрах может быть запущена самоподдерживающаяся цепная реакция.

Второй пример произошел гораздо позже, но имел не менее грандиозный успех: Monte-Carlo Tree Search (MCTS). Этот метод стал одним из ключевых в успехе нейросетей для классических игр и в частности для шахмат и го. Задолго до AlphaGo/AlphaZero были известны методы эвристического перебора позиций на основе дерева игры — это такое дерево, где каждый потомок соответствует ходу игрока. Такое дерево очень быстро разрасталось, поэтому его зачастую урезали вспомогательными методами. Проблема была в том, что до этого не было надежного способа получить информацию о том, хороший ли ход или нет. Для получения надежной информации нужно доиграть игру до конца — тогда мы знаем результат. Метод MCTS предлагал простую и неточную идею: для оценки хода производилась симуляция игры с текущими параметрами алгоритма игры на основе простых правил выбора хода, таким образом получался дешевый способ получить не очень точную информацию об успешности хода. Но дело не только в этом, вместе с успешностью хода также мы получали оценку на успешность текущих параметров алгоритма игры, что позволяло сделать небольшое, но всё же, улучшение качества игры. Совмещая это с уже известными и зарекомендовавшим на тот момент стохастическим градиентным спуском, со временем получилось добиться того, что последний раз человек выигрывал у лучшей компьютерной программы в 2016 году.

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

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

Логистика: задача о кратчайшем пути, задача о максимальном потоке, задача о назначениях — всё это задачи Линейного Программирования. В чистом виде они встречаются редко, но как составные части бОльших систем — постоянно. К слову, известный всем алгоритм Дейкстры был также независимо придуман Данцигом в 1962-м и опубликован в книге Linear Programming and Extensions
Машинное обучение: успех машинного обучения стал возможным благодаря развитию теории оптимизации, в частности стохастический градиентный спуск — один из основных алгоритмов этой теории. Несмотря на то, что линейное программирование и симплекс метод к нему уже малое отношение имеют, задачи с ограничениями встречаются в ML, например до сих пор публикуются исследования обучения RNN с помощью решения таких задач.
Теория управления: львиная доля задач этой теории заключается в нахождении устойчивой траектории динамической системы (это такие, которые задаются дифференциальными уравнениями), условия устойчивости хорошо известны — условия Ляпунова, а нахождение управляющего воздействия, удовлетворяющее этим условиям, обычно сводится к линейным матричным неравенствам (LMI). Это не совсем Линейное Программирование, но достаточно близко к нему и решается, в частности, методом внутренней точки. Где это применяется? Везде, где нужно летать/плавать/ездить и при этом не развалиться сразу после запуска.

А что сейчас?

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

Небольшой бонус, интересные факты о Канторовиче и Данциге

Как-то Данциг опоздал на лекцию, тихо вошел в зал, увидел на доске условие двух задач и подумал, что это домашнее задание. Через три дня он принес решение профессору со словами "извините, что так долго, они были сложнее, чем обычно". Как оказалось, это было не дз, а пример двух неразрешенных задач в статистике. Звучит как выдуманная мотивационная история, но так оно и было, а решение задач в итоге вошло вот в эту публикацию.
Канторович до 1942 года жил в блокадном Ленинграде, его методы использовались в том числе и в ленд-лизе.
В 1949г с Канторовичем произошел неприятный случай: на заводе вагоностроения им. Егорова применили предложенный Канторовичем метод вырезания определенных форм из листов металла. В итоге выход продукции увеличился на 4%, но по итогу были неприятные последствия: — Уменьшился отход по металлолому, а как оказалось это был один из важных показателей завода. — Руководители завода решили, что раз в этом году получилось увеличить на 4%, то и в следующем получится, пришлось доказывать, что математика так не работает, они уже получили максимум из того, что ЛП может предложить. Интервью Канторовича. Раздел 5.1.6 из заметок Б.Т.Поляка
Канторович получил нобелевскую премию по экономике в 1975 году во многом за его упор на практическую часть и применение ЛП в промышленности. В частности одной из ключевых идей были shadow prices — вспомогательные величины, возникающие при решении ЛП и имеющие важную практическую интерпретацию (мат. двойственные переменные, лемма о чувствительности). Данциг же в большей степени занимался теорией и, собственно, разработал симплекс-метод, но без практического применения. Возможно из-за этого в духе "гонки вооружений" того времени в 1976 Данциг получает президентскую награду от Джеральда Форда.
Симплекс-метод достаточно быстро освоили в СССР, а о работах Канторовича разумеется знали на западе. Канторович с Данцигом много цитировали друг друга находясь по разные стороны железного занавеса. В 1979 году они даже опубликовали совместную работу. Канторович умер 7 апреля 1986 года, с Данцигом они так и не встретились лично…

Подпространства Крылова

Заголовок оригинальной статьи об методе итераций Крылова

Есть два принципиально разных подхода к решению систем линейных уравнений:

Алгебраический: например метод Гаусса, много раз вычитаем одно уравнение из других пока не приведем систему к виду, который легко решается. Как известно, нужно сделать $\approx n^2/2$ преобразований строк, чтобы привести к удобному треугольному виду.
Итерационный: например метод простой итерации, последовательно делаются аффинные преобразования, каждое преобразование приближает к решению, но за конченое число шагов точного решения не получить. Такие методы хорошо подходят для больших разреженных матриц — это такие, где большинство элементов нули, возникают например соцсетях, где нужно провести какой-либо анализ графа подписок: пользователей много, но в среднем один человек подписан на несколько интересных ему людей/каналов.

Методы первого типа хороши тем, что сходятся за конечное число шагов, второго — меньшими затратами по памяти и возможностью дешево получить приближенное решение. А теперь представьте, что есть метод, которые совмещает плюсы обоих подходов — это метод сопряженных градиентов, сейчас он присутствует во всех библиотеках линейной алгебры, например, питоновский scipy, методы BiCGSTAB и GMRES. Этот метод был опубликован в работах Хестенса-Штифеля и Флетчера-Ривза, но, по всеобщему признанию, основной идеей выступают подпространства Крылова, названные в честь Алексея Николаевича Крылова — он впервые обнаружил, что с помощью этих подпространств можно ускорять итерационные методы. Существуют и другие методы, основанные на подпространствах Крылова, например методы Арнольди и Ланцоша для нахождения собственных чисел, такие методы даже обычно называют методами "крыловского типа". Примечательно, что Роджер Флетчер (один из соавторов метода сопряженных градиентов) позднее поучаствовал в создании очень известных и популярных методов оптимизации BFGS и DFP (да, да, буква F в обоих случаях именно по этой причине), первый из которых также присутствует в большинстве оптимизационных пакетов, например, тот же питоновский scipy BFGS.

Матричные декомпозиции

Слева страница из книги Дуаера, справа - Хаусхолдера

На картинках выше примеры страниц из книг 1951 года Пола Дуаера и 1954 года Альстона Хаусхолдера, посвященные вычислительным методам линейной алгебры. С книгой Хаусхолдера в обиход вошёл матричный язык и, что гораздо важнее, декомпозиционный подход в линейной алгебре — представление существующих методов с помощью разложения матрицы в виде произведения других матриц. Для иллюстрации метода давайте вспомним метод Гаусса для решения систем линейных уравнений — приведение системы к виду с верхнетреугольной матрицей . Решение системы можно сделать с помощью обратной подстановки. Как оказывается такое приведение эквивалентно домножению обеих частей уравнения на нижнетреугольную матрицу для получения . Собственно декомпозиционный эквивалент методу Гаусса предлагает никак не менять правую часть, а посчитать с нижнетреугольной ( обратная к ) и решить две простые системы с помощью прямой подстановки и c помощью обратной подстановки (как и в оригинальном методе). Преимущество такого подхода легко видеть на примере когда нужно решить несколько систем с одинаковой матрицей , но разными правыми частями

Находим матрицы такие что — сложность $\mathcal{O}(n^3)$ . Решаем две системы и , результат — решение исходной системы, сложность $\mathcal{O}(n^2)$ .
Если решить несколько систем с одинаковой матрицей и правыми частями , то нужно один раз сделать разложение, а потом раз применить прямую и обратные подстановки. При использовании обычного метода Гаусса $\mathcal{O}(kn^3)$ , при использовании декомпозиции $\mathcal{O}(n^3+kn^2)$ .

Описанное выше обычно называется LU-декомпозицией. Трюк с решением двух систем распространяется и на декомпозиции с большим числом сомножителей. Из наиболее важных декомпозиций, использующихся на практике — LU-декомпозиция, декомпозиция Холесского, QR-декомпозиция, декомпозиция Шура, спектральное и сингулярное разложения. Рассказывать подробно про каждую не очень хочется, но хотелось бы отметить еще одно важное преимущество декомпозиционных методов: для всех декомпозиций существуют эффективные методы пересчета за $\mathcal{O}(n^2)$ при однорагновом апдейте $A \rightarrow A+uv$ вместо $\mathcal{O}(n^3)$ для полного перестроения. Подобные вычисления применяются например в уже ранее упомянутом BFGS, а его наиболее распространенный вариант L-BFGS напрямую использует идею одноранговых апдейтов для уменьшения потребления памяти. Построение PCA в онлайн режиме также сводится к применению одноранговых апдейтов к сингулярной декомпозиции.

Фортран

Мне кажется, что наиболее понятное сравнение: Фортран — это Python того времени. Вычислительные машины только появлялись и это было что-то совершенно новое и непонятное. В какой-то момент математики и физики начали понимать, что это очень перспективно, но было совершенно непонятно что эти программисты делают. Fortran = Formulae Translator предоставил простой способ делать программы для учёных. Разница по удобству использованию на тот момент была схожа разнице между Python и C/C++ сейчас.

А что сейчас?

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

QR-алгоритм

QR-алгоритм — это алгоритм нахождения собственных чисел матрицы на основе QR-разложения. Про собственные числа подробно рассказывать не хочется, если знаете — хорошо, если не знаете, то вот два примера:

Колебания и резонанс: я уже пару раз упомянул, что в динамических системах устойчивости являются фундаментальным вопросом проектирования. Есть важный класс устойчивых систем, которые при этом находятся в движения — колебательные системы, например маятник или струны музыкальных инструментов. Два основных свойств колебания — амплитуда и частота — могут быть вычислены из собственных чисел матрицы системы. Связное с колебаниями понятие — резонанс — явление когда амплитуда колебаний усиливается под внешним воздействием других колебаний, простой пример — раскачивание на качелях. От резонанса может быть хороший эффект, например вся радиопередача основана на резонировании с определенными частотами, а гармония в теории музыки построена на контролируемом резонансе нот. Может быть и плохой эффект, например, в приложенном видео заснято обрушение Такомского моста в 1940 году под воздействием сильного ветра, причиной считаемся именно неудачность конструкции, повлекшую к резонансу (при подготовке материала встречал и другие мнения, напишите в комментариях если знаете детали), поэтому так важно уметь колебания анализировать и контролировать.
PageRank: считается, что алгоритм PageRank обеспечил первичный успех Google. Он оценивает вероятность оказаться на определенной странице в сети, случайно переходя по ссылкам. С математической точки зрения задача заключается в нахождении собственного вектора наибольшего собственного числа матрицы. Хоть QR и может быть применен для решения этой задачи, но все-таки он решает задачу более общую и в данном контексте оказывается неэффективным.

Быстрая сортировка

Приведение последовательности в неубывающий порядок с помощью быстрой сортировки

Основная сортировка в С/С++, невозможно представить себе книгу по алгоритмам, где есть раздел про сортировки, но нет quicksort. Является частью алгоритма IntroSort, который используется в качестве основного алгоритма сортировки почти во всех основных компиляторах С++: GCC, Clang, MSVC. IntroSort — это quicksort, но если уровень рекурсии превысил некоторый порог, то переключаемся на heapsort, а уже если у нас остался небольшой кусочек — сортируем его вставками. Почему вставками? Просто на практике выяснилось, что для небольших массивов он лучше любых логарифмических сортировок.

Идея быстрой сортировки довольно простая: если взять произвольный элемент , то за линейное время легко переставить элементы массива так, чтобы элементы меньше стояли в начале, а больше - в конце. Применив эту процедуру рекурсивно для получившихся частей получается алгоритм сортировки, доказательство асимптотической оценки $\mathcal{O}(n\log n)$ является небольшим математическим упражнением.

Быстрое преобразование Фурье

Впервые FFT был упомянут еще в работах Карла Фридриха Гаусса, он использовал FFT для предсказания траекторий астероидов Паллады и Юноны. В пункте про QR-алгоритм уже обсуждали колебания, в этом продолжим, но уже по другому поводу. Так получилось, что в природе очень много микропроцессов представляют собой колебания (обычно их называют волнами), вот пара примеров:

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

Дискретное преобразование Фурье (DFT, Discrete Fourier Transform) — это довольно мощный практический инструмент для анализа волн, который позволяет понять с какими частотами резонирует волна. Например если бы вы засняли на видео колебания маятника часов, в каждом кадре видео вычислили бы позицию маятника на этом кадре, а потом применили DFT на замеренной последовательности позиций, то получили бы период колебания маятника. Из анализа DFT мы знаем, что человеческий голос состоит по большей части из частот 80-400Гц. Каким частотам соответствуют сейсмические волны, образующиеся во время взрыва ядерного оружия я не знаю, но полагаю, что знали Джеймс Кули и Джон Тьюки — авторы первого эффективного алгоритма подсчета DFT. Тьюки предлагал использовать сейсмометры для отслеживания проведения ядерных испытаний в СССР, но судя по всему для реализации этой идеи нужны были эффективные методы для подсчета DFT, так на свет появилось быстрое преобразование Фурье (FFT, Fast Fourier Transform).

Основная идея FFT Кули-Тьюки

Пусть , обозначим $X_{even}=(x_0, _x2, \ldots, x_{n-2}), X_{odd}=(x_1, x_3, \ldots, x_{n-1})$ — элементы с четных и нечетных позиций вектора , еще обозначим $Y_{low}=(y_0, y_1, \ldots, y_{m-1}), Y_{high}=(y_m, y_{m+1}, \ldots,y_{n-1})$ — первая и вторая половина вектора .

$\left[\begin{array}{c}x_0 \\ x_1 \\ \vdots \\ x_{n-1}\end{array}\right] \Rightarrow{y_k=\sum_{j=0}^{n-1}e^{-\frac{2\pi ijk}{n}}x_j} \Rightarrow\left[\begin{array}{c}y_0 \\ y_1 \\ \vdots \\ y_{n-1}\end{array}\right]$

Если — это n-элементное дискретное преобразование Фурье, то заметим, что

$Y_{low}=FT_m(X_{even})+e^{-\frac{2\pi i}{n}m}FT_m(X_{odd})\\ Y_{high}=FT_m(X_{even})-e^{-\frac{2\pi i }{n}m}FT_m(X_{odd})$

Первое равенство проверяется честной подстановкой формул, а вот второе требует небольшого преобразования и опирается на равенство $e^{\pi i}=-1$ . Алгоритм Кули-Тьюки дополняет до ближайшей степени двойки и рекурсивно применяет формулы выше.

Асимптотический анализ: чтобы посчитать $FT_{2m}$ нужно посчитать два преобразования $FT_{m}$ и сделать линейный проход для итогового подсчета. Таким образом, время работы алгоритма на n-элементном векторе имеет рекуррентную зависимость

$T(2m)=2T(m)+\mathcal{O}(m)$

Из основной теоремы о рекуррентных соотношениях получаем $T(n)=\mathcal{O}(n\log n)$ .

После публикации в 1965 году алгоритм и его аналоги прочно обосновались во всех областях цифровой обработки сигнала, вот несколько примеров применения

JPEG использует ~~FFT~~ Discrete cosine transform, DCT для сжатия картинок. Примерно это выглядит так: делаем ~~DFT~~ DCT, убираем/квантуем/сжимаем как-то еще отдельные частоты, когда нужно отобразить картинку делаем обратное преобразование. MPEG и H.264 используют схожие техники для видео, mp3 для аудио.
С помощью FFT можно контролировать размытие и резкость.
Большинство нейросетей для распознавания речи используют FFT как один из шагов предобработки.
FFT используется для анализа ЭКГ и ЭЭГ
Технология OFDM, основанная на FFT, является ключевой для WiFi

Применение вне цифровой обработки сигналов:

Алгоритм Шёнхаге-Штрассена и другие варианты перемножения чисел
Эффективные вычисления в кодах Рида-Соломона
Ускорение вычислений в модели Блэка-Шоулза

Поиск целочисленных отношений

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

Доказательство формулы для π, правда опустили кучу технических выкладок

Есть набор вещественных чисел $x_1, x_2, \ldots, x_n\in \mathbb{R}$ , нужно найти набор целых чисел $a_1, a_2, \ldots, a_n\in\mathbb{Z}$ , чтобы хотя бы одно было ненулевым, и при этом выполнялось

$a_1\cdot x_1 + a_2\cdot x_2+ \ldots+ a_n\cdot x_n =0$

Для можно применить модификацию алгоритма Евклида
Для алгоритмы гораздо сложнее, наиболее значимые PSOS (Partial Sum of Squares), PSLQ (PSOS+LQ decomposition), LLL (Lenstra–Lenstra–Lovász), HJLS Algorithm (Håstad–Just–Lagarias–Schnorr).
C помощью PSLQ была получена одна из эффективных формул для числа $\pi$

$\pi=\sum_{k=0}^\infty\frac{1}{16^k}\left(\frac{4}{8k+1}-\frac{2}{8k+4}-\frac{1}{8k+5}-\frac{1}{8k+6}\right)$

Выражение было найдено с помощью применения PSLQ к вектору $x_1,x_2, \ldots, x_8, \pi$ , где

$x_i=\sum_{k=0}^\infty\frac{1}{16^k}\frac{1}{8k+i}$

Fast multipole method

Иллюстрация разделимых множеств из оригинальной статьи

Придуман для ускорения вычислений в задаче тел. Суть задачи в том, что есть система из объектов, воздействующих друг на друга, например электромагнитным взаимодействием если речь идёт о частицах или гравитационным в случае небесных тел. Если , то науке не известно аналитическое решение, позволяющее просчитать траекторию тел в этой системе. Для численной симуляции такой системы нужно уметь вычислять силы, действующие на каждую из частиц при фиксированном положении каждой из частиц. Простейший алгоритм — вычисление попарного взаимодействия, fast multipole method позволяет проделать тоже самое быстрее.

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

При подсчете влияния группы точек $x_1, \ldots, x_m$ на группу точек $y_1, \ldots, y_k$ с помощью приближения по Тейлору нужно посчитать несколько выражений вида

$\sum_{i=1}^n(x-y_i)^\ell=a_0x^\ell+a_1x^{\ell-1}\left(\sum_{i=1}^my_i\right)+\ldots+a_\ell\left(\sum_{i=1}^ny_i^\ell\right)$

где коэффициенты зависят только от $\ell$ и могут быть посчитаны заранее, а Величины $\sum_{i=1}^ny_i^t$ достаточно вычислить один раз и не пересчитывать для каждого . В итоге одно такое объединение имеет сложность $\mathcal{O}(\ell(m+k))$ и при акуратном иерархическом разделении ведёт к сложности $\mathcal{O}\left(n\log (1/\epsilon)\right)$ , где - число точек, $\epsilon$ - желаемая точность, против наивного алгоритма со сложностью $\mathcal{O}(n^2)$ .

Не вошедшие, но более чем достойные

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

Умножение Карацубы

В 1960 году А. Н. Колмогоров озвучил на семинаре мех-мата МГУ гипотезу о том, что не существует алгоритма перемножения чисел быстрее, чем $\mathcal{O}(n^2)$ , где - длина чисел (т.е. обычное умножение в столбик). Присутствующий на семинаре А. А. Карацуба в течение недели придумывает алгоритм, имеющий сложность $\mathcal{O}(n^{\log_23})$ . Алгоритм имеет вид "разделяй и властвуй", при перемножении числа делятся на старшие и младшие цифры

$a=c+dx \\ b=e+fx$

Произведение чисел тогда имеет вид

Основная идея заключается в следующем соотношении

Что позволяет сэкономить одно умножение на подсчете . Применяя описанную процедуру рекурсивно получаем алгоритм Карацубы с указанной асимптотикой.

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

Алгоритм также вдохновил методы Тоома-Кука также для перемножения чисел и алгоритм Штрассена для перемножения матриц.

Протокол Диффи-Хеллмана

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

Алиса и Боб публично договариваются использовать простой модуль $\color{blue}{p}$ и базу $\color{blue}{g}$ .
Алиса выбирает число $\color{red}{a}$ и передаёт по каналу число $\color{blue}{g^a\bmod p}$ . Боб выбирает число $\color{red}{b}$ и передаёт $\color{blue}{g^b\bmod p}$
Алиса получает число $\color{blue}{g^b\bmod p}$ и вычисляет $\color{blue}{(g^b\bmod p)}^{\color{red}{a}}\color{blue}{\bmod ~p}=\color{red}{g^{ab}\bmod p}$ . Боб получает число $\color{blue}{g^a\bmod p}$ и вычисляет $\color{blue}{(g^a\bmod p)}^{\color{red}{b}}\color{blue}{\bmod ~p}=\color{red}{g^{ab}\bmod p}$ . Таким образом Алисе и Бобу теперь известно число, не известное другим.

Протокол основывается на сложности задачи дискретного логарифмирования, т.е. задачи нахождения зная и $g^b\bmod p$ . Протокол является безальтернативным и является де факто стандартом RFC 5114, RFC 7919. Стоит отметить, что вместо умножению по модулю можно использовать умножение в любой другой группе, наиболее привлекательной в этом плане является группа точек эллиптической кривой.

Коды Рида-Соломона

Схема QR-кода. Error correction соответствует избыточным данным от кодов Рида-Соломона

Теория избыточного кодирования в целом пытается ответить на следующий вопрос: каким образом организовать передачу данных по каналу связи, где данные могут быть потеряны или искажены? Две основные задачи: данные искажаются и мы знаем или не знаем какие именно. Первая задача обычно проще второй. Если мы пытаемся закодировать сообщение длины в виде сообщения длины , то невозможно придумать алгоритм, который бы исправлял больше произвольных ошибок, иначе бы мы изобрели универсальный алгоритм сжатия. Это свойство обычно называется границей Синглтона для первой задачи. Для второй задачи есть аналогичная оценка на возможность исправить не более ошибок. Коды Рида-Соломона достигают обеих оценок. Вот описание алгоритма для первой задачи:

Хотим передать сообщение $a_0, \ldots, a_{n-1}$
Строим многочлен $P(x)=a_0+a_1x+\ldots + a_{n-1}x^{n-1}$
Вычисляем $P(1), P(2), \ldots, P(n+k)$
Передаем значения $P(\cdot)$ теряя при этом не более значений
Интерполяционная теорема: если и - многочлены степени и их значения совпадают в различных точках, то .
Проводим интерполяцию, восстанавливаем и, следовательно, исходное сообщение.
Проводим все вычисления в конечных полях, ошибки округления позволить себе не можем. В идеале в $GF(2^{8\ell})$ .

Коме передачи данных (RFC 5510, RFC 6865) коды Рида-Соломона применяются для хранения данных RAID 6, для улучшения распознавания QR кодов и многих других.

Алгоритм Дейкстры

Нахождение вершин в порядке отдаления от s в алгоритме Дейкстры

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

Все вершины графа можно упорядочить по удалению от исходной вершины . Пусть это порядок $s=x_1, x_2, \ldots, x_n$ . Если веса рёбер строго положительные, то минимальный путь из в проходит только по вершинам при .
Если мы сумели найти первые вершин по отдалению от , то вершину можно однозначно определить из путей по уже найденным.
Находим вершины по очереди пользуясь предыдущим свойством.

Все современные методы построения маршрутов либо основаны на алгоритме А* - модифицированном Дейкстре, либо на несколько порядков сложнее в восприятии. Используется например в OSM.

Алгоритм Ахо-Корасик

Автомат Ахо-Корасик, красным обозначены суффиксные ссылки

Известный алгоритм Кнута-Морриса-Пратта (который кстати говоря был за год до этой троицы открыт Юрием Матиясевичем) решает задачу нахождения строки в тексте за время $\mathcal{O}(|S|+|T|)$ . Самый просто способ описать этот алгоритм - это подсчёт префикс-функции на конкатенации $S\#T$ ( $\#$ - просто какой-то символ, которого нет ни в , ни в ). Подсчет префикс-функции в общем то уже даёт линейный алгоритм. Но всё же куда более интересный как на практике, так и в теории вариант алгоритма заключается в построении небольшого конечного автомата по на основе префикс функции и применении его к . Как оказалось, построение за линейное время такого автомата сделать и для нескольких строк $S_1, \ldots, S_k$ , что показали Альфред Ахо и Маргарет Корасик. Технически, автомат Ахо-Корасик - это Trie, дополненный суффиксными ссылками - аналог переходов в префикс-функции, суффиксная ссылка узла ведёт в другой узел, соответствующий наибольшему суффиксу исходного узла, который присутствует в Trie. Подсчёт суффиксных ссылок поверх Trie можно сделать за линейное время по аналогии с префикс функцией. Алгоритм Ахо-Корасик используется в варианте grep.

Алгоритм сортировочной станции

Обратная польская нотация - это способ записи математических выражений, её еще называют постфиксной нотацией. Например привычное выражение

$3 + 4 \times (2 − 1)$

в инфиксной нотации (да, это так называется) принимает следующий вид в обратной польской записи

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

Стохастический градиентный спуск

Несколько вариантов траекторий градиентного спуска

"Last but not least", стохастический градиентный спуск (СГД) решает задачу минимизации

$\min_xf(x)$

при помощи построения последовательности

$x_{k+1}=x_k- \alpha_kg(x_k, \zeta_k), ~~\mathbb{E}_\zeta g(x, \zeta)=\nabla f(x).$

В случае применения для функционала среднего риска при $x=(x_1, \ldots, x_m)$

$f(x)=\frac{1}{m}\sum_{i=1}^m\delta(x_i)$

Можно использовать функцию $g(x, \xi)=\nabla\delta(x_\xi)$ , $\xi$ - случайное число в диапазоне $\{1, 2, \ldots, m\}$ . По сравнению с градиентным спуском для функции

$y_{k+1}=y_k-\alpha_k\nabla f(y_k),$

где один шаг требует вычисления значений $\delta$ , шаг СГД требует вычисления только одного значения $\delta$ . Несмотря на то, что градиентный спуск имеет лучшую скорость сходимости по числу итераций, для задач с большой выборкой СГД проводит настолько больше итераций, что на порядок быстрее в этой ситуации. СГД сыграл ключевую роль в становлении AI и является основной всех алгоритмов обучения. Популярные сегодя оптимизаторы такие как Adam, AdaGrad, RMSProp все имеют в своей основе СГД.

Друзья и коллеги! С удовольствием хотел бы прорекламировать CS Space — открытый научный клуб по CS-related темам; идейных последователей питерского Computer Science Club (и CS Center), расформировавшегося после известных событий. Ребята организуют крутые лекции и курсы по CS от профессионалов своего дела, да еще и помогают мне с написанием научно-популярных статей!

Сайт сообщества: csspace.io
Telegram-канал: t.me/csspace

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

Only registered users can participate in poll. Log in, please.

А как вы думаете, какие алгоритмы 20 века наиболее значимы?

28.57% Метод Монте-Карло10

31.43% Симплекс-Метод11

5.71% Итерационные методы подпространства Крылова2

11.43% Матричные декомпозиции4

8.57% Фортран3

5.71% QR алгоритм2

37.14% Быстрая сортировка13

65.71% Быстрое преобразование Фурье23

0% Алгоритмы поиска целочисленных отношений0

0% Fast multipole method0

11.43% Умножение Карацубы4

31.43% Протокол Диффи-Хеллмана11

25.71% Коды Рида-Соломона9

17.14% Алгоритм Дейкстры6

5.71% Алгоритм Ахо-Корасик2

11.43% Алгоритм сортировочной станции4

42.86% Стохастический градиентный спуск15

2.86% Свой вариант, напишу в комментариях1

35 users voted. 16 users abstained.

Hubs: