Изменения
Нет описания правки
# Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица?
# Когда двойственный к графовому матроид является графовым?
# Задан многочлен $A(x) = \sum\limits_{i=0}^n a_i x^i$ степени $n$ и точка $x_0$. Найдите представление $A(x)$ в виде $A(x) = q(x) \cdot (x - x_0) + r$, где $r$~--- число, а $q(x) $~--- многочлен степени $n-1$ за время $O(n)$.
# Предложите способ восстановления коэффициентов многочлена $A(x) = \sum\limits_{i=0}^{n-1} a_i x^i$ по заданным $n$ парам $\{(x_0, y_0), (x_1, y_1), \ldots (x_{n-1}, y_{n-1})\}$, где $y_i = A(x_i)$ и все $x_i$ различны, за $O(n^2)$.
# Докажите, что $DFT(DFT(\langle a_0, a_1, \ldots, a_{n-1} \rangle)) = n \cdot \langle a_0, a_{n-1}, a_{n-2}, \ldots, a_1 \rangle$
# Опишите модификацию алгоритма FFT для случая, когда размер массива является степенью 3 ($n = 3^k$). Какое будет рекуррентное соотношение для времени работы и само время работы в таком случае? Указание: как разделить на 3 многочлена и как скомпоновать результаты?
# Для заданных $n$ различных чисел $x_0, x_1, \ldots, x_{n-1}$ постройте многочлен $n$ степени, который имеет корни только в заданных $n$ точках за $O(n \log^2 n)$
# Пусть мы хотим считать преобразование Фурье не в поле комплексных чисел, а в поле остатков по модулю $p$, где $p$~--- простое число. Для каких $p$ такое преобразование можно сделать, как найти соответствующий корень из единицы $\omega_n$, и как изменится сам алгоритм?
# Даны две строки $p$ и $t$ из символов 0 и 1 ($|p| \le |t|$). Найдите расстояние Хэмминга между $p$ и всеми подстроками $t[i..i+|p|-1]$ длины $|p|$ за $O(n \log n)$.
# Для всех чисел $n$ от 1 до $N$ посчитайте количество представлений вида $n = a\cdot b + c \cdot d$, $a, b, c, d > 0$ за $O(n \log n)$.
# Задан многочлен $A(x) = \sum\limits_{i=0}^{2^k-1} a_i x^i, a_0 \neq 0$. Найдите такой многочлен $B(x)$, что $A(x) \times B(x) \equiv 1 \bmod (x^{2^k})$ за $O(n \log^2 n$ [hard].
# То же самое за $O(n \log n)$ [very hard].
</wikitex>
