Быстрое преобразование Фурье. Часть 1.

Быстрое преобразование Фурье.
Семинар 5 мая 2017 года. Докладчик: Алексей Данилюк.

0:20 основная идея FFT
4:35 комплексные числа; корни из 1
6:00 определение FFT
9:10 как считать FFT (алгоритм)
16:15 псевдокод FFT
24:13 оптимизации
38:43 оптимизированный псевдокод FFT
1:04:20 обратное преобразование Фурье
1:16:00 FFT в поле вычетов по простому модулю (NTT)
1:19:50 введение в ТЧ (теорию чисел); корни из 1
1:30:20 хорошие простые модули для NTT

[orla]

Не знаю куда писать, напишу под самым свежим видео. Очень хочется послушать решение Huawei Codecraft. Кажется, ваши студенты хорошо там выступили.