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

1. Разминка
1. Даны CRC-32(A) и CRC-32(B). Найдите CRC-32(A XOR B)
2. Зная CRC-32(A), посчитайте за O(1) CRC-32(A1)
3. Умножение многочленов над кольцом Z/mZ, m - простое вида x*2^s+1, n < 2^s.
4. Рид-Соломон. Где же ответ? B = A*E, A'*E, неизвестные - коэффициенты B и E


2. Сверхбыстрая линейная рекуррента
1. Фибоначчи за O(logn): возведение матрицы в степень
2. Линейная рекурренты длины k за O(k³logn): возведение матрицы в степень
3. Линейная рекурренты длины k за O(klogklogn): xⁿ mod S(x)

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

1. Эквивалентность
1. Проверка эквивалентности двух автоматов: очередь пар разных состояний O((nk)²).
2. Проверка эквивалентности через минимизацию: попадут ли в один класс s₁ и s₂


2. Минимизация
1. Минимизация за O(nklogn): алгоритм Хопкрофта
2. Корректность, определение правых контекстов, определение минимального через правые контексты.
3. Минимизация через детерминизацию (Алгоритм Бржозовского): A_min = d(r(d(r(A)))) = drdrA. Подходит для недетрминированных. [paper].


3. Изоморфность
1. Изоморфность двух автоматов за O(nk)
2. Проверка изоморфности минимальному за O(nk)