Хронология алгоритмов
Появление
Следующая хронология алгоритмов описывает развитие алгоритмов (в основном «математических рецептов») с момента их создания.
Средневековый период [ править ]
- Прежде – писать о « рецептах » (на кулинарию, ритуалы, сельское хозяйство и другие темы)
- в. 1700–2000 гг. До н.э. – египтяне разработали самые ранние известные алгоритмы умножения двух чисел.
- в. 1600 г. до н.э. - вавилоняне разрабатывают самые ранние известные алгоритмы факторизации и поиска квадратных корней.
- в. 300 г. до н. э. — алгоритм Евклида.
- в. 200 г. до н.э. – Решето Эратосфена.
- 263 г. н.э. - метод исключения Гаусса, описанный Лю Хуэем.
- 628 – Метод Чакравалы , описанный Брахмагуптой.
- в. 820 — Аль-Хаваризми описал алгоритмы решения линейных и квадратных уравнений в своей «Алгебре» ; слово алгоритм происходит от его имени
- 825 — Аль-Хаваризми описал алгоритмы использования индуистско-арабской системы счисления в своем трактате «О вычислении индуистскими цифрами» , который был переведен на латынь как Algoritmi de numero Indorum , где «Algoritmi», переводческая версия имя автора дало начало слову алгоритм ( лат. алгоритмус ) со значением «метод расчета».
- в. 850 — алгоритмы криптоанализа и частотного анализа , разработанные Аль-Кинди (Алкиндусом) в «Рукописи по расшифровке криптографических сообщений» , которая содержит алгоритмы взлома шифров и шифров. [1]
- в. 1025 — Ибн аль-Хайсам (Альхазен), был первым математиком, выведшим формулу суммы четвертых степеней , а он, в свою очередь, разработал алгоритм определения общей формулы суммы любых целых степеней. [2]
- в. 1400 г. - Ахмад аль-Калкашанди приводит список шифров в своей «Субх аль-аша» , которые включают как замену , так и транспозицию , и впервые представляет шифр с множественными заменами для каждой открытого текста буквы ; он также дает изложение и проработанный пример криптоанализа , включая использование таблиц частотности букв и наборов букв, которые не могут встречаться вместе в одном слове.
До 1940 года [ править ]
- 1540 – Лодовико Феррари открыл метод нахождения корней многочлена четвертой степени.
- 1545 - Джероламо Кардано опубликовал метод Кардано для поиска корней кубического многочлена.
- 1614 – Джон Нэпьер разрабатывает метод выполнения вычислений с использованием логарифмов.
- 1671 г. - метод Ньютона-Рафсона . разработал Исаак Ньютон
- 1690 г. - метод Ньютона-Рафсона независимо разработан Джозефом Рафсоном.
- 1706 - Джон Мачин разрабатывает быстро сходящийся ряд обратного тангенса для π и вычисляет π с точностью до 100 десятичных знаков.
- 1768 - Леонард Эйлер публикует свой метод численного интегрирования обыкновенных дифференциальных уравнений в задаче 85 книги Institutiones Calculi Integralis. [3]
- 1789 - Юрий Вега улучшает формулу Мачина и вычисляет число π с точностью до 140 десятичных знаков.
- 1805 г. - алгоритм, подобный БПФ, известен Карлом Фридрихом Гауссом.
- 1842 – Ада Лавлейс пишет первый алгоритм вычислительной машины.
- 1903 – быстрого преобразования Фурье . представил алгоритм Карл Дэвид Толме Рунге
- 1918 - Саундэкс
- 1926 – Алгоритм Борувки.
- 1926 - Алгоритм первичной декомпозиции представлен Гретой Херманн. [4]
- 1927 г. - разработан метод Хартри-Фока для моделирования квантовой системы многих тел в стационарном состоянии.
- 1934 – триангуляция Делоне разработана Борисом Делоне.
- 1936 — Машина Тьюринга , абстрактная машина , разработанная Аланом Тьюрингом , вместе с другими разработали современное понятие алгоритма .
1940-е годы [ править ]
- 1942 - Алгоритм быстрого преобразования Фурье , разработанный Г. К. Дэниэлсоном и Корнелиусом Ланцосом.
- 1945 – сортировку слиянием . разработал Джон фон Нейман
- 1947 – Симплексный алгоритм разработан Джорджем Данцигом.
1950-е годы [ править ]
- 1952 – кодирование Хаффмана . разработал Дэвид А. Хаффман
- 1953 – имитацию отжига . представил Николас Метрополис
- 1954 - сортировки по основанию. разработал компьютерный алгоритм Гарольд Х. Сьюард
- 1964 — Преобразование Бокса-Мюллера для быстрой генерации нормально распределенных чисел, опубликованное Джорджем Эдвардом Пелхэмом Боксом и Мервином Эдгаром Мюллером . Независимо предварительно обнаружен Раймондом EAC Пейли и Норбертом Винером в 1934 году.
- 1956 - алгоритм Краскала . разработал Джозеф Краскал
- 1956 - Алгоритм Форда-Фалкерсона разработан и опубликован Р. Фордом-младшим и Д. Р. Фулкерсоном.
- 1957 - алгоритм Прима . разработал Роберт Прим
- 1957 - Алгоритм Беллмана-Форда разработан Ричардом Э. Беллманом и Л.Р. Фордом-младшим.
- 1959 - алгоритм Дейкстры . разработал Эдсгер Дейкстра
- 1959 – сортировку Шелла . разработал Дональд Л. Шелл
- 1959 - Алгоритм Де Кастельжо, разработанный Полем де Кастельжо.
- 1959 - QR-факторизации Алгоритм независимо разработан Джоном Г.Ф. Фрэнсисом и Верой Кублановской. [5] [6]
- 1959 - Конструкция набора сил Рабина-Скотта для преобразования NFA в DFA, опубликованная Майклом О. Рабином и Даной Скотт.
1960-е годы [ править ]
- 1960 – Размножение Карацубы
- 1961 - CRC (циклическая проверка избыточностью) изобретен У. Уэсли Петерсоном.
- 1962 – Деревья АВЛ
- 1962 – Быстрая сортировка разработана CAR Hoare.
- 1962 - линейный алгоритм Брезенхэма. разработал Джек Э. Брезенхэм
- 1962 - Алгоритм «стабильного брака» Гейла-Шепли, разработанный Дэвидом Гейлом и Ллойдом Шепли.
- 1964 – пирамидальную сортировку . разработал Дж. У. Дж. Уильямс
- 1964 г. – многосеточные методы впервые предложены Р. П. Федоренко.
- 1965 - Алгоритм Кули-Тьюки заново открыт Джеймсом Кули и Джоном Тьюки.
- 1965 — дистанцию Левенштейна . разработал Владимир Левенштейн
- 1965 - Алгоритм Кока-Янгера-Касами (CYK) независимо разработан Тадао Касами.
- 1965 - Алгоритм Бухбергера для вычисления базисов Грёбнера, разработанный Бруно Бухбергером.
- 1965 – LR-парсеры . изобрел Дональд Кнут
- 1966 – Алгоритм Данцига для поиска кратчайшего пути в графе с отрицательными ребрами.
- 1967 - Алгоритм Витерби предложен Эндрю Витерби.
- 1967 - Алгоритм Кока-Янгера-Касами (CYK) независимо разработан Дэниелом Х. Янгером.
- 1968 — Алгоритм поиска по графу A* описан Питером Хартом , Нильсом Нильссоном и Бертрамом Рафаэлем.
- 1968 - Алгоритм Риша для неопределенного интегрирования, разработанный Робертом Генри Ришем.
- 1969 - Алгоритм Штрассена для умножения матриц, разработанный Фолькером Штрассеном.
1970-е годы [ править ]
- 1970 - Алгоритм Динича для расчета максимального расхода в проточной сети, автор Ефим (Хаим) А. Диниц.
- 1970 - Алгоритм завершения Кнута – Бендикса, разработанный Дональдом Кнутом и Питером Б. Бендиксом.
- 1970 г. – БФГС-метод квазиньютоновского . класса
- 1970 - Алгоритм Нидлмана-Вунша опубликован Солом Б. Нидлманом и Кристианом Д. Вуншем.
- 1972 - Алгоритм Эдмондса-Карпа , опубликованный Джеком Эдмондсом и Ричардом Карпом , по сути идентичен алгоритму Диника 1970 года.
- 1972 – сканирование Грэма , разработанное Рональдом Грэмом.
- 1972 г. - красно-черные деревья и B-деревья. обнаружены
- 1973 — RSA . обнаружил алгоритм шифрования Клиффорд Кокс
- 1973 - алгоритм марша Джарвиса , разработанный Р.А. Джарвисом.
- 1973 - Алгоритм Хопкрофта-Карпа разработан Джоном Хопкрофтом и Ричардом Карпом.
- 1974 - Алгоритм Полларда p - 1 разработан Джоном Поллардом.
- 1974 – Quadtree разработан Рафаэлем Финкелем и Дж. Л. Бентли.
- 1975 – Генетические алгоритмы популяризируются Джоном Холландом.
- 1975 - Ро-алгоритм Полларда разработан Джоном Поллардом.
- 1975 - Алгоритм сопоставления строк Ахо – Корасика разработан Альфредом В. Ахо и Маргарет Дж. Корасик.
- 1975 - Цилиндрическое алгебраическое разложение , разработанное Джорджем Э. Коллинзом.
- 1976 - Алгоритм Саламина-Брента независимо открыт Юджином Саламином и Ричардом Брентом.
- 1976 - Алгоритм Кнута-Морриса-Пратта разработан Дональдом Кнутом и Воаном Праттом и независимо Дж. Х. Моррисом.
- 1977 - Алгоритм поиска строки Бойера-Мура для поиска вхождения одной строки в другую строку.
- 1977 — RSA Алгоритм шифрования заново открыт Роном Ривестом , Ади Шамиром и Леном Адлеманом.
- 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 – раскидистые деревья. обнаружили Слейтор и Тарьян
- 1986 — Блюм Блюм Шуб , предложенный Л. Блюмом , М. Блюмом и М. Шубом.
- 1986 - Нажмите на перемаркировку алгоритма максимального потока Эндрю Голдберга и Роберта Тарьяна.
- 1986 - Метод дерева Барнса-Хата , разработанный Джошем Барнсом и Питом Хатом для быстрого приближенного моделирования задач n тел.
- 1987 – Метод быстрых мультиполей разработан Лесли Грингардом и Владимиром Рохлиным.
- 1988 – сито со специальным номерным полем. разработал Джон Поллард
- 1989 - ACORN PRNG , опубликованный Роем Викрамаратной.
- 1989 - Протокол Paxos разработан Лесли Лэмпортом.
- 1989 – список пропусков . обнаружил Уильям Пью
1990-е годы [ править ]
- 1990 - Сито общего числового поля разработано на основе Карлом SNFS Померансом , Джо Бюлером , Хендриком Ленстрой и Леонардом Адлеманом.
- 1990 - Алгоритм Копперсмита-Винограда, разработанный Доном Копперсмитом и Шмуэлем Виноградом.
- 1990 — Алгоритм BLAST разработан Стивеном Альтшулом , Уорреном Гишем , Уэббом Миллером , Юджином Майерсом и Дэвидом Дж. Липманом из Национальных институтов здравоохранения.
- 1991 - Синхронизация без ожидания, разработанная Морисом Херлихи.
- 1992 - Алгоритм Дойча-Йожы, предложенный Д. Дойчем и Ричардом Джожа.
- 1992 — алгоритм C4.5 , потомок алгоритма дерева решений ID3 . разработал Росс Куинлан
- 1993 - Алгоритм Apriori разработан Ракешем Агравалом и Рамакришнаном Срикантом.
- 1993 - Алгоритм Каргера для вычисления минимального разреза связного графа Дэвида Каргера.
- 1994 - Алгоритм Шора, разработанный Питером Шором.
- 1994 - преобразование Берроуза-Уиллера , разработанное Майклом Берроузом и Дэвидом Уилером.
- 1994 - Бутстрап-агрегирование (пакетирование), разработанное Лео Брейманом.
- 1995 - Алгоритм AdaBoost , первый практический алгоритм повышения, был представлен Йоавом Фройндом и Робертом Шапиром.
- с мягким запасом машины опорных векторов опубликовали алгоритм 1995 — Владимир Вапник и Коринна Кортес . Он добавляет идею мягкой маржи к алгоритму Бозера, Нгуйона, Вапника 1992 года и является алгоритмом, на который люди обычно ссылаются, говоря о SVM.
- 1995 – Алгоритм Укконена для построения суффиксных деревьев.
- 1996 - Алгоритм Брюуна на произвольные даже составные размеры. , обобщенный Х. Мураками
- 1996 - алгоритм Гровера , разработанный Ловом К. Гровером.
- 1996 — RIPEMD-160 разработан Хансом Доббертином , Антоном Босселерсом и Бартом Пренилом.
- 1997 - Mersenne Twister, генератор псевдослучайных чисел, разработанный Макото Мацумото и Тадзюки Нисимура.
- 1998 — PageRank . опубликовал алгоритм Ларри Пейдж
- 1998 — алгоритм rsync разработан Эндрю Триджеллом.
- 1999 г. - алгоритм повышения градиента , разработанный Джеромом Х. Фридманом.
- 1999 — Алгоритм Ярроу , разработанный Брюсом Шнайером , Джоном Келси и Нильсом Фергюсоном.
2000-е [ править ]
- 2000 - Тематический поиск по гиперссылкам. Алгоритм анализа гиперссылок, разработанный Джоном Кляйнбергом.
- 2001 – Алгоритм сжатия цепей Лемпеля – Зива – Маркова, разработанный Игорем Павловым.
- 2001 - Алгоритм Виолы-Джонса для обнаружения лиц в реальном времени был разработан Полом Виолой и Майклом Джонсом.
- 2001 - DHT (распределенная хеш-таблица) изобретена несколькими людьми из научных кругов и прикладных систем.
- 2001 — опубликована BitTorrent, первая полностью децентрализованная одноранговая система распространения файлов.
- 2001 - LOBPCG Локально оптимальный блочный метод сопряженных градиентов с предобуславливанием для поиска крайних собственных значений симметричных задач на собственные значения, Андрей Князев
- 2002 — тест простоты AKS , разработанный Маниндрой Агравалом , Нираджем Каялом и Нитином Саксеной.
- 2002 - Алгоритм Гирвана-Ньюмана для обнаружения сообществ в сложных системах.
- 2002 - разработан парсер Packrat для создания синтаксического анализатора, который анализирует PEG (грамматику выражений синтаксического анализа) в режиме линейного анализа, разработанного Брайаном Фордом.
- 2009 – Биткойн , не требующая доверия. опубликована первая децентрализованная криптовалютная система
2010-е [ править ]
- 2013 - Протокол консенсуса Raft опубликован Диего Онгаро и Джоном Оустерхаутом.
- 2015 — YOLO («Ты смотришь только один раз») — эффективный алгоритм распознавания объектов в реальном времени, впервые описанный Джозефом Редмоном и др. [7] [8] [9] [10] [11] [12]
Ссылки [ править ]
- ^ Саймон Сингх , Кодовая книга , стр. 14–20.
- ^ Виктор Дж. Кац (1995). «Идеи исчисления в исламе и Индии», журнал Mathematics Magazine 68 (3), стр. 163–174.
- ^ Брюс, Ян (29 июня 2010 г.). «Institutionum Calculi Integralis» Эйлера . www.17 Centurymaths.com . Архивировано из оригинала 1 февраля 2011 года . Проверено 17 мая 2023 г.
- ^ Силиберто, Чиро; Хирцебрух, Фридрих; Миранда, Рик; Тейчер, Мина , ред. (2001). Приложения алгебраической геометрии к теории кодирования, физике и вычислениям . Дордрехт: Springer Нидерланды. ISBN 978-94-010-1011-5 .
- ^ Фрэнсис, JGF (1961). «QR-трансформация, я» . Компьютерный журнал . 4 (3): 265–271. дои : 10.1093/comjnl/4.3.265 .
- ^ Кублановская, Вера Н. (1961). «О некоторых алгоритмах решения полной проблемы собственных значений». Вычислительная математика и математическая физика СССР . 1 (3): 637–657. дои : 10.1016/0041-5553(63)90168-X . Опубликовано также в: Журнал вычислительной математики и математической физики, 1(4), стр. 555–570 (1961).
- ^ «YOLO: Обнаружение объектов в реальном времени» . 19 декабря 2023 года. Архивировано из оригинала 19 декабря 2023 года . Проверено 19 декабря 2023 г.
- ^ «Понимание сети обнаружения объектов в реальном времени: вы смотрите только один раз (YOLOv1)» . 19 декабря 2023 года. Архивировано из оригинала 20 декабря 2023 года . Проверено 20 декабря 2023 г.
- ^ «Как использовать даркнет для обучения собственной нейронной сети» . 20 декабря 2023 года. Архивировано из оригинала 20 декабря 2023 года . Проверено 20 декабря 2023 г.
- ^ «Как компьютеры учатся мгновенно распознавать объекты» . 20 декабря 2023 года. Архивировано из оригинала 20 декабря 2023 года . Проверено 20 декабря 2023 г.
- ^ «Даркнет: платформа с открытым исходным кодом для глубоких нейронных сетей» . 20 декабря 2023 года. Архивировано из оригинала 20 декабря 2023 года . Проверено 20 декабря 2023 г.
- ^ «Ваш подробный путеводитель по семейству моделей YOLO» . 21 декабря 2023 года. Архивировано из оригинала 21 декабря 2023 года . Проверено 21 декабря 2023 г.