Список заданий по продвинутым алгоритмам 2021 осень

1. $1 | p_i=1 | L_{max}$.
2. $1 | r_i, d_i=d | L_{max}$.
3. $1 | prec, r_i, p_i=1 | L_{max}$.
4. Рассмотрим задачу $1 | p_i = 1, d_i | -$. Докажите, что подмножества работ, которые можно выполнить, образуют семейство независимых множеств некоторого матроида.
5. $1 | p_i = 1, d_i | \sum w_iU_i$. Время $O(n\log n)$.
6. $1 | p_i = 1, d_i, r_i | \sum U_i$. Время - полином от $n$.
7. $1 | p_i = 1, d_i, r_i | \sum w_iU_i$. Время - полином от $n$.
8. $1 | p_i = p, pmtn, r_i | \sum w_iU_i$ за $O(n^{10})$.
9. $1 || \sum U_i$
10. $1 | r_i, p_i = p | \sum w_iC_i$ за $O(n^7)$
11. Обозначение outtree означает, что граф зависимостей представляет собой исходящее дерево: каджая работа зависит не более чем от одной другой. $1 | outtree | \sum w_iC_i$
12. Обозначение intree означает, что граф зависимостей представляет собой входящее дерево: от каждой работы зависит не более одной другой. $1 | intree | \sum w_iC_i$
13. $P | pmtn, r_i | C_{max}$
14. $P | pmtn, r_i | L_{max}$
15. $Q | pmtn, r_i | C_{max}$
16. $P | p_i = p, r_i, d_i | \sum C_i$ за $O(n^3 \log n)$ (бонус за $O(n^3 \log\log n)$)
17. $P | p_i = 1 | \sum w_iU_i$ - доведите доказательство с пары до конца
18. $P | p_i = 1 | \sum w_iC_i$
19. $P | p_i = 1, pmtn | \sum w_iC_i$
20. $Q | pmtn | \sum C_i$
21. $Q | pmtn | \sum f_i$ (напомним, что f_i - произвольная неубывающая функция, может быть своя у каждой работы)
22. $Q | pmtn | f_{max}$
23. $P2 | p_i = 1, prec, r_i | \sum C_i$ за $O(n^9)$
24. Сведите задачу $R|pmtn|C_{max}$ к задаче линейного программирования.
25. $P|intree, p_i=1|L_{max}$
26. $F | p_{ij} = 1 | \sum C_i$
27. $F2 | pmtn | C_{max}$
28. $F | p_{ij} = 1 | \sum U_i$
29. $F | p_{ij} = 1 | \sum w_iU_i$
30. $O | p_{ij} = 1 | C_{max}$
31. $O | p_{ij} = 1 | \sum C_i$
32. $O | p_{ij} = 1 | \sum w_iC_i$
33. $O | p_{ij} = 1, d_i | -$
34. $O | p_{ij} = 1 | \sum U_i$
35. $O | p_{ij} = 1 | \sum w_iU_i$
36. $O | p_{ij} = 1, r_i | C_{max}$
37. $O2 | p_{ij} = 1, prec | \sum C_i$
38. Обозначим как $BP(n)$ время умножения булевых матриц размера $n \times n$ над $\vee, \wedge$. Обозначим как $MM(n)$ время умножения целочисленных матриц размера $n \times n$ над $+, \times$. Докажите, что $BP(n) = O(MM(n))$.
39. Докажите, что можно найти транзитивное замыкание графа за время $O(BP(n))$.
40. Пусть $A$ и $B$ - матрицы размера $n \times n$. Пусть $R \subset \{1, 2, \ldots, n\}$, $|R|=r$. Обозначим как $A^R$ матрицу, которая получается из $A$ удалением всех столбцов, кроме столбцов из множества $R$. Аналогично, обозначим как $B_R$ матрицу, которая получается из $B$ удалением всех строк, кроме строк из множества $R$. Докажите, что произведение матриц $A^R\cdot B_R$ может быть найдено за время $O((n/r)^2 MM(r))$, где $MM(r)$ - время умножения матриц размером $r\times r$.
41. Пусть $MM(n)=2+\varepsilon$, $\varepsilon>0$. Модифицируйте алгоритм построения BPWM, чтобы он работал за $MM(n) \log n$. Почему эта идея не сработает, если $MM(n) = O(n^2)$?
42. Докажите лемму с лекции про то, что если в урне $n$ шаров, из которых $w$ белых и $n/2\le wr \le n$, а событие $A$ означает, что из $r$ наугад выбранных из урны шаров оказался ровно один белый, то $P(A) \ge 1/2e$.
43. Сохраняется ли вероятность из предыдущего задания, если шары после вытаскивания возвращаются в урну? Если нет, то можно ли получить аналогичную оценку?
44. Нижняя оценка на сумму длин путей. Докажите, что можно построить граф, в котором $\Omega(n^2)$ пар вершин, расстояние между которыми $\Omega(n)$.
45. Известно, что у учителя есть $2^k$ яблок для некоторого целого неотрицательного $k$. На глазах у студентов он съедает одно яблоко, а остальное раздает ученикам А и В, чтобы ни один из них не видел, сколько получает другой. А и В не знают числа $k$. Они могут показать друг другу по одному знаку из трёх возможных: почесать голову правой, левой или обеими руками. К удивлению учителя, ученики всегда знают, кто получил больше яблок или что учитель съел единственное яблоко сам. Как такое возможно?
46. Вероятностный алгоритм поиска минимума некоторый функции от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $1/2$. Как найти верный ответ с вероятностью $99/100$ за полином от $n$?
47. Вероятностный алгоритм проверки некоторого предиката от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $1/2$. Можно ли найти верный ответ с вероятностью $99/100$ за полином от $n$?
48. Вероятностный алгоритм проверки некоторого предиката от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $2/3$. Как найти верный ответ с вероятностью $99/100$ за полином от $n$?
49. В алгоритме Кинг с лекции обозначим как $f(u)$ лист, которая получается в ветвящемся дереве $T'$ из вершины $u$ в исходном дереве $T$. Докажите, что если вес максимального ребра на пути из $u$ в $v$ в $T$ равен $x$, а вес максимального ребра на пути из $f(u)$ в $f(v)$ в $T'$ равен $x'$, то $x \ge x'$.
50. В условиях предыдущей задачи докажите, что то $x \le x'$.
51. Рассмотрим ветвящееся дерево, пусть в нем $n$ вершин. Пусть есть $m$ запросов на пары листьев, для которых необходимо найти максимальное ребро на пути. Разобьем каждый запрос на два запроса на вертикальном пути до $LCA$ этих листьев, таким образом имеем $2m$ вертикальных путей. Для вершины $v$ обозначим как $A(v)$ множество вертикальных путей, проходящих через $v$. Обозначим как $D_i$ множество вершин на расстоянии $i$ от корня, как $d_i$ число вершин на расстоянии $i$ от корня ($d_i=|D_i|$). Докажите, что $\sum\limits_{u\in D_i}\lceil\log(1+|A(u)|)\rceil<\sum\limits_{u\in D_i}\left(1+\log(1+|A(u)|)\right)\le d_i+d_i \log\frac{d_i+2m}{d_i}$.
52. В условиях предыдущей задачи докажите, что $\sum\limits_{i\ge 0}\left(d_i + d_i\log\frac{d_i+2m}{d_i}\right)\le n+n\log\frac{n+2m}{n}+2n$.
53. Докажите, что $\sum\limits_{u}\lceil\log(1+|A(u)|)\rceil = O(n + m)$.
54. Обозначим как $A[v]$ число, в котором $i$-й бит равен $1$, если в $A(v)$ есть путь, заканчивающийся на расстоянии $i$ от корня. Считайте, что вы можете решить задачу о $m$ запросах $LCA$ в дереве с $n$ вершинами за $O(n+m)$ (например, используя алгоритм Фарах-Колтона и Бендера, см https://www.ics.uci.edu/~eppstein/261/BenFar-LCA-00.pdf). Объясните, как посчитать $A[v]$ за время $O(n+m)$.
55. Назовем вершину $v$ большой, если $|A(v)| > \log n/\log\log n$ и маленькой в противном случае. Докажите, что число больших вершин асимптотически не превышает $m /\log\log n$. Указание: оцените число больших вершин на каждом уровне дерева. Отдельно рассмотрите большие вершины на нижних $\log\log n$ и на остальных уровнях.
56. Для вершины $v$, для которой $|A(v)| = k$ рассмотрим фрагменты путей, лежащие выше вершины $v$. Будем хранить $B(v) = [l_1, l_2, \ldots, l_k]$ - список глубин самых тяжелых ребер на фрагментах путях, проходящих через $v$, в порядке от самого длинного пути к самому короткому. Иначе говоря, пронумеруем пути из $A(v)$ в порядке возрастания глубины их верхней вершины. Тогда $l_i$ - расстояние от корня до ребра, которое является самым тяжелым на пути от $v$ до некоторой вершины $u_i$, которая является верхним концом $i$-го пути. Числа $l_i$ называются тагами, длина тага $O(\log\log n)$. Докажите, что массив $B(v)$ отсортирован по неубыванию.
57. Пусть $p$ - родитель вершины $v$, как связаны массивы $B(p)$ и $B(v)$? Дайте подробное описание, используя, при необходимости, $A(p)$ и $A(v)$.
58. Для больших вершин $B(v)$ помещается в $O(\log\log n)$ машинных слово. Пусть родитель вершины также большой. Предложите алгоритм пересчета $B(v)$ через $B(p)$, $A[p]$ и $A[v]$ за $O(\log\log n)$, перед этим можно выполнить общий для всех вершин предподсчет за $O(n+m)$.
59. Обозначим как $bigp[v]$ максимальную глубину, на котором находится большой предок вершины $v$. Предложите алгоритм, как за построить массив $bigp$ по массиву $A$ за $O(n)$.
60. Для маленьких вершин $B(v)$ помещается в машинное слово, однако вместо списка $B(v)$ будем хранить вспомогательный список $C(v)$, устроенный так. Если самое тяжелое ребро на $i$-м по глубине пути из $A(v)$ находится ниже, чем $bigp[v]$, то будем хранить просто $l_i$. Иначе будем хранить $z_i$ - номер $l_i$ в $B(bigp[v])$. Обозначим упакованный в машинное слово список $C(v)$ за $C[v]$. Предложите алгоритм пересчета $С[v]$ за $O(1)$, перед этим можно выполнить общий для всех вершин предподсчет за $O(n+m)$. Вы можете использовать посчитанные для родителей и предков $C[u]$, $B(u)$, $A[u]$, $bigp[u]$.
61. Объедините результаты всех предыдущих заданий, чтобы получить алгоритм обработки $m$ запросов поиска максимального ребра на пути между двумя вершинами на дереве за $O(n+m)$.
62. Покажите, как свести задачу поиска минимального разреза в графе к $O(n)$ запускам алгоритма поиска минимального $s-t$ разреза.
63. Покажите, как свести задачу поиска минимального $s-t$ разреза в графе к полиномимальному числу запусков алгоритма поиска глобального минимального разреза.
64. Петя хочет упростить алгоритм Каргера-Штайна. Он запускает алгоритм Каргера (стягивание по случайному ребру), пока количество вершин не станет равно $t$, а затем запускает алгоритм за $t^3$ поиска минимального глобального разреза. Затем он повторяет алгоритм, пока вероятность успеха не составит хотя бы $1/2$. Какое значение $t$ необходимо выбрать, чтобы минимизировать время работы получившегося алгоритма? Какое будет время работы?
65. Докажите, что если в полном двоичном дереве высоты $h$ каждое ребро удаляется с вероятностью $1/2$, то путь от корня до листа сохраняется с вероятностью $\Theta(1/h)$.
66. Обобщите предыдущее задание, если ребро удаляется с вероятностью $p$.
67. С учетом предыдущего задания модифицируйте алгоритм Каргера-Штайна, чтобы разветвляться когда накопленная вероятность ошибки достигнет $p$. Найдите зависимость времени работы от $p$, какое значение $p$ оптимально выбрать?
68. Назовем разрез $\alpha$-оптимальным, если его размер не больше $\alpha C_{min}$, где $C_{min}$ - минимальный разрез. Оцените вероятность, что один запуск алгоритма Каргера (без разветвлений) найдет $\alpha$-оптимальный разрез (в зависимости от $\alpha$).
69. Докажите, что в графе не больше $n\choose 2$ различных минимальных глобальных разрезов.
70. Сформулируйте и докажите аналогичный предыдущему заданию результат для $\alpha$-оптимальных разрезов.
71. Докажите, что для полинома $p(x_1, \ldots, x_n)$ от $n$ переменных степени $d$ над полем $F$ и множества $S\subset F$ размера $s$ вероятность $P(p(x_1, \ldots, x_n)=0)\le d/s$, где вероятностное пространство - равновероятно все вектора $(x_1, \ldots, x_n)\in S^n$. Используйте без доказательства, что полином от одной переменной степени $d$ над любым полем имеет не более $d$ корней.
72. Покажите, что требование, что $F$ поле в предыдущей задаче является существенным, приведите пример полинома степени $d$ над кольцом, которое не является полем, имеющего более $d$ корней.
73. Покажите, что в определении PRAS можно заменить константу $3/4$ в требовании, что вероятность попасть в интервал $[1-\varepsilon;1+\varepsilon]$ должна быть $3/4$, на любое другое число, строго большее $1/2$.
74. Можно ли в предыдущем задании заменить $1/2$ на $0$?
75. Можно ли в решении задания 73 брать среднее значение в качестве оценки?
76. Рассмотрим формулу в ДНФ. Обозначим как $t$ количество пар $($терм$,$ удовлетворяющее этот терм назначение переменных$)$. Выберем случайно терм, где вероятность выбрать терм пропорциональна числу удовлетворяющих этот терм назначений. Выберем случайное назначение $a$, удовлетворяющее этот терм. Рассмотрим случайную величину $X = t/cov(a)$, где $cov(a)$ - число термов, удовлетворенных назначением $a$. Докажите, что $EX = Y$, где $Y$ - число удовлетворяющих назначений заданной формулы.
77. На базе предыдущего задания предложите альтернативный алгоритм апроксимации числа удовлетворяющих назначений ДНФ.
78. Рандомизированный алгоритм для 2SAT. Рассмотрим следующий алгоритм решения задачи удовлетворимости булевой формулы в 2КНФ с $n$ переменными. Выберем случайное значение каждой переменной. Если формула не удовлетворена, выберем случайный не удовлетворенный клоз и инвертируем значение случайной переменной в нем. Докажите, что если удовлетворяющее назначение существует, оно будет найдено за $O(n^2)$ шагов. Указание: зафиксируйте любое удовлетворяющее формулу назначение и рассмотрите задачу как случайное блуждание по прямой, где координата - это число переменных, значение которых совпадает с значением в выбранном назначении.
79. Почему алгоритм из предыдущего задания не работает для 3SAT?
80. Докажите, что оценку из задания 78 нельзя улучшить: предложите формулу, для которой в среднем понадобится $\Omega(n^2)$ случайных шагов для поиска удовлетворяющего назначения.
81. Предложите аналогичный заданию 78 алгоритм поиска раскраски графа в два цвета.
82. Почему алгоритм из предыдущего задания не работает для поиска раскраски графа в три цвета?