Интернет магазин китайских планшетных компьютеров

Компьютеры - Быстрые алгоритмы - История вопроса

Первые задачи по битовой сложности вычисления были поставлены в 50-х годах 20 века А.Н. Колмогоровым, который при этом ссылался на работы Клода Шеннона и Норберта Винера, возбудившие его интерес к науке, впоследствии названной информатикой.

Область быстрые алгоритмы появилась в 1960 году, когда был найден первый быстрый метод — метод умножения Карацубы. Впоследствии метод Карацубы был назван «Разделяй и властвуй», другими названия этого метода, используемые в литературе, это метод двоичного разбиения, двоичный поиск, метод бисекции и др.

Метод Карацубы имел много непосредственных обобщений и приложений в других областях вычислительной математики. В их числе метод Тоома-Кука, метод умножения Шёнхаге — Штрассена, алгоритм Штрассена для быстрого умножения матриц, Быстрое преобразование Фурье, метод БВЕ для вычисления простейших и высших трансцендентных функций. и т. д. Некоторые старые методы становятся быстрыми вычислительными методами, если использовать в них один из быстрых алгоритмов умножения, например, метод Ньютона для вычисления элементарных алгебраических функций и АГС метод Гаусса для вычисления простейших трансцендентных функций.