|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Об алгоритмах быстрого умножения целых чиселкурсовая работа (Специалист)
- Научный руководитель: Нестеренко Юрий Валентинович
- Автор: Костромин Александр Николаевич
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Кафедра: Кафедра теории чисел
- Год защиты: 2019
- Курс: 4
- Аннотация: Для умножения двух целых чисел, записываемых в двоичной системе счисления n цифрами, требуется согласно школьному алгоритму n^2 попарных умножений этих цифр. В середине прошлого века А.А. Карацуба предложил алгоритм, требующий всего лишь O(n^{\log_2 3}) таких умножений. Ряд авторов пытались уменьшить постоянную в показателе степени этой оценки. Существенно снизить оценку удалось Шёнхаге и Штрассену, которые использовали быстрый алгоритм вычисления дискретного преобразования Фурье. Их алгоритм имеет оценку сложности O(n\log n\log\log n) арифметических операций. В 2007 и 2008 годах появились статья М.Фюрера и ещё одна статья четырёх французских авторов, где оценка Шёнхаге - Штрассена была ещё улучшена. А именно, второй логарифм от n в этих работах был заменён монотонной функцией растущей медленнее любой итерации логарифма. Наконец уже в 2019 г. появилась в архиве ещё одна работа, где указывается, что автор полностью решил давно стоящую и известную проблему найти алгоритм, сложность которого оценивается величиной O(n\log n). Впрочем эта работа пока не проверена. Курсовая работа А. Костромина посвящена анализу алгоритмов, предложенных в статьях Фюрера и четырёх французов.
- Добавил в систему: Нестеренко Юрий Валентинович