Семинар 6. Быстрое преобразование Фурье
Суббота, 19 октября 2019
НГУ, ауд. 2128, НГУ, новый корпус
Перемножение многочленов. Алгоритм Карацуба. Представления многочлена: набор коэффициентов и набор значений. Свёртка. Перевод: схема Горнера, интерполяция Ньютона. Комплексные корни из единицы, их свойства. Дискретное преобразование Фурье, его матрица. Обратное преобразование. Быстрое преобразование Фурье, рекурсивная реализация. Оценка времени работы. Итеративный FFT; Bit-Reverse-Copy и Butterfly-преобразование.
Видео для студентов заочного отделения: https://my.compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4270/