Программирование основных алгоритмов 12. Суффиксный автомат (2). Быстрое преобразование Фурье (FFT)

Программирование основных алгоритмов. МФТИ, Физтех-школа прикладной математики и информатики.

Дата лекции: 26.04.2023
Лектор: Кулапин Артур Евгеньевич

00:00:00 - интро
00:00:04 - повторение с прошлой лекции
00:03:00 - алгоритм построения суфф автомата
00:20:23 - асимптотика
00:33:52 - быстрое преобразование Фурье (FFT): интуиция
00:38:51 - теорема о ряде Фурье
00:43:55 - задача FFT
00:50:49 - матрица преобразования
00:53:40 - схема Кули-Тьюки
00:58:34 - как перемножать многочлены
01:02:23 - вычислене обратной матрицы
01:10:13 - свёртка двух дискретных сигналов

Монтажер: Вашкевич Егор
Оператор: Вашкевич Егор