FFT (8-е апреля 2019)

1. Разминка: число счастливых билетов из 2n цифр
1. P(x) = (x⁰ + x¹ + ... + x^d)ⁿ, ответ = сумма квадратов коэффициентов P(x)
2. N = dn ⇒ оно возведение в степень работает за O(Mul(N)) = O(NlogN)


2. Разделяй и властвуй для интерполяции
1. Ньютон: (x₁...x_n-1, y₁...y_n-1) → P(x) → P(x) + Q(x)/Q(x_n)*(y_n - P(x_n)), где Q(x) = (x-x₁)(x-x₂)...(x-x_n-1)
2. Разделяй и властвуй: (x₁...x_n/2, y₁...y_n/2) → P(x) → P(x) + Q(x)*S(x), (x-x₁)(x-x₂)...(x-x_n/2), а
   значения S(x) в точках x_n/2+1...x_n вычисляются как S(x_i) = (y_i - P(x_i)) / Q(x_i)


3. Закрепление: перевод числа из 2-ичной системы в 10-ичную
1. Разделяй и властвуй: F(a₁...a_n) = F(a₁...a_n/2) + 2^n/1F(a_n/2+1...a_n)


4. CRC-32
1. Один из вариантов хеширования последовательности бит a₀, a₁, ... a_n-1 - остаток от деления многочлена A(x)*x^k на G(x),
где G(x) - специальный многочлен, и k = deg G.
2. В CRC-32-IEEE-802.3 (используется в v.42, mpeg-2, png, POSIX cksum) k = 32, G(x) = 0xEDB88320 (32 бита).
3. Вычисление взятия по модуля одним проходом за O(n) при w ≥ k


5. Коды Рида-Соломона
1. Пример 1: передать 1 бит по каналу, где любой 1 бит может быть заменён. 00, 11 - плохой код. 000, 111 - хороший.
2. Пример 2: только проверка на корректность, без исправления ошибок. Передать xor.
3. Пример 3: передать n бит. Код повторять три раза. Код частичные суммы.
4. Критерий того, что при k ошибках всё можно однозначно декодировать: расстояния Хэмминга не менее 2k+1.
5. Задача: хотим передать n слов из поля F_q, q > n, не более k ошибок.
6. Какие бывают q? Чтобы было поле, q = pⁿ. Поля простого размера - остатки по модулю. По pⁿ - нужно найти неприводимый многочлен степени n над F_p.
7. Входные данные - многочлен. Алгоритм кодирования - вычисление значений многочлена в произвольных n+2k точках x_i.
8. Корректность кодирования: у A₁-A₂ не более n-1 корней ⇒ у A₁ и A₂ значения хотя бы в 2k+1 точке различны
9. Проверка наличия ошибок - интерполяция имеет степень не более n-1.
10. Исправление ошибок: A(x) - входные данные, A'(x) - интерполяция переданного, E(x) = (x-x_e1)...(x-x_ek) - многочлен ошибок. У B(x) = A(x)E(x) и A'(x)E(x) совпадают значения во всех n+2k точках. СЛАУ: неизвестные - коэффициенты B и E, каждая из n+2k точек даёт уравнение.
11. Асимптотика декодирования. Гаусс O((n+k)³). Бэрликэмп-Мэсси O((n+k)²).

Автоматы (8-е апреля 2019)

1. Определение детерминированного и недетерминированного.
2. Детерминизация за O(2ⁿΣ)
3. Минимизация за O(n²Σ) (прообраз алгоритма Хопкрофта)