Алгоритмы и структуры данных 8. FFT. Многочлены. Multipoint evaluation

Алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики Дата лекции: Лектор: Степанов Илья Даниилович Монтажер: Голицын Сергей Оператор: Жулябина Ира // звука не было с 00:54:57 до 00:56:13 00:00:00 — начало; напоминание задачи с прошлой лекции про строку, ее решение 00:11:00 — асимптотика 00:14:15 — постановка задачи 2 — найти обратный многочлен по модулю x^M 00:16:00 — решение задачи 00:28:00 — асимптотика 00:33:46 — постановка задачи 3 — деление многочленов с остатком 00:35:09 — решение 00:36:00 — утверждение о мультипликативности функции reverse 00:42:20 — продолжение решения задачи 3 00:50:25 — асимптотика 00:52:40 — постановка задачи 4 — multipoint evaluation 00:53:45 — теорема (Безу): P(b) = значение остатка при делении P(x) на (x - b) 00:55:54 — решение задачи 01:00:36 — асимптотика 01:09:26 — постановка задачи 5 — найти a_n в линейной рекурренте 01:13:07 — решение