-
Period: to
«Счётная мудрость» древнерусский учебник арифметики.
Историки датируют 1691 годом один из списков древнерусского учебника арифметики, известного как «Счётная мудрость». Это сочинение известно во многих вариантах и восходит к ещё более древним рукописям XVI в. По ним можно проследить, как знание арабских цифр и правил действий с ними постепенно распространялось на Руси. -
Period: to
Определение алгоритма в Большой Советской Энциклопедии, издание 1926 года.
Слово «алгорифм» можно найти и в популярном дореволюционном Энциклопедическом словаре братьев Гранат, и в первом издании Большой Советской Энциклопедии (БСЭ), изданном в 1926 г. И там, и там оно трактуется одинаково: как правило, по которому выполняется то или иное из четырёх арифметических действий в десятичной системе счисления. -
Period: to
Алгоритм Левинсона
Алгоритм Левинсона-Дурбина был предложен сначала Норманом Левинсоном в 1947 году, улучшен Джеймсом Дурбином в 1960 году. Это алгоритм в линейной алгебре для рекурсивного вычисления решения уравнения с матрицей Теплица. -
Period: to
Появление теории быстрых алгоритмов
Область быстрые алгоритмы появилась в 1960 году, когда был найден первый быстрый метод — метод умножения Карацубы. Впоследствии метод Карацубы был обобщён до парадигмы «Разделяй и властвуй» -
Period: to
Метод Штрассена
1969 – Штрассен.
Создание быстрого алгоритма перемножения матриц.
Первый алгоритм быстрого умножения больших матриц был разработан Фолькером Штрассеном в 1969 г. В основе алгоритма лежит рекурсивное разбиение матриц на блоки 2Х2. Штрассен доказал, что матрицы 2Х2 можно некоммутативно перемножить с помощью семи умножений, поэтому на каждом этапе рекурсии выполняется семь умножений вместо восьми. В результате асимптотическая сложность этого алгоритма уменьшилась. -
Period: to
Алгоритм Агарвала-Кули
Для малых длин блоков быстрые алгоритмы свёрток были впервые построены Агарвалом и Кули в 1977 году. -
Period: to
Алгоритм Пана
В 1978 Пан предложил свой метод умножения матриц. -
Period: to
Алгоритм Бини
В 1979 группа итальянских учёных во главе с Бини разработала алгоритм умножения матриц с использованием тензоров. -
Period: to
Алгоритмы Шёнхаге
В 1981 Шёнхаге представил метод, работающий со скоростью Θ(n2.695). Оценка получена с помощью подхода, названного частичным матричным умножением. -
Period: to
Книга «Введение в алгоритмы»
1991 – Корман, Лейзерсон и Райвест – «Введение в алгоритмы» - главная книга по алгоритмам во всем мире. Первое издание книги вышло в 1990 году и было выпущено издательствами McGraw-Hill и MIT Press. На русском языке книгу издало издательство МЦНМО. Второе издание книги было выпущено в 2001 году и издано на русском языке издательством «Вильямс» в 2005 году.
Третье издание было выпущено в 2009 году, его перевод на русский язык в 2013 году в издательстве «Вильямс». -
Period: to
Алгоритм Копперсмита — Винограда
В 1990 Копперсмит и Виноград опубликовали алгоритм, который в модификации Вильямс Василевской 2011 года умножает матрицы со скоростью O(n2.3727). Этот алгоритм использует идеи, схожие с алгоритмом Штрассена. На сегодняшний день модификации алгоритма Копперсмита-Винограда являются наиболее асимптотически быстрыми. Но тот факт, что полученные улучшения ничтожны. Алгоритм Копперсмита-Винограда эффективен только на матрицах астрономического размера и на практике применяться не может.