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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:19:36Z

rollbackEdits.php mass rollback

171.25.193.80 в 05:29, 1 сентября 2022

2022-09-01T05:29:06Z

188.162.64.82 в 20:33, 15 декабря 2015

2015-12-15T20:33:22Z

185.29.130.2 в 14:52, 14 декабря 2015

2015-12-14T14:52:25Z

185.29.130.2 в 14:47, 14 декабря 2015

2015-12-14T14:47:24Z

188.162.64.9 в 22:37, 7 декабря 2015

2015-12-07T22:37:32Z

188.162.64.3 в 00:17, 1 декабря 2015

2015-12-01T00:17:07Z

188.162.64.3 в 00:14, 1 декабря 2015

2015-12-01T00:14:50Z

84.42.11.174 в 22:43, 22 ноября 2015

2015-11-22T22:43:42Z

Niyaz Nigmatullin в 22:55, 9 ноября 2015

2015-11-09T22:55:03Z

← Предыдущая		Версия 16:19, 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>
	= Алгоритмы и структуры данных, 1 семестр =		= Алгоритмы и структуры данных, 1 семестр =

← Предыдущая		Версия 05:29, 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>
	= Алгоритмы и структуры данных, 1 семестр =		= Алгоритмы и структуры данных, 1 семестр =

@@ Строка 94: / Строка 94: @@
              u \ne d(v)}} k(v)$. Доказать, что $\sum\limits_{v \in V}g(v) = O(n)$.
 # Задано подвешенное дерево. Нужно отвечать на запросы: подвесить вершину как лист к одной из имеющихся вершин, найти наименьшего общего предка двух уже добавленных вершин. Время работы запросов: $O(n \log{n})$.
-# Предложите алгоритм добавления в АВЛ-дерево
+# Предложите алгоритм добавления в АВЛ-дерево за $O(h)$, где $h$ {{---}} высота дерева.
-# Предложите алгоритм удаления из АВЛ-дерева.
+# Предложите алгоритм удаления из АВЛ-дерева за $O(h)$, где $h$ {{---}} высота дерева.
-# Предложите алгоритм добавления в красно-черное дерево
+# Предложите алгоритм добавления в красно-черное дерево за $O(h)$, где $h$ {{---}} высота дерева.
-# Предложите алгоритм удаления из красно-черного дерева
+# Предложите алгоритм удаления из красно-черного дерева за $O(h)$, где $h$ {{---}} высота дерева.
 # Статически оптимальное дерево поиска: пусть заданы ключи и известно для каждого ключа, сколько раз его потребуется искать: $p[i]$. Требуется построить дерево поиска, чтобы суммарное время доступа ко всем ключам было минимально.
 # Предложите алгоритм слияния двух АВЛ-деревьев, при том, что в первом дереве все ключи меньше, чем во втором за $O(\log n)$
@@ Строка 106: / Строка 106: @@
 # Перекошенное сбалансированное дерево. Дерево называется перекошенным сбалансированным, если у каждой вершины разность высоты левого и правого поддерева 0, 1 или 2. Предолжите реализацию операций вставки и удаления для перекошенного сбалансированного дерева.
 # Мальчик Петя считает, что если в дереве поиска можно хранить несколько одинаковых ключей, то на пути от одного такого ключа до другого не может быть ключей с другим значением. Тогда можно легко найти все такие ключи. Прав ли он?
 </wikitex>

@@ Строка 93: / Строка 93: @@
              u \in C(v) \\
              u \ne d(v)}} k(v)$. Доказать, что $\sum\limits_{v \in V}g(v) = O(n)$.
 </wikitex>

@@ Строка 89: / Строка 89: @@
 # Покраску дерева в $k$ цветов от 1 до $k$ назовем яркой, если между любыми двумя вершинами одного цвета $c$, существует вершина цвета $d$, что $d < c$. Рассмотрим функцию $f(n) = k$ {{---}} минимальное $k$, что любое дерево из $n$ вершин можно ярко покрасить в $k$ цветов. Докажите, что $f(n) = O(\log{n})$
 # Задано дерево из $n$ вершин. В каждой вершине есть число. Нужно отвечать на запросы: медиана в множестве чисел, записанных в вершинах на пути. Время на запрос: $O(\log{n})$.
-# Будет добавлено позже..
+# Рассмотрим подвешенное дерево. Пусть $s(v)$ {{---}} размер поддерева с корнем в вершине $v$, $C(v)$ {{---}} множество всех непосредственных потомков вершины $v$, $h(v) = \operatorname*{arg\,max}\limits_{u \in C(v)} s(u)$, $f(v) = s(v) - s(h(v))$. Доказать, что $\sum\limits_{v \in V}f(v) = O(n \log{n})$.
 </wikitex>

@@ Строка 84: / Строка 84: @@
 # Дано взвешенное дерево. Научиться отвечать на запросы "вес ребра" и "прибавить ко всем ребрам на пути от $v$ до $u$ число $d$". После предобработки за $O(n)$ ответ на запрос за $O(\log{n})$.
 # Алгоритм Хьюи. Дано дерево, вершины которого раскрашены в цвета, то есть задано отображение $col: V \to \{1..k\}$. С помощью LCA найти $dc: V \to \{1..k\}$, где $dc(u)$ - число различных цветов в поддереве с корнем в вершине $u$. Время работы: $O(V)$.
+# Задано взвешенное дерево. Посчитать число простых путей в дереве длины от $L$ до $R$ и весом от $x$ до $y$. Время работы $O(n \log^2{n})$.
 </wikitex>

@@ Строка 79: / Строка 79: @@
 # Решите за $O(\log{n})$ на запрос. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам на отрезке заданное число и вывести сумму сумм всех подотрезков отрезка.
 # Решите за $O(\log{n})$ на запрос. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам на отрезке заданное число, умножить все элементы на отрезке на заданное число, вывести $i$-й элемент массива.
-# Модифицировать алгоритм Фараха-Колтона-Бендера, чтобы массив precalc занимал только $O(K \log{K})$ памяти для каждой маски.
+# Модифицировать алгоритм Фараха-Колтона-Бендера, чтобы массив precalc занимал только $O(K \log{K})$ бит памяти для каждой маски.
 # Дано взвешенное дерево. Научиться отвечать на запросы "вес пути из $u$ в $v$". После предобработки за $O(n)$ ответ на запрос за $O(1)$.
 # Дано взвешенное дерево. Научиться отвечать на запросы "вес пути из $u$ в $v$" и "изменить вес ребра". После предобработки за $O(n)$ ответ на запрос за $O(\log{n})$.

@@ Строка 66: / Строка 66: @@
 # Дано $n$ точек на плоскости. Требуется найти наибольшую последовательность точек, в которой при переходе к следующей точке обе координаты строго возрастают, за $O(n \log n)$.
 # Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти точку, покрытую максимальным числом прямоугольников за $O(n \log n)$.
 </wikitex>

@@ Строка 57: / Строка 57: @@
 # Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 разных знаков, или одно из них равно 0.
 # Предложите алгоритм с временем работы $O(n)$ для следующей задачи: задан массив из неотрицательных чисел и число $k$, определите число отрезков с суммой, не превышающей $k$. Также проанализируйте, работает ли ваш алгоритм, если массив может содержать отрицательные числа: постройте контрпример или докажите, что работает.
-# Запросы на статическом массиве: задано число $k$ и запросы~--- отрезки длины от $k$ до $2k$. Ответ на запросы за $O(1)$ и препроцессинг за $O(n)$.
+# Запросы на статическом массиве: задано число $k$ и запросы {{---}} посчитать ассоциативную необратимую функцию на отрезке длины от $k$ до $2k$. Ответ на запросы за $O(1)$ и препроцессинг за $O(n)$.
-# Запросы: 1. set(i, x) {{---}} $a[i] := x$ (x {{---}} неотрицательно), 2. get(s) {{---}} найти такое минимальное $y$, что $\sum\limits_{i=1}^y \ge s$, $\sum\limits_{i=1}^{y - 1} < s$ за $O(\log{n})$.
+# Запросы: 1. set(i, x) {{---}} $a_i := x$ (x {{---}} неотрицательно), 2. get(s) {{---}} найти такое минимальное $y$, что $\sum\limits_{i=1}^y a_i \ge s$, $\sum\limits_{i=1}^{y - 1} a_i < s$ за $O(\log{n})$.
-# Обработайте $Q$ запросов на прибавление на отрезке, получите конечный массив, за $O(Q)$.
+# Обработайте $q$ запросов на прибавление на отрезке, получите конечный массив длины $n$, за $O(n + q)$.
 # Обработайте запросы за $O(\log{n})$. Первый {{---}} присвоить значение элементу, второй {{---}} задан отрезок, найти подотрезок с максимальной суммой, содержащийся в этом отрезке.
 # Сведите задачу к запросам изменения в точке и функции на отрезке за $O(\log{n})$. Задача {{---}} отвечать на запросы: прибавление на отрезке и минимум на отрезке.