Список заданий по ДМ 2к 2020 осень - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:32:20Z

rollbackEdits.php mass rollback

185.100.85.24 в 04:33, 1 сентября 2022

2022-09-01T04:33:30Z

178.66.159.173 в 17:24, 21 декабря 2020

2020-12-21T17:24:53Z

77.234.215.133 в 09:10, 15 декабря 2020

2020-12-15T09:10:12Z

94.19.233.169 в 10:15, 3 декабря 2020

2020-12-03T10:15:48Z

188.170.77.146 в 19:41, 27 ноября 2020

2020-11-27T19:41:01Z

109.172.15.29 в 18:24, 27 ноября 2020

2020-11-27T18:24:58Z

77.234.215.133 в 08:52, 17 ноября 2020

2020-11-17T08:52:35Z

195.246.120.73 в 12:40, 15 ноября 2020

2020-11-15T12:40:48Z

109.172.15.29 в 15:34, 6 ноября 2020

2020-11-06T15:34:39Z

← Предыдущая		Версия 16:32, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	# Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее "постройте граф с $n$ вершинами, ..." означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.		# Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее "постройте граф с $n$ вершинами, ..." означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
	# Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$.		# Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$.

← Предыдущая		Версия 04:33, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	# Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее "постройте граф с $n$ вершинами, ..." означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.		# Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее "постройте граф с $n$ вершинами, ..." означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
	# Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$.		# Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$.

@@ Строка 199: / Строка 199: @@
 # Когда двойственный к графовому матроид является графовым для некоторого графа?
 # Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $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$ и $B$ и элемента $x \in A \subset B$ найдётся $y \in B \subset A$, так что $A \setminus x \cup y$ и $B \setminus y \cup x$ обе являются базами.
+# Сверхсильная теорема о базах. Докажите, что для любых двух различных баз $A$ и $B$ и элемента $x \in A \setminus B$ найдётся $y \in B \setminus A$, так что $A \setminus x \cup y$ и $B \setminus y \cup x$ обе являются базами.
 # Доказать, что $M^{**}=M$
 # Один студент считает, что xor двух циклов обязательно содержит цикл. Доказать или опровергнуть.

@@ Строка 191: / Строка 191: @@
 # Докажите, что если $A \subset B$, то $\langle A \rangle \subset \langle B \rangle$.
 # Докажите, что $\langle \langle A \rangle \rangle = \langle A \rangle$
-# Докажите, что если $p \not\in \langle A \rangle$, $q \in \langle A \cup p\rangle$, то $p \in \langle A \cup q \rangle$
+# Докажите, что если $q \not\in \langle A \rangle$, $q \in \langle A \cup p\rangle$, то $p \in \langle A \cup q \rangle$
 # Двойственный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M^*$ следующую конструкцию: $M^* = \langle X, \{A \,|\, \exists B $ - база $M,  A \cap B = \varnothing\}\rangle$. Докажите, что $M^*$ является матроидом.
 # Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом.
-# Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица?
+# Докажите, что двойственный к матричному матроид является матричным для некоторой матрицы. Как устроена его матрица?
-# Докажите, что двойственный матроид к $K_5$ не является графовым.
+# Докажите, что двойственный матроид к графовому на $K_5$ не является графовым ни для какого графа.
-# Докажите, что двойственный матроид к $K_{3,3}$ не является графовым.
+# Докажите, что двойственный матроид к графовому на $K_{3,3}$ не является графовым ни для какого графа.
-# Когда двойственный к графовому матроид является графовым?
+# Когда двойственный к графовому матроид является графовым для некоторого графа?
 # Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $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$ и $B$ и элемента $x \in A \subset B$ найдётся $y \in B \subset A$, так что $A \setminus x \cup y$ и $B \setminus y \cup x$ обе являются базами.
 # Доказать, что $M^{**}=M$
 # Один студент считает, что xor двух циклов обязательно содержит цикл. Доказать или опровергнуть.

← Предыдущая		Версия 10:15, 3 декабря 2020
Строка 186:		Строка 186:
	# Дайте альтернативное определение параллельных элементов на языке баз.		# Дайте альтернативное определение параллельных элементов на языке баз.
	# Докажите, что отношение "быть параллельными" является транзитивным.		# Докажите, что отношение "быть параллельными" является транзитивным.
		+	# Как устроено замыкание в графовом матроиде?
		+	# Как устроено замыкание в матричном матроиде?
		+	# Докажите, что если $A$ независимо, то для любого $p \in A$ выполнено $p \not\in \langle A \setminus p\rangle$.
		+	# Докажите, что если $A \subset B$, то $\langle A \rangle \subset \langle B \rangle$.
		+	# Докажите, что $\langle \langle A \rangle \rangle = \langle A \rangle$
		+	# Докажите, что если $p \not\in \langle A \rangle$, $q \in \langle A \cup p\rangle$, то $p \in \langle A \cup q \rangle$
		+	# Двойственный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M^$ следующую конструкцию: $M^ = \langle X, \{A \,\|\, \exists B $ - база $M, A \cap B = \varnothing\}\rangle$. Докажите, что $M^*$ является матроидом.
		+	# Циклы двойственного матроида называются коциклами. Докажите, что любая база пересекается с любым коциклом.
		+	# Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица?
		+	# Докажите, что двойственный матроид к $K_5$ не является графовым.
		+	# Докажите, что двойственный матроид к $K_{3,3}$ не является графовым.
		+	# Когда двойственный к графовому матроид является графовым?
		+	# Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $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$ и $B$ и элемента $x \in A \subset B$ найдётся $y \in B \subset A$, так что $A \setminus x \cup y$ и $B \setminus y \cup x$ обе являются базами.
		+	# Доказать, что $M^{**}=M$
		+	# Один студент считает, что xor двух циклов обязательно содержит цикл. Доказать или опровергнуть.

@@ Строка 158: / Строка 158: @@
 # Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ матожидание количества независимых множеств размера $(2 - \varepsilon) \log_2 n$ стремится к $\infty$.
 # Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ а.п.н. существует независимое множество размера $(2 - \varepsilon) \log_2 n$.
 # Постройте матроид с 4 элементами и 5 базами. Укажите множество циклов этого матроида.
 # Постройте матроид с 5 элементами и 12 базами.

← Предыдущая		Версия 18:24, 27 ноября 2020
Строка 158:		Строка 158:
	# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ матожидание количества независимых множеств размера $(2 - \varepsilon) \log_2 n$ стремится к $\infty$.		# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ матожидание количества независимых множеств размера $(2 - \varepsilon) \log_2 n$ стремится к $\infty$.
	# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ а.п.н. существует независимое множество размера $(2 - \varepsilon) \log_2 n$.		# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ а.п.н. существует независимое множество размера $(2 - \varepsilon) \log_2 n$.
		+	# Постройте матроид с 4 элементами и 5 базами. Укажите множество циклов этого матроида.
		+	# Постройте матроид с 5 элементами и 12 базами.
		+	# Матроид, стянутый по элементу. Пусть $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$ является матроидом.
		+	# Прямая сумма матроидов. Пусть $X$ и $Y$ - непересекающиеся множества, $M_1$ - матроид с носителем $X$ и $M_2$ - матроид с носителем $Y$. Построим новый матроид, назовем носителем объединение $X \cup Y$, независимыми объявим множества, которые являются объединением независимого из $M_1$ и независимого из $M_2$. Докажите, что прямая сумма матроидов является матридом.
		+	# Представьте разноцветный матроид в виде прямой суммы универсальных матроидов.
		+	# Является ли алгоритм Прима вариантом алгоритма Радо-Эдмондса?
		+	# Являются ли паросочетания в полном графе семейством независимых множеств некоторого матроида?
		+	# Рассмотрим кратчайшие пути из $s$ в $t$ в неориентированном невзвешенном графе. Назовем множество ребер независимым, если оно лежит на некотором кратчайшем пути. Образует ли эта конструкция семейство независимых множеств некоторого матроида?
		+	# Урезанный матроид. Пусть $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$ - матроид.
		+	# Для каких универсальных матроидов существует изоморфный ему матричный матроид?
		+	# Проекция матроида. Пусть $M = \langle X, I \rangle$ - матроид, $f : X \to Y$ - произвольная функция. Обратите внимание, что нет необходимости, чтобы $f$ была инъекцией или сюрьекцией. Построим конструкцию $f(M)$ как пару из носителя $Y$ и семейства множеств $f(I) = \{ f(A) \,\|\, A \in I\}$. Докажите, что $f(M)$ является матроидом.
		+	# Будем называть два элемента $x$ и $y$ матроида параллельными, если пара $\{x, y\}$ образует цикл. Докажите, что если $A$ независимо $x \in A$, а $x$ и $y$ параллельны, то $A\setminus x\cup y$ также независимо.
		+	# Дайте альтернативное определение параллельных элементов на языке баз.
		+	# Докажите, что отношение "быть параллельными" является транзитивным.

@@ Строка 146: / Строка 146: @@
 # Докажите, что если $p = \omega(n^{-1.5})$, то $G(n, p)$ а.п.н. содержит путь длины 2.
 # Пусть $p = o(n^{-\frac 23})$. Докажите, что а.п.н. $G(n, p)$ не содержит $K_4$.
-# Пусть $p = \o(\frac 1n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. не содержит цикл длины $k$.
+# Пусть $p = o(\frac 1n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. не содержит цикл длины $k$.
 # Пусть $p = \omega(\frac 1n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. содержит цикл длины $k$.
 # Пусть $p = o(\frac 1n)$. Покажите, что $G(n, p)$ а.п.н. не содержит циклов.

← Предыдущая		Версия 12:40, 15 ноября 2020
Строка 142:		Строка 142:
	# Пусть для некоторого свойства $A$ существует две функции $p_1(n)$ и $p_2(n)$, что для графа $G(n, p_1(n))$ свойство $A$ а.п.н. не выполняется, а для $G(n, p_2(n))$ свойство $A$ а.п.н. выполняется. Докажите, что существует функция $\tilde p(n)$, что для случайного графа $G(n, \tilde p(n))$ свойство $A$ выполняется с вероятностью, стремящейся к $\frac 12$.		# Пусть для некоторого свойства $A$ существует две функции $p_1(n)$ и $p_2(n)$, что для графа $G(n, p_1(n))$ свойство $A$ а.п.н. не выполняется, а для $G(n, p_2(n))$ свойство $A$ а.п.н. выполняется. Докажите, что существует функция $\tilde p(n)$, что для случайного графа $G(n, \tilde p(n))$ свойство $A$ выполняется с вероятностью, стремящейся к $\frac 12$.
	# Докажите, что $G(n, \frac {2\ln n}{n})$ а.п.н. не содержит вершин степени 0.		# Докажите, что $G(n, \frac {2\ln n}{n})$ а.п.н. не содержит вершин степени 0.
		+	# Рассмотрим модель случайного двудольного графа $G(n, n, p)$: из полного двудольного графа $K_{n,n}$ каждое ребро удаляется с вероятностью $1 - p$. Пусть $X$ -- количество изолированных вершин первой доли. Найдите $EX$ и $DX$.
		+	# Докажите, что если $p = o(n^{-1.5})$, то $G(n, p)$ а.п.н. является объединением компонент связности размера 1 и 2.
		+	# Докажите, что если $p = \omega(n^{-1.5})$, то $G(n, p)$ а.п.н. содержит путь длины 2.
		+	# Пусть $p = o(n^{-\frac 23})$. Докажите, что а.п.н. $G(n, p)$ не содержит $K_4$.
		+	# Пусть $p = \o(\frac 1n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. не содержит цикл длины $k$.
		+	# Пусть $p = \omega(\frac 1n)$ и $k$ -- константа. Покажите, что $G(n, p)$ а.п.н. содержит цикл длины $k$.
		+	# Пусть $p = o(\frac 1n)$. Покажите, что $G(n, p)$ а.п.н. не содержит циклов.
		+	# Покажите, что матожидание количества остовных деревьев у графа $G(n, \frac {\ln n}{2n})$ стремится к бесконечности.
		+	# Покажите, что матожидание количества остовных деревьев у графа $G(n, \frac {2\ln n}{n})$ стремится к бесконечности. Можно ли это считать доказательством а.п.н. связности графа $G(n, \frac {2\ln n}n)$?
		+	# Найдите матожидание количества индуцированных подграфов $G(n, \frac dn), d > 1$, которые являются путем длины $k = \sqrt{\log n}$.
		+	# Подберите $p(n)$ и приведите последовательности случайных величин $X_n$ для $G(n, p)$, что $EX_n \to \infty$, но $\mathcal{P}(X_n = 0) \nrightarrow 0$.
		+	# Для каких $p$ граф $G(n, p)$ а.п.н. не содержит $K_k$ (надо привести пороговую асимптотику)?
		+	# Пусть $p = \frac dn$. Докажите, что в $G(n, p)$ каждая вершина а.п.н. принадлежит не более, чем одному треугольнику.
		+	# Докажите, что в $G(n, \frac 12)$ а.п.н. не существует независимого множества размера $2 \log_2 n$
		+	# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ матожидание количества независимых множеств размера $(2 - \varepsilon) \log_2 n$ стремится к $\infty$.
		+	# Докажите, что для любого $\varepsilon > 0$ в $G(n, \frac 12)$ а.п.н. существует независимое множество размера $(2 - \varepsilon) \log_2 n$.

@@ Строка 133: / Строка 133: @@
 # (для 34-35) Докажите, что если $p = \omega(\frac{1}{n^2})$, то случайный граф $G(n, p)$ а.п.н. имеет хотя бы одно ребро.
 # (для 34-35) Пусть $p = \frac{c}{n^2}$ для некоторого $c$. Найдите вероятность того, $G(n, p)$ имеет хотя бы одно ребро.
-# Оцените центральный биномиальный коэффициент ${2n \choose n}$ снизу величиной порядка $\frac {c}{\sqrt{n}}$. Указание: используйте формулу Стирлинга.
+# Оцените центральный биномиальный коэффициент ${2n \choose n}$ снизу величиной порядка $c \frac {4^n}{\sqrt{n}}$. Указание: используйте формулу Стирлинга.
 # Рассмотрим число ребер $m$, такое что $m(n) \to \infty$ и ${n \choose 2} - m(n) \to \infty$, а также $p(n) = \frac {m(n)}{n \choose 2}$. Докажите, что вероятность того, что $G(n, p)$ имеет ровно $m$ ребер есть $\Omega(m^{-0.5})$.
 # Рассмотрим свойство $A$, а и такие же $m(n)$ и $p(n)$, как в предыдущей задаче. Докажите, что $P(G(n, m) \in A) \le C \sqrt{m} P(G(n, p) \in A)$.