Фурье (5 мая 2016)

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