Изменения
Нет описания правки
# Образуют ли паросочетания в полном графе семейство независимых множеств некоторого матроида?
# Рассмотрим кратчайшие пути из $s$ в $t$ в неориентированном невзвешенном графе. Назовем множество ребер независимым, если оно лежит на некотором кратчайшем пути. Образует ли эта конструкция семейство независимых множеств некоторого матроида?
# Верно ли, что в графовом матроиде любая база пересекается с любым циклом?
# Верно ли, что в матричном матроиде любая база пересекается с любым циклом?
# Верно ли, что в любом матроиде любая база пересекается с любым циклом?
# Обратная аксиома баз. Докажите, что если $B_1$ и $B_2$ - базы матроида, то для любого $y \in B_2 \setminus B_1$ найдется $x \in B_1 \setminus B_2$, такой что $B_1 \setminus x \cup y$ тоже база.
# Двойственный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M^*$ следующую констркуцию: $M^* = \langle X, \{A | \exists B $ - база $M, A \cap B = \varnothing\}\rangle$. Докажите, что $M^*$ является матроидом.
# Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом?
# Урезанный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M|_k$ следующую констркуцию: $M|_k = \langle X, \{A | A \in I, |A| \le k \}\rangle$. Докажите, что $M|_k$ является матроидом.
# Будем называть предматроидом пару $\langle X, I \rangle$, для которой выполнены аксимомы нетривиальности ($\varnothing \in I$) и наследования независимости ($A \subset B$, $B \in I$, тогда $A \in I$). Пусть в предматроиде для любой весовой функции верно работает жадный алгоритм Радо-Эдмондса. Докажите, что такой предматроид является матроидом.
# Пусть $M$ - предматроид. Как и в матроиде будем называть базой множества максимальное подмножество из $I$. Докажите, что если для каждого множества $A$ все его базы равномощны, то $M$ - матроид.
# Будем называть два элемента $x$ и $y$ матроида параллельными, если пара $\{x, y\}$ образует цикл. Докажите, что если $A$ независимо $x \in A$, а $x$ и $y$ параллельны, то $A\setminus x\cup y$ также независимо.
# Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $X = \{x_1, x_2, \ldots, x_n\}$. Пусть $Y = \left\{x_k \,|\, rank(\{x_1, \ldots, x_{k-1}, x_k\}) > rank(\{x_1, \ldots, x_{k-1}\})\right\}$. Докажите, что $Y$ независимо.
# Какие универсальные матроиды являются матричными?
# Докажите, что матроид Вамоса не является представимым ни над каким полем.
# Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица?
# Когда двойственный к графовому матроид является графовым?
# Задан многочлен $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 a_i x^i$ по заданным $n+1$ парам $\{(x_0, y_0), (x_1, y_1), \ldots (x_n, y_n)\}$, где $y_i = A(x_i)$ и все $x_i$ различны, за $O(n^2)$.
# Пусть заданы значения многочлена $A(x)$ степени $n$ для всех $x = 0, 1, \ldots, n$. Для заданного числа $t > n$ посчитайте $A(t)$ за $O(n)$.
# Докажите, что $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 для случая, когда размер массива является степенью тройки ($n = 3^k$). Какое будет рекуррентное соотношение для времени работы и само время работы в таком случае? Указание: как разделить на 3 многочлена и как скомпоновать результаты?
# Как за один вызов алгоритма FFT посчитать преобразование Фурье 2 многочленов $A$ и $B$ с вещественными коэффициентами? Указание: нужно объединить 2 многочлена степени $n$ в один многочлен $C$ степени $n$ с комплексными коэффициентами и восстановить $DFT(A)$ и $DFT(B)$ по $DFT(C)$.
# Для заданных $n$ различных чисел $x_0, x_1, \ldots, x_{n-1}$ постройте многочлен $n$-й степени, который имеет корни только в заданных $n$ точках за $O(n \log^2 n)$
# Пусть мы хотим считать преобразование Фурье не в поле комплексных чисел, а в поле остатков по модулю $p$, где $p$~--- простое число. Для каких $p$ такое преобразование можно сделать, как найти соответствующий корень $n$-й степени из единицы $\omega_n$, и как изменится сам алгоритм?
# Даны 2 числа в десятичной системе счисления, каждое состоит из $n$ десятичных цифр. Найдите их произведение за $O(n \log n)$.
# Даны две строки $p$ и $t$ из символов 0 и 1 ($|p| \le |t|$). Найдите расстояние Хэмминга между $p$ и всеми подстроками $t[i..i+|p|-1]$ длины $|p|$ за $O(n \log n)$.
# Задан многочлен $A(x) = \sum\limits_{i=0}^{n - 1} a_i x^i, a_0 \neq 0$. Найдите такой многочлен $B(x)$, что $A(x) \times B(x) = 1 + x^n Q(x)$ для какого-то многочлена $Q(x)$ за $O(n \log^2 n)$.
# То же самое за $O(n \log n)$.
# Каков критерий существования решения и алгоритм восстановления числа в КТО, если убрать требование взаимной простоты модулей $m_1$ и $m_2$?
# Чему равна сумма всех чисел от 0 до $n-1$, взаимнопростых с $n$?
# Найдите $\frac{n!}{p^k} \mod p$, где $k$ - максимальная степень вхождения простого $p$ в $n!$, за $O(p \log n)$
# Докажите, что $gcd$ последовательных чисел Фибоначчи равен 1.
# Докажите, что $gcd(F_n, F_m) = F_{gcd(n, m)}$.
# Для заданных $a$ и нечетного простого $p$, проверьте, что существует $x$: $x^2 \equiv a \mod p$ за $O(\log p)$
# Решите задачу дискретного логарифма для простого модуля $p$ вида $2^k + 1$ за $O(\mathop{poly}(k))$.
# Докажите лемму о паросочетании в графе замен (формулировка тут: [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D0%BF%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B8_%D0%B2_%D0%B3%D1%80%D0%B0%D1%84%D0%B5_%D0%B7%D0%B0%D0%BC%D0%B5%D0%BD], доказательство неправильное - неверный индукционный переход)
# Рассмотрим два матроида $M_1$ и $M_2$. Как связаны максимальное независимое множество пересечения $M_1 \cap M_2$ и база $M_1 \cup M_2^*$? ($M_2^*$ - матроид, двойственный $M_2$)
# Докажите теорему Радо: пусть $M$ - матроид с ранговой функцией $r$, $X = X_1 \cup X_2 \cup ...\cup X_k$, причем все $X_i$ попарно не пересекаются. Будем называть независимой системой представителей независимое множество $A$, такое что $|A \cap X_i| \le 1$. Пусть $A_{max}$ - максимальная по мощности независимая система представителей. Тогда $|A_{max}|=\min_{Z\subset \{1,..,k\}}(r(\cup_{i\in Z} X_i)+k-|Z|)$.
# Предложите алгоритм построения максимальной независимой системы представителей.
# Докажите, что длина кратчайшего пути из $S$ в $T$ в алгоритме построения базы пересечения матроидов не убывает.
# Докажите, что число различных длин кратчайшего пути из $S$ в $T$, которые встречаются в алгоритме построения базы пересечения матроидов, есть $O(\sqrt n)$.
# Докажите, что сумма длин кратчайших пути из $S$ в $T$, которые встречаются в алгоритме построения базы пересечения матроидов, есть $O(n \log n)$.
# Игра Шеннона. Рассмотрим игру на связном графе с множеством ребер $E$. Играют два игрока, cut и link, первым ходит cut. Игроки по очереди добавляют себе ребра, не использованные на предыдущих ходах. В конце игры link выигрывает, если по его ребрам можно дойти от любой вершины до любой. Докажите, что link выигрывает при оптимальной игре, если и только если в графе существует два непересекающихся остовных дерева.
# Игра Шеннона на произвольном матроиде. Рассмотрим игру на матроиде $M$. Играют два игрока, cut и link, первым ходит cut. Игроки по очереди выбирают себе элементы носителя, не использованные на предыдущих ходах. В конце игры link выигрывает, если его множество содержит базу матроида. Докажите, что link выигрывает при оптимальной игре, если и только если в графе существует две непересекающихся базы.
# Пусть $M$ - невырожденная квадратная матрица над вещественными числами. Докажите, что для любого множества строк $R$ найдется множество столбцов той же мощности $C$, что миноры $R\times C$ и $\overline{R}\times \overline{C}$ - ненулевые (как $\overline T$ обозначено множество строк/столбцов, не входящих в $T$).
# Задан двудольный граф, каждая вершина имеет вес. Требуется выбрать паросочетание, чтобы суммарный вес покрытых вершин был максимален. Решите эту задачу, не используя сведение к обычной задаче о назначениях.
</wikitex>
