|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Преобразование Фурье многочленов от нескольких переменныхкурсовая работа (Специалист)
- Научный руководитель: Нестеренко Юрий Валентинович
- Автор: Костромин Александр Николаевич
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Кафедра: Кафедра теории чисел
- Год защиты: 2020
- Курс: 5
- Аннотация: Курсовая работа А. Костромина по существу связана с быстрыми алгоритмами умножения целых чисел. Первый такой алгоритм был предложен в 1962г. А.А. Карацубой. При умножении двух целых n – разрядных чисел, этот алгоритм требует O(n^(1,58…)) операций умножения. Для сравнения отметим, что классический алгоритм умножения столбиком использует O(n^2) операций умножения цифр. Алгоритм Карацубы несколько раз уточнялся. В 1971г. Шёнхаге и Штрассен предложили алгоритм, требующий O(n ln n lnln n) операций умножения для n-разрядных чисел. В 2007г. Фюрер и ряд других специалистов предложили алгоритмы, в оценках сложности которых второй логарифм был заменён функций, растущей медленнее любой итерации логарифма. И, наконец, в 2019г. Харви и ван дер Хувен предложили алгоритмы умножения со сложностью O(n ln n). Предполагается, что асимптотические оценки такого рода неулучшаемы. Эти алгоритмы основаны на вычислениях с многочленами от многих переменных. А.Костромину была поставлена задача разработать алгоритм умножения сложности O(n ln n), основанные на быстром преобразовании Фурье для многочленов от нескольких переменных, не использующие рекурсию. Эта задача сложна и, к сожалению, полностью решена не была. Тем не менее был найден ряд перспективных идей, которые будут предметом изучения в дальнейшей работе.
- Добавил в систему: Нестеренко Юрий Валентинович