Список заданий по ДМ 2к 2016 осень

2016-11-28T20:23:37Z

94.25.229.159:

<wikitex>
# Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.
# Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл.
# Будем называть ''согласованным циклом'' в графе класс эквивалентности циклических путей относительно циклического сдвига. При этом циклический путь не должен проходить два раза по одному ребру в разных направлениях. Докажите, что в графе есть согласованный цикл тогда и только тогда когда там есть цикл.
# Петя придумал отношение средней связности: $u$ средне связана с $v$, если из $u$ достижима $v$ или из $v$ достижима $u$. Является ли это отношение отношением эквивалентности?
# Пусть граф $G$ - объединение двух различных простых путей из $u$ в $v$. Докажите, что в $G$ есть цикл.
# Харари 2.3
# Харари 2.5
# Харари 2.9
# Харари 2.13
# Харари 2.15
# Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
# Харари 2.16
# Харари 2.20
# Харари 2.22
# Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
# Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
# Какое максимальное число точек сочленения может быть в графе с $n$ вершинами?
# При каких соотношениях $a$, $b$, $n$, $m$, $k$ существует граф с $a$ точками сочленения, $b$ мостами, $n$ вершинами, $m$ рёбрами, $k$ компонентами связности?
# Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это рефлексивно-транзитивное замыкание $R$.
# Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
# Харари 4.2
# Харари 4.3
# Харари 2.29
# Харари 2.31
# Харари 2.32
# Харари 2.33
# Харари 2.35
# Харари 2.36
# Харари 7.2
# Харари 7.4
# Харари 7.5
# Харари 7.7
# Харари 7.9
# Харари 7.14
# Харари 7.17
# Харари 7.18
# Харари 3.2
# Наименьшее число вершин в кубическом графе, имеющем мост, равно 10. (Харари 3.3)
# Харари 3.4
# Харари 3.5
# Харари 3.6
# Харари 3.7
# Харари 3.9
# Посчитать хроматический многочлен цикла $C_n$
# Посчитать хроматический многочлен колеса $C_n + K_1$.
# Посчитать полного двудольного графа $K_{n,m}$.
# Харари 12.2
# Харари 12.3
# Харари 12.4
# Харари 12.5
# Харари 12.6
# Харари 12.12
# Доказать формулу Зыкова для хроматического многочлена графа $G$: $P_G(x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}$, где $pt(G,i)$ — число способов разбить вершины $G$ на $i$ независимых множеств.
# Доказать формулу Уитни: пусть $G$ - обыкновенный $(n, m)$ - граф. Тогда коэффициент при $x^i$, где $1\le i\le n$ в хроматическом многочлене $P_G(x)$ равен $\sum \limits_{j=0}^{m}{(-1)^jN(i, j)}$, где $N(i, j)$ - число остовных подграфов графа $G$, имеющих $i$ компонент связности и $j$ рёбер.
# Харари 11.1
# Харари 11.2
# Харари 11.3
# Харари 11.7
# Харари 11.8
# Харари 11.9
# Харари 11.10
# Харари 11.14
# Харари 11.15
# Харари 11.25
# Харари 9.1
# Харари 9.3
# Харари 9.4
# Харари 9.5
# Харари 9.8
# Харари 9.9
# Харари 9.13
# Харари 8.1
# Харари 8.2
# Харари 8.3
# Харари 8.8
# Харари 8.9
# Харари 8.10
# Харари 8.11
# Матроид с выкинутым элементом. Пусть $M$ - матроид. Обозначим как $M\setminus x$ матроид, где из носителя выкинут элемент $x$. Множества, не содержавшие $x$, остаются независимыми. Формально, если $M = \langle X, I\rangle$, то $M\setminus x = \langle X \setminus x, \{A | A \in I, x \not\in A\}\rangle$. Докажите, что для любых $M$ и $x$ получившаяся конструкция $M\setminus x$ является матроидом.
# Матроид, стянутый по элементу. Пусть $M$ - матроид. Обозначим как $M/x$ матроид, где из носителя выкинут элемент $x$. Независимыми объявляются множества, которые ранее содержали $x$, после удаления из них этого элемента. Формально, если $M = \langle X, I\rangle$, то $M/x = \langle X \setminus x, \{A \setminus x | A \in I, x \in A\}\rangle$. Докажите, что для любых $M$ и $x$, таких что $\{x\}\in I$ получившаяся конструкция $M/x$ является матроидом.
# Прямая сумма матроидов. Пусть $M_1 = \langle X_1, I_1\rangle$ и $M_2=\langle X_2, I_2\rangle$ - матроиды с непересекающимися носителями ($X_1 \cap X_2 = \varnothing$). Обозначим как $M_1+M_2$ следующую конструкцию: $M_1 + M_2 = \langle X_1 \cup X_2, I = \{A \cup B|A \in I_1, B \in I_2\}$. Докажите, что сумма матроидов является матроидом.
# Разноцветные множества. Пусть $X$ - множество элементов, каждый из которых раскрашен в некоторый цвет. Будем называть независимыми множества, в которых все элементы разного цвета. Докажите, что эта конструкция является матроидом. Используйте определение матроида.
# Представьте конструкцию из предыдущего примера в виде прямой суммы универсальных матроидов.
# Является ли алгоритм Прима вариантом алгоритма Радо-Эдмондса?
# Является ли венгерский алгоритм вариантом алгоритма Радо-Эдмондса?
# Образуют ли паросочетания в полном графе семейство независимых множеств некоторого матроида?
# Рассмотрим кратчайшие пути из $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))$.
</wikitex>

Викиконспекты - Вклад участника [ru]

Список заданий по ДМ 2к 2016 осень