Временная шкала алгоритмов
редактировать
Следующая временная шкала алгоритмов описывает развитие алгоритмов (в основном «математических рецепты ») с момента их создания.
Содержание
- 1 Средневековый период
- 2 До 1940-х годов
- 3 1940-х
- 4 1950-х
- 5 1960-х
- 6 1970-х
- 7 1980-х
- 8 1990-х
- 9 2000-е
- 10 2010-е
- 11 Источники
Средневековый период
- До - писать о «рецептах » (по кулинарии, ритуалам, сельскому хозяйству и другим темам)
- с. 1700–2000 гг. До н.э. - Египтяне разработали самые ранние известные алгоритмы умножения двух чисел
- c. 1600 г. до н.э. - вавилоняне разработали самые ранние известные алгоритмы для факторизации и нахождения квадратных корней
- c. 300 г. до н.э. - алгоритм Евклида
- c. 200 г. до н.э. - Сито Эратосфена
- 263 г. н.э. - Гауссово устранение, описанное Лю Хуэй
- 628 - Метод Чакравалы, описанный Брахмагуптой
- в. 820 - Аль-Хаваризми описал алгоритмы решения линейных уравнений и квадратных уравнений в своей Алгебре ; слово алгоритм происходит от его имени
- 825 - Аль-Хаваризми описал алгоритм, алгоритмы использования индуистско-арабской системы счисления, в его трактате «О вычислении с помощью индусских цифр», который был переведен на латынь как Algoritmi de numero Indorum, где «Algoritmi», перевод имени автора переводчиком, дал начало слову алгоритм (латинский алгоритм) со значением «метод расчета»
- c. 850 - алгоритмы криптоанализа и частотного анализа, разработанные Аль-Кинди (Алькиндус) в «Рукописи по расшифровке криптографических сообщений», в которой содержатся алгоритмы взлома шифрования и шифры
- c. 1025 - Ибн аль-Хайтам (Альхазен), был первым математиком, который вывел формулу для суммы четвертых степеней, и, в свою очередь, он разработал алгоритм для определения общей формула для суммы любых интегральных степеней, которая была фундаментальной для развития интегрального исчисления
- c. 1400 - Ахмад аль-Калкашанди приводит список шифров в своем Субх аль-а'ша, которые включают как замену, и транспозицию, и впервые - шифр с множественными заменами для каждой буквы открытого текста ; он также дает описание и рабочий пример криптоанализа, включая использование таблиц частотности букв и наборов букв, которые не могут встречаться вместе в одном слове
До 1940 года
- 1540 - Лодовико Феррари открыл метод поиска корней полинома четвертой степени
- 1545 - Джероламо Кардано опубликовал метод Кардано для поиска корней кубический полином
- 1614 - Джон Напье разрабатывает метод для выполнения вычислений с использованием логарифмов
- 1671 - метод Ньютона – Рафсона, разработанный Исаак Ньютон
- 1690 - Метод Ньютона – Рафсона независимо разработан Джозефом Рафсоном
- 1706 - Джон Мачин разрабатывает быстро сходящийся ряд обратных касательных для π и вычисляет π с точностью до 100 десятичных знаков. места
- 1789 - Юрий Вега улучшает формулу Мачина и вычисляет π до 140 десятичных знаков,
- 1805 - алгоритм, подобный БПФ, известный Карл Фридрих Гаусс
- 1842 - Ада Лавлейс пишет первый алгоритм для вычислительной машины
- 1903 - алгоритм быстрого преобразования Фурье, представленный Карлом Дэвидом Толме Рунге
- 1926 - Борувкой. алгоритм
- 1926 - Алгоритм первичной декомпозиции, представленный Гретой Герман
- 1927 - метод Хартри – Фока разработан для моделирования квантовой системы многих тел в стационарном состоянии.
- 1934 - Триангуляция Делоне, разработанная Борисом Делоне
- 1936 - машина Тьюринга, абстрактная машина, разработанная Алан Тьюринг и другие разработали современное понятие алгоритма.
1940-е
1950-е годы
- 1952 - кодирование Хаффмана разработано Дэвидом А. Хаффманом
- 1953 - Имитация отжига введена Николасом Метрополисом
- 1954 - компьютерный алгоритм Radix sort, разработанный Гарольдом Х. Сьюардом
- 1964 - преобразование Бокса – Мюллера для быстрой генерации нормально распределенных чисел, опубликованный Джорджем Эдвардом Пелхэм Бокс и Мервин Эдгар Мюллер. Независимо предварительно обнаружено Раймондом Е.А. Пэли и Норбертом Винером в 1934 году.
- 1956 - алгоритм Краскала, разработанный Джозефом Краскалом
- 1956 - алгоритм Форда – Фулкерсона разработан и опубликован Д. Р. Фулкерсон
- 1957 - алгоритм Прима, разработанный Робертом Примом
- 1957 - алгоритм Беллмана – Форда, разработанный Ричардом Э. Беллманом и Л. Р. Форд, младший
- 1959 - алгоритм Дейкстры, разработанный Эдсгер Дейкстра
- 1959 - Сортировка Shell, разработанный Дональдом Л. Шелл
- 1959 - Алгоритм Де Кастельжау, разработанный Полом де Кастельжау
- 1959 - QR-факторизация алгоритм независимо разработан Джоном Г.Ф. Фрэнсис и Вера Кублановская
- 1959 - конструкция Powerset Рабина – Скотта для преобразования NFA в DFA, опубликованная Майклом О.. Рабин и Дана Скотт
1960-е
1970-е годы
- 1970 - алгоритм Динича для вычисления максимального потока в потоковой сети Ефимом (Хаимом) А. Диницем
- 1970 - алгоритм завершения Кнута – Бендикса, разработанный Дональдом Кнутом и
- 1970 - метод BFGS из квази- Ньютон класс
- 1970 - алгоритм Нидлмана – Вунша опубликован Солом Б. Нидлманом и Кристианом Д. Вуншем
- 1972 - Алгоритм Эдмондса-Карпа, опубликованный Джеком Эдмондсом и Ричардом Карпом, по существу идентичен алгоритму Динича из 1970
- 1972 - Сканирование Грэма разработано Рональдом Грэмом
- 1972 - Красно-черные деревья и B-деревья обнаружены
- 1973 - Алгоритм шифрования RSA, открытый Клиффордом Коксом
- 1973 - алгоритм Джарвиса Марча, разработанный
- 1973 - алгоритм Хопкрофта – Карпа разработанный Джон Хопкрофт и Ричард Карп
- 1974 - алгоритм p - 1 Полларда разработан Джоном Поллардом
- 1974 - Quadtree разработан Рафаэлем Финкелем и JL Bentley
- 1975 - Генетические алгоритмы популяризировал Джон Холланд
- 1975 - Ро-алгоритм Полларда разработан Джоном Поллардом
- 1975 - Алгоритм сопоставления строк Ахо – Корасика разработан Альфредом В. Ахо и Маргарет Дж. Корасик
- 1975 - Цилиндрическое алгебраическое разложение разработано Джорджем Э.. Коллинз
- 1976 - алгоритм Саламина – Брента независимо обнаружен Юджином Саламином и Ричардом Брентом
- 1976 - алгоритм Кнута – Морриса – Пратта разработан Дональдом Кнутом и Воаном Праттом и независимо Дж. Х. Моррис
- 1977 - алгоритм поиска строки Бойера – Мура для поиска вхождения строки в другую строку.
- 1977 - алгоритм шифрования RSA заново открыт Рон Ривест, Ади Шамир и Лен Адлеман
- 1977 - алгоритм LZ77, разработанный Абрахамом Лемпелем и Якоб Зив
- 1977 - многосеточные методы, независимо разработанные Ачи Брандтом и Вольфгангом Хакбушем
- 1978 - алгоритм LZ78, разработанный на основе LZ77 от Авраама Лемпеля и Якоба Зива
- 1978 - алгоритм Брууна, предложенный для степени двойки
- 1979 - алгоритм Хачияна метод эллипсоида, разработанный Леонидом Хачияном
- 1979 - ID3 алгоритм дерева решений, разработанный Росс Куинлан
1980-е годы
1990-е годы
- 1990 - Сито общего числового поля разработано на основе SNFS, разработано Карлом Померансом, Джо Булером, Хендрик Ленстра и Леонард Адлеман
- 1990 - Алгоритм Копперсмита – Винограда, разработанный Доном Копперсмитом и Шмуэлем Виноградом
- 1990 - алгоритм BLAST разработан Стивеном Альтшулом, Уорреном Гишем, Уэббом Миллером, Юджином Майерсом, и Дэвид Дж. Ли pman из Национальных институтов здравоохранения
- 1991 - Синхронизация без ожидания разработана Морисом Херлихи
- 1992 - предложен алгоритм Дойча – Йожи Автор Д. Deutsch и Ричард Джозса
- 1992 - Алгоритм C4.5, потомок алгоритма дерева решений ID3, был разработан Росс Куинлан
- 1993 - Алгоритм априори, разработанный Ракешем Агравалом и Рамакришнаном Срикантом
- 1993 - алгоритм Каргера для вычисления минимального разреза связного графа Дэвида Каргера
- 1994 - алгоритм Шора, разработанный Питером Шором
- 1994 - преобразование Барроуза-Уиллера, разработанный Майклом Берроузом и Дэвидом Уилером
- 1994 - Агрегирование начальной загрузки (пакетирование), разработанное Лео Брейманом
- 1995 - алгоритм AdaBoost, первый практический алгоритм повышения, был представлен Йоавом Freund и Robert Schapire
- 1995 - алгоритм векторной машины поддержки soft-margin был опубликован Владимиром Вапником и Коринной Кортес. Он добавляет идею мягкого поля к алгоритму 1992 года Бозера, Нгуйона, Вапника и является алгоритмом, на который люди обычно ссылаются, когда говорят, что SVM
- 1995 - алгоритм Укконена для построения суффикса деревья
- 1996 - алгоритм Брууна, обобщенный на произвольные четные составные размеры
- 1996 - алгоритм Гровера, разработанный Лов К.Гровер
- 1996 - RIPEMD-160 разработан Хансом Доббертином и Барт Пренил
- 1997 - Мерсенн Твистер генератор псевдослучайных чисел, разработанный и
- 1998 - алгоритм PageRank был опубликован Ларри Пейджем
- 1998 - алгоритм rsync разработан Эндрю Триджеллом
- 1999 - алгоритм повышения градиента, разработанный Джеромом Х. Фридманом
- 1999 - алгоритм Ярроу разработан Брюсом Шнайером, Джоном Келси, и Нильс Фергюсон
2000-е годы
- 2000 - тематический поиск по гиперссылкам разработка алгоритма анализа гиперссылок под редакцией Джона Клейнберга
- 2001 - алгоритм цепи Лемпеля – Зива – Маркова для сжатия, разработанный Игорем Павловым
- 2001 - алгоритм Виолы – Джонса для Обнаружение лиц в реальном времени было разработано Полом Виолой и Майклом Джонсом.
- 2001 - DHT (распределенная хеш-таблица) изобретена несколькими людьми из академических кругов и прикладных систем
- 2001 - BitTorrent опубликована первая полностью децентрализованная одноранговая система распространения файлов
- 2002 - Тест на простоту AKS разработан Маниндрой Агравал, Нирадж Каял и Нитин Саксена
- 2002 - алгоритм Гирвана – Ньюмана для обнаружения сообществ в сложных системах
- 2002 - синтаксический анализатор Packrat разработан для создания синтаксического анализатора, который анализирует PEG (Parsing expression grammar) с линейным синтаксическим анализом времени, разработанный
- 2009 г. - Биткойн первая децентрализованная криптовалютная система без доверия опубликовано
2010-е годы
- 2013 - протокол консенсуса Raft pub Автор и Джон Остерхаут
- 2015 - YOLO («Ты смотришь один раз») - эффективный алгоритм распознавания объектов в реальном времени, впервые описанный и др.
Ссылки
Последняя правка сделана 2021-06-11 12:46:06
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
