Фурье (5 мая 2016)
- Известно с лекции
- Общая схема (экстерполяция, O(n), интерполяция)
- Прямое Фурье
- Написан работающий рекурсивный код Фурье
- Обратное Фурье: сперва формулировка, затем доказательство
- Можно заменить поле на остатки по простому модулю P : P-1 близко к степени двойки.
- Задачи на Фурье
- Найти циклический сдвиг, минимизирующий скалярное произведение
- Поиск циклического сдвига, максимизирующего количество совпавших символов у двух строк (алфавит = ACGT)
- Поиск шаблона с "?" в строке с "?"
- Поиск подотрезка в массиве c минимизицией квадратичного отклонения
- Поиск подматрицы в матрице c минимизицией квадратичного отклонения
- Улучшение Фурье
- Два вещественных в одном комплексном: zi = xi + iyi, fxi = (fzi + fzn-i)/2
- Убираем рекурсию. Разворот битовой записи числа.
- Длинная арифметика
- Связь Фурье с длинной арифметикой. Выбираем систему счисления: base * len2 < 1018, len = 220 > 106 ⇒ base < 106 ⇒ base = 104 или 105
- Повышение точности (вместо 1 Фурье, 4 Фурье)
- Умножение трёх длинных чисел (a * b * c)
- Хранение вещественных чисел
- Вычисления по модулю (RSA). Деление и остаток за O(nlog2n).
- Перевод из одной системы счисления в другую методом разделяй и властвуй за O(nlog2n).