Семинар 6. Быстрое преобразование Фурье
Алгоритмы и структуры данных, часть 1


Что: Семинар
Когда: Суббота, 20 октября 2018, 16:20–17:55
Где: НГУ, ауд. 2128

Описание

Перемножение многочленов. Алгоритм Карацуба. Представления многочлена: набор коэффициентов и набор значений. Свёртка. Перевод: схема Горнера, интерполяция Ньютона. Комплексные корни из единицы, их свойства. Дискретное преобразование Фурье, его матрица. Обратное преобразование. Быстрое преобразование Фурье, рекурсивная реализация. Оценка времени работы. Итеративный FFT; Bit-Reverse-Copy и Butterfly-преобразование.

Видео