Спустя два с половиной месяца закончил свой аркадный автомат⁠⁠

Вот  некоторые из самых базовых алгоритмов/теорем открытые математиками. Используются для передачи сообщений, криптографии, построения геогр. карт, 3Д моделяции, графики, игр, расчитывания конструкций на компе и тд. (Их много, но тут наверно лишь <1% от общего числа) Почти все разработаны в 20ом веке:

Поиск в ширину

Поиск в глубину

Топологическая сортировка

Поиск компонент связности

Интегрирование по формуле Симпсона

Поиск компонент сильной связности, построение конденсации графа за O (N + M)

Поиск мостов за O (N + M)

Поиск точек сочленения за O (N + M)

Поиск мостов в режиме онлайн за O(1) в среднем

Минимальное остовное дерево. Алгоритм Крускала со структурой данных 'система непересекающихся множеств' за O (M log N)

Матричная теорема Кирхгофа. Нахождение количества остовных деревьев за O (N3)

Код Прюфера. Формула Кэли. Количество способов сделать граф связным

Наименьший общий предок. Нахождение за O (1) с препроцессингом O (N) (алгоритм Фарах-Колтона и Бендера)

Задача RMQ (Range Minimum Query - минимум на отрезке). Решение за O (1) с препроцессингом O (N)

Наименьший общий предок. Нахождение за O (1) в режиме оффлайн (алгоритм Тарьяна)

Алгоритм Эдмондса-Карпа нахождения максимального потока за O (N M2)

Метод Проталкивания предпотока нахождения максимального потока за O (N4)

Алгоритм сжатия Хаффмана

Теорема Пика. Нахождение площади решётчатого многоугольника за O (1) [TeX]

Задача о покрытии отрезков точками

Центры тяжести многоугольников и многогранников

Алгоритмы шифрования и хэша DES-1, 3DES, AES, RSA, Diffie-Hellman, Kerberos, MD1-5, SHA1, 2, 256, 1024

Z-функция строки и её вычисление за O (N)

Префикс-функция, её вычисление и применения. Алгоритм Кнута-Морриса-Пратта

Алгоритмы хэширования в задачах на строки

Алгоритм Рабина-Карпа поиска подстроки в строке за O (N)

Разбор выражений за O (N). Обратная польская нотация

Суффиксный массив. Построение за O (N log N) и применения

Суффиксный автомат. Построение за O (N) и применения

Нахождение всех подпалиндромов за O (N)

Декомпозиция Линдона. Алгоритм Дюваля. Нахождение наименьшего циклического сдвига за O (N) времени и O (1) памяти

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

Суффиксное дерево. Алгоритм Укконена

Поиск всех тандемных повторов в строке алгоритмом Мейна-Лоренца (разделяй-и-властвуй) за O (N log N)

Sqrt-декомпозиция

Дерево Фенвика

Система непересекающихся множеств

Дерево отрезков

Декартово дерево (treap, дерамида)

Модификация стека и очереди для нахождения минимума за O (1)

Рандомизированная куча

Игры на произвольных графах. Метод ретроспективного анализа за O (M)

Теория Шпрага-Гранди.