|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
О быстром алгоритме вычисления преобразования Фурьедипломная работа (Специалист)
- Научный руководитель: Нестеренко Ю.В.
- Автор: Костромин Александр Николаевич
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2021
- Аннотация: Быстрые алгоритмы вычисления преобразования Фурье, возникли в связи с проблемами ускорения обработки и передачи информации, но оказались весьма полезными в связи с созданием более эффективных алгоритмов умножения больших натуральных чисел и многочленов - важной проблеме в теории алгоритмов, теории чисел и алгебре. В 1962г. А.А. Карацуба предложил быстрый рекурсивный алгоритм умножения целых чисел. В 1965г. Кули и Тьюки опубликовали быстрый алгоритм вычисления комплексного преобразования Фурье и, хотя речь в этой работе не шла об умножении целых чисел, все последующие ускорения алгоритмов умножения были связаны с использованием различных вариантов быстрого преобразования Фурье. Две упомянутые работы имели прорывной характер и породили большое направление исследований по быстрым алгоритмам умножения. Подробный обзор развития этой области можно найти в обстоятельной работе С.Б. Гашкова и И.С. Сергеева. Отметим здесь лишь основные достижения, опубликованные в работах А.Шёнхаге и Ф.Штрассен (1971), М.Фюрера (2007). В 2008г. А. Де +3 соавтора, нашли алгоритм такой же сложности, как и у М.Фюрера, но использующий вместо поля комплексных чисел некоторое конечное кольцо. Наконец, в 2019г. в работе Д. Харви и ван дер Хоевена, был опубликован алгоритм умножения целых чисел, имеющий сложность O(NlnN) арифметических операций. Существование такого алгоритма было предсказано ещё А.Шёнхаге и Ф.Штрассеном. По-видимому это окончательный результат. В дипломной работе А.Н. Костромина описывается и обосновывается быстрый алгоритм вычисления преобразования Фурье над конечными кольцами со специальными свойствами, не использующий рекурсию. В чём то он похож на алгоритм Кули и Тьюки.
- Добавил в систему: Нестеренко Юрий Валентинович