Хронология алгоритмов - Timeline of algorithms - Wikipedia

Следующее график алгоритмов описывает развитие алгоритмы (в основном «математические рецепты») с момента их появления.

Средневековый период

• Перед - письмо о "рецепты "(на кулинарию, ритуалы, сельское хозяйство и другие темы)
• c. 1700–2000 гг. До н.э. - Египтяне разрабатывают самые ранние известные алгоритмы для умножение два числа
• c. 1600 г. до н.э. - Вавилоняне разработать самые ранние известные алгоритмы для факторизация и найти квадратные корни
• c. 300 г. до н.э. - Алгоритм Евклида
• c. 200 г. до н.э. - Сито Эратосфена
• 263 г. н.э. - Гауссово исключение описанный Лю Хуэй
• 628 – Метод чакравалы описанный Брахмагупта
• c. 820 - Аль-Хорезми описанные алгоритмы решения линейные уравнения и квадратные уравнения в его Алгебра; слово алгоритм происходит от его имени
• 825 – Аль-Хаваризми описал алгоритм, алгоритмы использования Индусско-арабская система счисления в своем трактате О вычислении с помощью индусских цифр, который был переведен на латынь в качестве Algoritmi de numero Indorum, где "Алгоритми", переводом имени автора, возникло слово алгоритм (латинский алгоритм) со значением "метод расчета"
• c. 850 - криптоанализ и частотный анализ алгоритмы, разработанные Аль-Кинди (Алькиндус) в Рукопись о расшифровке криптографических сообщений, который содержит алгоритмы взлома шифрование и шифры^[1]
• c. 1025 - Ибн аль-Хайсам (Альхазен) был первым математиком, который вывел формулу для суммы четвертых полномочия, а в свою очередь разрабатывает алгоритм определения общей формулы для суммы любых интеграл полномочия, что было основополагающим для развития интегральное исчисление^[2]
• c. 1400 - Ахмад аль-Калкашанди дает список шифры в его Субх аль-а'ша которые включают как замена и транспозиция, и впервые - шифр с множественными заменами для каждого простой текст письмо; он также дает описание и работает пример криптоанализ, включая использование таблиц частота букв и наборы букв, которые не могут совпадать в одном слове

До 1940 г.

• 1540 – Лодовико Феррари открыл способ найти корни полином четвертой степени
• 1545 – Джероламо Кардано опубликовал метод Кардано для поиска корней кубический многочлен
• 1614 – Джон Напье разрабатывает методику проведения расчетов с использованием логарифмы
• 1671 – Метод Ньютона – Рафсона разработан Исаак Ньютон
• 1690 – Метод Ньютона – Рафсона независимо разработан Джозеф Рафсон
• 1706 – Джон Мачин строит быстро сходящийся ряд обратных касательных для π и вычисляет π до 100 знаков после запятой
• 1789 – Юрий Вега улучшает формулу Мачина и вычисляет π до 140 знаков после запятой,
• 1805 – БПФ-подобный алгоритм известный Карл Фридрих Гаусс
• 1842 – Ада Лавлейс пишет первый алгоритм для вычислительной машины
• 1903 - А быстрое преобразование Фурье алгоритм представлен Карл Давид Толме Рунге
• 1926 – Алгоритм Борувки
• 1926 – Первичное разложение алгоритм представлен Грета Германн^[3]
• 1927 – Метод Хартри – Фока разработан для моделирования квантовой системы многих тел в стационарном состоянии.
• 1934 – Триангуляция Делоне разработан Борис Делоне
• 1936 – Машина Тьюринга, абстрактная машина разработан Алан Тьюринг, с другие развил современное понятие алгоритм.

1940-е годы

• 1942 - А быстрое преобразование Фурье алгоритм, разработанный G.C. Danielson и Корнелиус Ланцош
• 1945 – Сортировка слиянием разработан Джон фон Нейман
• 1947 – Симплексный алгоритм разработан Джордж Данциг

1950-е годы

• 1952 – Кодирование Хаффмана разработан Дэвид А. Хаффман
• 1953 – Имитация отжига представлен Николай Метрополис
• 1954 – Radix sort компьютерный алгоритм, разработанный Гарольд Х. Сьюард
• 1964 – Преобразование Бокса – Мюллера для быстрой генерации нормально распределенных чисел, публикуемых Коробка Джорджа Эдварда Пелхэма и Мервин Эдгар Мюллер. Независимо предварительно обнаружено Раймонд Э. А. С. Пейли и Норберт Винер в 1934 г.
• 1956 – Алгоритм Крускала разработан Джозеф Крускал
• 1956 – Алгоритм Форда – Фулкерсона разработан и опубликован Р. Форд мл. и Д. Р. Фулкерсон
• 1957 – Алгоритм Прима разработан Роберт Прим
• 1957 – Алгоритм Беллмана – Форда разработан Ричард Э. Беллман и Л. Р. Форд-младший
• 1959 – Алгоритм Дейкстры разработан Эдсгер Дейкстра
• 1959 – Сортировка оболочки разработан Дональд Л. Шелл
• 1959 – Алгоритм де Кастельжау разработан Поль де Кастельжау
• 1959 – QR-факторизация алгоритм независимо разработан Джон Г.Ф. Фрэнсис и Вера Кублановская^[4][5]
• 1959 – Конструкция электростанции Рабина – Скотта для преобразования NFA в DFA опубликовано Майкл О. Рабин и Дана Скотт

1960-е

• 1960 – Умножение Карацубы
• 1961 – CRC (циклический контроль избыточности) изобретен В. Уэсли Петерсон
• 1962 – Деревья АВЛ
• 1962 – Быстрая сортировка разработан К. А. Р. Хоар
• 1962 – Линейный алгоритм Брезенхема разработан Джек Э. Брезенхэм
• 1962 – Алгоритм «стабильного брака» Гейла – Шепли разработан Дэвид Гейл и Ллойд Шепли
• 1964 – Heapsort разработан Дж. У. Дж. Уильямс
• 1964 – многосеточные методы впервые предложено Р. П. Федоренко
• 1965 – Алгоритм Кули-Тьюки заново открыт Джеймс Кули и Джон Тьюки
• 1965 – Расстояние Левенштейна разработан Владимир Левенштейн
• 1965 – Алгоритм Кок-Янгера-Касами (CYK) независимо разработан Тадао Касами
• 1965 – Алгоритм Бухбергера для вычислений Базы Грёбнера разработан Бруно Бухбергер
• 1965 – Парсеры LR изобретен Дональд Кнут
• 1966 – Алгоритм Данцига для кратчайшего пути в графе с отрицательными ребрами
• 1967 – Алгоритм Витерби предложено Эндрю Витерби
• 1967 – Алгоритм Кок-Янгера-Касами (CYK) независимо разработан Дэниел Х. Младший
• 1968 – Алгоритм поиска по графу описанный Питер Харт, Нильс Нильссон, и Бертрам Рафаэль
• 1968 – Алгоритм риша для неопределенной интеграции разработан Роберт Генри Риш
• 1969 – Алгоритм Штрассена для матричного умножения, разработанного Фолькер Штрассен

1970-е годы

• 1970 – Алгоритм диника для вычисления максимального потока в сети потока Ефим (Хаим) А. Диниц
• 1970 – Алгоритм завершения Кнута – Бендикса разработан Дональд Кнут и Питер Б. Бендикс
• 1970 – Метод BFGS из квазиньютон учебный класс
• 1970 – Алгоритм Нидлмана – Вунша опубликовано Сол Б. Нидлман и Кристиан Д. Вунш
• 1972 – Алгоритм Эдмондса – Карпа опубликовано Джек Эдмондс и Ричард Карп, по существу идентичный Алгоритм диника с 1970 г.
• 1972 – Сканирование Грэма разработан Рональд Грэм
• 1972 – Красно-черные деревья и B-деревья обнаруженный
• 1973 – ЮАР алгоритм шифрования обнаружен Клиффорд Кокс
• 1973 – Марш джарвиса алгоритм, разработанный Р. А. Джарвис
• 1973 – Алгоритм Хопкрофта-Карпа разработан Джон Хопкрофт и Ричард Карп
• 1974 – Полларда п - 1 алгоритм разработан Джон Поллард
• 1974 – Quadtree разработан Рафаэль Финкель и Дж. Л. Бентли
• 1975 – Генетические алгоритмы популяризируется Джон Холланд
• 1975 – Алгоритм ро Полларда разработан Джон Поллард
• 1975 – Алгоритм сопоставления строк Ахо – Корасика разработан Альфред В. Ахо и Маргарет Дж. Корасик
• 1975 – Цилиндрическое алгебраическое разложение разработан Джордж Э. Коллинз
• 1976 – Алгоритм Саламина – Брента независимо обнаруженный Евгений Саламин и Ричард Брент
• 1976 – Алгоритм Кнута – Морриса – Пратта разработан Дональд Кнут и Воан Пратт и независимо Дж. Х. Моррис
• 1977 – Алгоритм поиска строки Бойера – Мура для поиска вхождения строки в другую строку.
• 1977 – ЮАР алгоритм шифрования заново открыл Рон Ривест, Ади Шамир, и Лен Адлеман
• 1977 – LZ77 алгоритм, разработанный Авраам Лемпель и Джейкоб Зив
• 1977 – многосеточные методы независимо разработан Ачи Брандт и Вольфганг Хакбуш
• 1978 – LZ78 алгоритм разработан из LZ77 к Авраам Лемпель и Джейкоб Зив
• 1978 – Алгоритм Брууна предложено для степени двойки Георг Бруун
• 1979 - Хачиян эллипсоидный метод разработан Леонид Хачиян
• 1979 – ID3 алгоритм дерева решений, разработанный Росс Куинлан

1980-е

• 1980 – Алгоритм Брента для обнаружения цикла Ричард П. Брендт
• 1981 – Квадратное сито разработан Карл Померанс
• 1981 – Алгоритм Смита – Уотермана разработан Темпл Ф. Смит и Майкл С. Уотерман
• 1983 – Имитация отжига разработан С. Киркпатрик, К. Д. Гелатт и М. П. Векки
• 1983 – Дерево классификации и регрессии (CART) алгоритм, разработанный Лео Брейман, и другие.
• 1984 – LZW алгоритм разработан из LZ78 к Терри Велч
• 1984 – Алгоритм внутренней точки Кармаркара разработан Нарендра Кармаркар
• 1984 - ACORN_PRNG обнаружен Роем Викрамаратна и используется в частном порядке
• 1985 – Имитация отжига независимо разработан В. Черны
• 1985 - Молекулярная динамика Кар – Парринелло разработан Роберто Автомобиль и Микеле Парринелло
• 1985 – Раскидистые деревья обнаружен Sleator и Tarjan
• 1986 – Блюм Блюм Шуб предложено Л. Блюм, М. Блюм, и М. Шуб
• 1986 – Нажмите, чтобы изменить алгоритм максимального потока Эндрю Голдберг и Роберт Тарьян
• 1986 - Метод дерева Барнса – Хат разработан Джош Барнс и Пит Хат для быстрого приближенного моделирования проблемы с телом
• 1987 – Быстрый мультипольный метод разработан Лесли Грингард и Владимир Рохлин
• 1988 – Специальное числовое сито разработан Джон Поллард
• 1989 - ACORN_PRNG опубликовано Роем Викрамаратна
• 1989 – Протокол Paxos разработан Лесли Лэмпорт

1990-е годы

• 1990 – Общее числовое поле сито разработан из SNFS к Карл Померанс, Джо Бюлер, Хендрик Ленстра, и Леонард Адлеман
• 1990 – Алгоритм Копперсмита – Винограда разработан Дон Копперсмит и Шмуэль Виноград
• 1990 – Алгоритм BLAST разработан Стивен Альтшул, Уоррен Гиш, Уэбб Миллер, Юджин Майерс, и Дэвид Дж. Липман из Национальные институты здоровья
• 1991 – Синхронизация без ожидания разработан Морис Херлихи
• 1992 – Алгоритм Дойча – Йожи предложено Д. Дойч и Ричард Джозса
• 1992 – C4.5 алгоритм, потомок ID3 алгоритм дерева решений, был разработан Росс Куинлан
• 1993 – Алгоритм априори разработан Ракешем Агравалом и Рамакришнаном Шрикантом
• 1993 – Алгоритм Каргера для вычисления минимального разреза связного графа Дэвида Каргера
• 1994 – Алгоритм Шора разработан Петр Шор
• 1994 – Преобразование Барроуза – Уиллера разработан Майкл Берроуз и Дэвид Уиллер
• 1994 – Агрегирование бутстрапа (упаковка) разработан Лео Брейман
• 1995 – AdaBoost алгоритм, первый практический алгоритм повышения, был представлен Йоав Фройнд и Роберт Шапир
• 1995 - софт-маржа Машина опорных векторов алгоритм был опубликован Владимир Вапник и Коринна Кортес. Он добавляет идею soft-margin к алгоритму 1992 года Бозера, Нгуйона, Вапника, и это алгоритм, на который люди обычно ссылаются, говоря о SVM.
• 1995 – Алгоритм Укконена для построения суффиксных деревьев
• 1996 – Алгоритм Брууна обобщены на произвольные четные составные размеры Х. Мураками
• 1996 – Алгоритм Гровера разработан Лов К. Гровер
• 1996 – РИПЭМД-160 разработан Ганс Доббертин, Антун Босселаерс, и Барт Пренил
• 1997 – Мерсенн Твистер генератор псевдослучайных чисел, разработанный Макото Мацумото и Таджуки Нисимура
• 1998 – PageRank алгоритм был опубликован Ларри Пейдж
• 1998 – алгоритм rsync разработан Эндрю Триджелл
• 1999 – повышение градиента алгоритм, разработанный Джером Х. Фридман
• 1999 – Алгоритм тысячелистника разработано Брюс Шнайер, Джон Келси, и Нильс Фергюсон

2000-е

• 2000 – Поиск темы по гиперссылке алгоритм анализа гиперссылок, разработанный Джоном Кляйнбергом
• 2001 – Цепной алгоритм Лемпеля – Зива – Маркова для сжатия разработан Игорь Павлов
• 2001 – Виола – Джонс Алгоритм обнаружения лиц в реальном времени был разработан Полом Виолой и Майклом Джонсом.
• 2001 – DHT (распределенная хеш-таблица) изобретен несколькими людьми из академических кругов и прикладных систем
• 2001 – BitTorrent опубликована первая полностью децентрализованная одноранговая система распространения файлов
• 2002 – Тест на простоту AKS разработан Маниндра Агравал, Нирадж Каял и Нитин Саксена
• 2002 – Алгоритм Гирвана – Ньюмана для обнаружения сообществ в сложных системах
• 2002 – Парсер Packrat разработан для генерации парсера, который анализирует PEG (грамматика синтаксического анализа) в линейном синтаксическом анализе времени, разработанном Брайан Форд
• 2009 – Биткойн опубликована первая децентрализованная криптовалютная система без доверия

2010-е

• 2013 – Протокол консенсуса Raft опубликовано Диего Онгаро и Джон Остерхаут
• 2015 – ЙОЛО («Ты смотришь один раз») - это эффективный алгоритм распознавания объектов в реальном времени, впервые описанный Джозеф Редмон и другие.

Рекомендации

1. Саймон Сингх, Кодовая книга, стр. 14–20
2. Виктор Дж. Кац (1995). «Идеи исчисления в исламе и Индии», Математический журнал 68 (3), стр. 163–174.
3. Чилиберто, Чиро; Хирцебрух, Фридрих; Миранда, Рик; Тейхер, Мина, ред. (2001). Приложения алгебраической геометрии к теории кодирования, физике и вычислениям. Дордрехт: Springer, Нидерланды. ISBN  978-94-010-1011-5.
4. Фрэнсис, J.G.F. (1961). "Преобразование QR, я". Компьютерный журнал. 4 (3): 265–271. Дои:10.1093 / comjnl / 4.3.265.
5. Кублановская, Вера Н. (1961). «О некоторых алгоритмах решения полной задачи на собственные значения». Вычислительная математика и математическая физика СССР. 1 (3): 637–657. Дои:10.1016 / 0041-5553 (63) 90168-X. Также опубликовано в: Журнал вычислительной математики и математической физики, 1 (4), стр. 555–570 (1961).