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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:44:02Z

rollbackEdits.php mass rollback

185.220.100.241 в 03:24, 1 сентября 2022

2022-09-01T03:24:42Z

188.227.78.59 в 18:58, 23 декабря 2015

2015-12-23T18:58:55Z

188.227.78.59 в 17:50, 23 декабря 2015

2015-12-23T17:50:48Z

188.227.78.59 в 17:49, 23 декабря 2015

2015-12-23T17:49:15Z

188.227.78.59 в 17:41, 23 декабря 2015

2015-12-23T17:41:51Z

188.227.78.59 в 17:34, 23 декабря 2015

2015-12-23T17:34:23Z

77.234.215.133 в 15:21, 18 декабря 2015

2015-12-18T15:21:02Z

77.234.215.133 в 18:13, 14 декабря 2015

2015-12-14T18:13:47Z

188.227.78.144 в 08:49, 20 ноября 2015

2015-11-20T08:49:48Z

← Предыдущая		Версия 16:44, 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 Майкл Наки].
−	\|}
−
	<wikitex>		<wikitex>
	# Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.		# Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.

← Предыдущая		Версия 03:24, 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 Майкл Наки].
		+	\|}
		+
	<wikitex>		<wikitex>
	# Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.		# Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.

@@ Строка 136: / Строка 136: @@
 # Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.
 # Постройте граф, в котором алгоритм Форда-Фалкерсона (ФФ) находит $\Omega(C_{max})$ путей. Веса всех рёбер целочисленные.
 # Постройте граф, в котором алгоритм Эдмондса-Карпа совершить $\Omega(V E)$ дополнений до пути.
 # Доказать теорему о декомпозиционном барьере. (см. вики-конспекты)

@@ Строка 137: / Строка 137: @@
 # Постройте граф, в котором алгоритм Форда-Фалкерсона (ФФ) находит $\Omega(C_{max})$ путей. Веса всех рёбер целочисленные.
 # Постройте граф, в котором не будет найден максимальный поток. Веса рёбер вещественные.
 # Постройте граф, в котором алгоритм Эдмондса-Карпа совершить $\Omega(V E)$ дополнений до пути.
 # Доказать теорему о декомпозиционном барьере. (см. вики-конспекты)

@@ Строка 140: / Строка 140: @@
 # Постройте граф, в котором алгоритм Эдмондса-Карпа совершить $\Omega(V E)$ дополнений до пути.
 # Доказать теорему о декомпозиционном барьере. (см. вики-конспекты)
 # Альтернативная реализация масштабирования потока $-$ на каждом шаге рассматриваем рёбра с пропускной способностью $c \ge 2^{k-i}$. Доказать, что для такой реализации время работы $O(EEk)$.
 # $f_{max}$ - макс. поток, $f_{blocking}$ - блокирующий поток. Доказать, что $\frac {|f_{blocking}|} { |f_{max}|} $ может быть сколь угодно мало.

@@ Строка 135: / Строка 135: @@
 # Докажите вершнинную теорему Менгера: минимальное число вершин, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу вершинно непересекающихся путей из $s$ в $t$ ($s$ и $t$ удалять нельзя).
 # Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.
 # Постройте граф, в котором алгоритм Форда-Фалкерсона (ФФ) находит $\Omega(C_{max})$ путей. Веса всех рёбер целочисленные.
 # Постройте граф, в котором не будет найден максимальный поток. Веса рёбер вещественные.
 # Если выбирать путь с максимальным $C_{min}$, то время работы ФФ будет $O(polynom(V, E) \log(C_{max}))$. Докажите это.
 # Постройте граф, в котором алгоритм Эдмондса-Карпа совершить $\Omega(V E)$ дополнений до пути.
-# Доказать, что величину потока можно представить в виде $\sum{c_{i}  f_{p_{i}}}$ + $\sum{d_{j} f_{k_{j}}}$ , где $p_i$ - путь из $s$ в $t$, $k_j$ - цикл, $c_i$ и $d_j$ - константы.
+# Доказать теорему о декомпозиционном барьере. (см. вики-конспекты)
 # Пусть есть $k$ истоков и $m$ стоков. Свести задачу к задаче о максимальном потоке.
 # Пусть у вершин тоже будет пропускная способность. Свести задачу к задаче о максимальном потоке.

← Предыдущая		Версия 17:34, 23 декабря 2015
Строка 135:		Строка 135:
	# Докажите вершнинную теорему Менгера: минимальное число вершин, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу вершинно непересекающихся путей из $s$ в $t$ ($s$ и $t$ удалять нельзя).		# Докажите вершнинную теорему Менгера: минимальное число вершин, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу вершинно непересекающихся путей из $s$ в $t$ ($s$ и $t$ удалять нельзя).
	# Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.		# Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.
		+	# Сформулируйте и докажите аналогичную лемме о сумме лемму о разности потоков.
		+	# Постройте граф, в котором алгоритм Форда-Фалкерсона (ФФ) находит $\Omega(C_{max})$ путей. Веса всех рёбер целочисленные.
		+	# Постройте граф, в котором не будет найден максимальный поток. Веса рёбер вещественные.
		+	# Если выбирать путь с максимальным $C_{min}$, то время работы ФФ будет $O(polynom(V, E) \log(C_{max}))$. Докажите это.
		+	# Постройте граф, в котором алгоритм Эдмондса-Карпа совершить $\Omega(V E)$ дополнений до пути.
		+	# Доказать, что величину потока можно представить в виде $\sum{c_{i} f_{p_{i}}}$ + $\sum{d_{j} f_{k_{j}}}$ , где $p_i$ - путь из $s$ в $t$, $k_j$ - цикл, $c_i$ и $d_j$ - константы.
		+	# Доказать теорему о декомпозиционном барьере. (см. вики-конспекты)
		+	# Поток назовём циркуляцией, если его величина равна $0$. Рассмотрим граф $G$ такой, что $ \forall uv \in E : L_{uv} \le f_{uv} \le R_{uv} $. Свести поиск допустимой циркуляции к задаче о макс. потоке.
		+	# Пусть есть $k$ истоков и $m$ стоков. Свести задачу к задаче о максимальном потоке.
		+	# Пусть у вершин тоже будет пропускная способность. Свести задачу к задаче о максимальном потоке.
		+	# Альтернативная реализация масштабирования потока $-$ на каждом шаге рассматриваем рёбра с пропускной способностью $c \ge 2^{k-i}$. Доказать, что для такой реализации время работы $O(EEk)$.
		+	# $f_{max}$ - макс. поток, $f_{blocking}$ - блокирующий поток. Доказать, что $\frac {\|f_{blocking}\|} { \|f_{max}\|} $ может быть сколь угодно мало.
		+	# Доказать, что если в алгоритме масштабирования использовать алгоритм Диница вместо ФФ, то время работы равно $O(E V k)$.
		+	# Доказать, что на графе с целочисленными пропускными способностями рёбер число итераций while в алгоритме Диница равно $O(V^{\frac{2}{3}} {c_{max}}^{\frac{1}{3}})$.
		+	# Доказать, что на графе с целочисленными пропускными способностями рёбер число итераций алгоритма Диница равно $O(V^{\frac{1}{2}} * c(G)^{\frac{1}{2}})$.

← Предыдущая		Версия 15:21, 18 декабря 2015
Строка 128:		Строка 128:
	# Докажите, что если в кубическом графе не более двух мостов, то в нем есть полное паросочетание.		# Докажите, что если в кубическом графе не более двух мостов, то в нем есть полное паросочетание.
	# Приведите пример кубического графа, в котором нет полного паросочетания.		# Приведите пример кубического графа, в котором нет полного паросочетания.
		+	# Докажите, что если $f$ - поток, и в графе $G_f$ нет циклов отрицательного веса и пути отрицательного веса из $s$ в $t$, то $f$ - поток минимальной стоимости среди всех потоков в $G$ (вне зависимости от величины).
		+	# Пусть в графе нет циклов отрицательной стоимости. Рассмотрим алгоритм: начав с нулевого потока, каждый раз дополняем поток вдоль пути минимальной стоимости способности из $s$ в $t$ в остаточной сети. Докажите, что стоимости найденных путей не убывают.
		+	# Пусть в графе нет циклов отрицательной стоимости. Предложите алгоритм поиска потока минимальной среди всех потоков стоимости (вне зависимости от величины).
		+	# Предложите алгоритм проверки, что в графе единственный минимальный разрез
		+	# Докажите реберную теорему Менгера: минимальное число ребер, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу реберно непересекающихся путей из $s$ в $t$.
		+	# Докажите вершнинную теорему Менгера: минимальное число вершин, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу вершинно непересекающихся путей из $s$ в $t$ ($s$ и $t$ удалять нельзя).
		+	# Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.

← Предыдущая		Версия 18:13, 14 декабря 2015
Строка 112:		Строка 112:
	# Предложите реализацию алгоритма двух китайцев за $O(E \log E)$.		# Предложите реализацию алгоритма двух китайцев за $O(E \log E)$.
	# Предложите алгоритм поиска остовного дерева с минимальным весом максимального ребра за время равное работе алгоритма поиска MST.		# Предложите алгоритм поиска остовного дерева с минимальным весом максимального ребра за время равное работе алгоритма поиска MST.
		+	# Петя в алгоритме Форда-Фалкерсона для поиска паросочетания в двудольном графе сделал ошибку: оставил рёбра между долями графа неориентированными. Построить пример, на котором алгоритм будет работать неправильно.
		+	# Доказать теорему Холла: что в двудольном графе $G$ существует полное паросочетание тогда и только тогда, когда для любого множества вершин левой доли $A \subset X$ выполнено $\|N(A)\| \ge \|A\|$. ($N(A)$ - множество соседей вершин из $A$)
		+	# Докажите, что в регулярном двудольном графе существует полное паросочетание.
		+	# Дефектом множества вершин левой доли в графе называется $def(A) = \|N(A)\| - \|A\|$. Найти в двудольном графе множество с минимальным дефектом.
		+	# Дан ациклический ориентированный граф. Нужно покрыть его минимальным числом вершинно-непересекающихся путей. Сведите эту задачу к задаче о максимальном паросочетании.
		+	# Дан ациклический ориентированный граф. Нужно покрыть его минимальным числом реберно-непересекающихся путей.
		+	# Докажите, что если в графе единственное полное паросочетание, то в нем есть мост
		+	# Предложите алгоритм проверки, что в двудольном графе четное число полных паросочетаний
		+	# Предложите алгоритм проверки по двудольному графу и заданному полному паросочетанию, является ли оно единственным в этом графе (за $O(E)$).
		+	# Предложите алгоритм для решения следующей задачи за $O(E)$. Дан двудольный граф и полное паросочетание в нем. Требуется выяснить для каждого ребра, лежит ли оно на некотором полном паросочетании.
		+	# Задача об устойчивом паросочетании. Задан двудольный граф с равным числом вершин в долях. Для каждой вершины каждой доли известен порядок предпочтения вершин другой доли (каждая вершина знает, какая вершина другой доли ей нравится больше всего, какая вершина на втором месте, и так далее). Паросочетание называется устойчивым, если никакие две вершины не могут обменяться парами, чтобы для каждой из них новый партнер стал более предпочтительным. Требуется построить устойчивое полное паросочетание за $O(VE)$.
		+	# Пусть $G$ - регулярный двудольный граф степени $k$. Докажите, что ребра $G$ можно разбить на $k$ полных паросочетаний.
		+	# Пусть $G$ - регулярный граф степени $k$, $U \subset V$, $U$ содержит нечетное число вершин и $m$ - число ребер, которые соединяют вершины $U$ с вершинами $V \setminus U$. Тогда $m$ четно тогда и только тогда, когда $k$ четно.
		+	# Докажите, что в двусвязном кубическом графе есть полное паросочетание.
		+	# Докажите, что если в кубическом графе не более двух мостов, то в нем есть полное паросочетание.
		+	# Приведите пример кубического графа, в котором нет полного паросочетания.

← Предыдущая		Версия 08:49, 20 ноября 2015
Строка 100:		Строка 100:
	# Сведите задачу о максимальном потоке с несколькими истоками и несколькими стоками к обычной задаче о максимальном потоке.		# Сведите задачу о максимальном потоке с несколькими истоками и несколькими стоками к обычной задаче о максимальном потоке.
	# Можно ввести понятие пропускной способности вершины $c(u)$ как максимальной разрешенной суммы $\sum_{uv}f(uv)$. Решите задачу о максимальном потоке для графа с пропускными способностями вершин.		# Можно ввести понятие пропускной способности вершины $c(u)$ как максимальной разрешенной суммы $\sum_{uv}f(uv)$. Решите задачу о максимальном потоке для графа с пропускными способностями вершин.
		+	# Доказать, что дерево $T$ является MST (здесь и далее MST - минимальное остовное дерево) тогда и только тогда, когда для любого ребра $uv \not\in T$ это ребро максимальное по весу на единственном цикле в графе $T \cup uv$. (Критерий Тарьяна)
		+	# Используя критерий Тарьяна предложить алгоритм проверки того, что $T$ - MST, работающий за $O(E\times DSU)$
		+	# [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D1%80%D1%83%D0%B2%D0%BA%D0%B8]. Доказать корректность работы алгоритма Борувки.
		+	# Предложить реализацию алгоритма Борувки, работающую за $O(E \log V)$.
		+	# Предложите реализацию алгоритма Борувки, работающую за $O(E \log^*V)$. (Указание - см. Freedman, Tarjan статью про фибоначчиевы кучи)
		+	# Рассмотрим граф, вершины которого - остовные деревья $G$, а ребро между деревьями $T_1$ и $T_2$ существует, если $T_1$ получается из $T_2$ добавлением одного ребра и удалением другого. В нём рассмотрим подграф, состоящий только из $MST$. Доказать, что он связен.
		+	# Рассмотрим граф. Упорядочим все его остовные деревья по возрастанию веса. Требуется найти вес второго в этом упорядочении дерева.
		+	# Разработать алгоритм поиска всех рёбер, принадлежащих какому-нибудь MST за $O(VE)$.
		+	# Петя пытается применить алгоритм Прима для ориентированного графа. Приведите пример графа, на котором Петя не сможет найти MST даже, если исходящее дерево из $s$ существует и Петя найдет какое-либо такое дерево.
		+	# Коля пытается применить алгоритм Краскала для ориентированного графа. Приведите пример графа, на котором Коля не сможет найти MST, если исходящее дерево из $s$ существует и Коля найдет какое-либо такое дерево.
		+	# Предложите реализацию алгоритма двух китайцев за $O(E \log E)$.
		+	# Предложите алгоритм поиска остовного дерева с минимальным весом максимального ребра за время равное работе алгоритма поиска MST.