Редактирование: Список заданий по ДМ 2к 2016 осень

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 14: Строка 14:
 
# Харари 2.20
 
# Харари 2.20
 
# Харари 2.22
 
# Харари 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))$.
 
# Докажите лемму о паросочетании в графе замен (формулировка тут: [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>
 
</wikitex>

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)