Список заданий по продвинутым алгоритмам 2023 осень — различия между версиями
Admin (обсуждение | вклад) |
Admin (обсуждение | вклад) |
||
Строка 49: | Строка 49: | ||
# Докажите, что в графе не больше $n\choose 2$ различных минимальных глобальных разрезов. | # Докажите, что в графе не больше $n\choose 2$ различных минимальных глобальных разрезов. | ||
# Сформулируйте и докажите аналогичный предыдущему заданию результат для $\alpha$-оптимальных разрезов. | # Сформулируйте и докажите аналогичный предыдущему заданию результат для $\alpha$-оптимальных разрезов. | ||
− | # | + | # Докажите, что для полинома $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$ корней. |
− | + | # Покажите, что требование, что $F$ поле в предыдущей задаче является существенным, приведите пример полинома степени $d$ над кольцом, которое не является полем, имеющего более $d$ корней. | |
− | # Покажите, | + | # Покажите, что в определении PRAS можно заменить константу $3/4$ в требовании, что вероятность попасть в интервал $[1-\varepsilon;1+\varepsilon]$ должна быть $3/4$, на любое другое число, строго большее $1/2$. |
− | # | + | # Можно ли в предыдущем задании заменить $1/2$ на $0$? |
− | # | + | # Можно ли в решении задания 73 брать среднее значение в качестве оценки? |
− | # | + | # Рассмотрим формулу в ДНФ. Обозначим как $t$ количество пар $($терм$,$ удовлетворяющее этот терм назначение переменных$)$. Выберем случайно терм, где вероятность выбрать терм пропорциональна числу удовлетворяющих этот терм назначений. Выберем случайное назначение $a$, удовлетворяющее этот терм. Рассмотрим случайную величину $X = t/cov(a)$, где $cov(a)$ - число термов, удовлетворенных назначением $a$. Докажите, что $EX = Y$, где $Y$ - число удовлетворяющих назначений заданной формулы. |
− | + | # На базе предыдущего задания предложите альтернативный алгоритм апроксимации числа удовлетворяющих назначений ДНФ. | |
− | + | # Рандомизированный алгоритм для 2SAT. Рассмотрим следующий алгоритм решения задачи удовлетворимости булевой формулы в 2КНФ с $n$ переменными. Выберем случайное значение каждой переменной. Если формула не удовлетворена, выберем случайный не удовлетворенный клоз и инвертируем значение случайной переменной в нем. Докажите, что если удовлетворяющее назначение существует, оно будет найдено за $O(n^2)$ шагов. Указание: зафиксируйте любое удовлетворяющее формулу назначение и рассмотрите задачу как случайное блуждание по прямой, где координата - это число переменных, значение которых совпадает с значением в выбранном назначении. | |
− | # | + | # Почему алгоритм из предыдущего задания не работает для 3SAT? |
− | # | + | # Докажите, что оценку из задания 78 нельзя улучшить: предложите формулу, для которой в среднем понадобится $\Omega(n^2)$ случайных шагов для поиска удовлетворяющего назначения. |
− | + | # Предложите аналогичный заданию 78 алгоритм поиска раскраски графа в два цвета. | |
− | + | # Почему алгоритм из предыдущего задания не работает для поиска раскраски графа в три цвета? | |
− | # | ||
− | # |
Версия 19:36, 19 октября 2023
- Докажите, что дисперсия возвращаемого значения в алгоритме Морриса не превышает $1/2n^2$
- Докажите, что дисперсия возвращаемого значения в алгоритме Флажолета-Мартина не превышает $1/(t+1)^2$
- Доминирующий элемент. Рассмотрим алгоритм, который ищет элемент, который встречается хотя бы $n/2$ раз в потоке $[a_1, \ldots, a_n]$. Пусть $0 \le a_i < N$ и $N \ge 2n$. Докажите, что детерминированный алгоритм, использующий $o(n\log(N/n))$ бит, не может решить поставленную задачу. Указание: рассмотрите состояние после половины элементов потока.
- Предложите алгоритм, использующий $O(\log(N+n))$ бит, который решает предыдущую задачу в предположении, что доминирующий элемент существует.
- Обобщите предыдущий алгоритм на случай $\varepsilon$-частых элементов: будем называть элемент $\varepsilon$-частым, если он составляет хотя бы $\varepsilon$ долю элементов во вводе. Как зависит память от $\varepsilon$?
- Все различные. Докажите или опровергните, что любой детерминированный алгоритм, который всегда корректно отвечает, верно ли, что все элементы во вводе $[a_1, a_2, \ldots, a_n]$ различны, должен использовать хотя бы $\Omega(n\log(2N/n))$ памяти.
- Недостающий элемент. Задан массив $[a_1, a_2, \ldots, a_{n-1}]$, где все элементы от $1$ до $n$, кроме одного, встречаются ровно один раз. Найдите недостающий элемент, используя $O(\log n)$ памяти.
- Два недостающих элемента. Задан массив $[a_1, a_2, \ldots, a_{n-2}]$, где все элементы от $1$ до $n$, кроме двух, встречаются ровно один раз. Найдите недостающие элементы, используя $o(n)$ памяти.
- Два недостающих элемента. Задан массив $[a_1, a_2, \ldots, a_{2n-1}]$, где все элементы от $1$ до $n$, кроме одного, встречаются ровно два раза, а один — один раз. Найдите этот элемент, используя $o(n)$ памяти.
- Два недостающих элемента. Задан массив $[a_1, a_2, \ldots, a_{2n-2}]$, где все элементы от $1$ до $n$, кроме двух, встречаются ровно два раза, а два — по одному разу. Найдите эти элементы, используя $o(n)$ памяти.
- В алгоритме KMV обозначим как $Z$ количество элементов, для которых $h(v) < kM/(1-\varepsilon)t$. Докажите, что $P(Z<k)<1/6$.
- Задача приблизительного подсчета числа вхождений. Biased Sketch. Рассмотрим алгоритм: выберем случайную хеш-функцию $h: U\to \{0,1, \ldots, m-1\}$ из универсального семейства. Заведем счетчик $cnt[0\ldots m-1]$ и в качестве операцими $update(x)$ будем делать $cnt[h(x)]$++, а в качестве $query(x)$ будем возвращать $cnt[h(x)]$. Пусть выполнено $n$ запросов $update$. Обозначим как $a(x)$ количество вхождений числа $x$. Оцените $P(query(x) > a(x) + \varepsilon n)$.
- CountMin. В предыдущей задаче чтобы лучше оценить количество, будем использовать несколько хеш-функций. Пусть мы используем $r$ хеш-функций, для каждой свой массив $cnt_i$, в качестве ответа на запрос будем выдавать $\min(cnt_i[h_i(x)])$. Какое $r$ необходимо выбрать, чтобы выполнялось $P(query(x) > a(x) + \varepsilon n) < \delta$?
- Задача приблизительного подсчета числа вхождений. Unbiased Sketch. Рассмотрим алгоритм: выберем случайную хеш-функцию $h: U\to \{0,1, \ldots, m-1\}$ из универсального семейства, а также случайную знаковую функцию $s: U \to \{-1,1\}$. Заведем счетчик $cnt[0\ldots m-1]$ и в качестве операцими $update(x)$ будем делать $cnt[h(x)]$ += s(x), а в качестве $query(x)$ будем возвращать $cnt[h(x)]\cdot s(x)$. Пусть выполнено $n$ запросов $update$. Обозначим как $a(x)$ количество вхождений числа $x$. Чему равно $E[query(x)]$?
- В условиях предыдущей задачи докажите, что $D[query(x)] \le \frac{1}{m}\sum_y a(y)^2$.
- В условиях предыдущих двух задач обозначим как $\lVert a \rVert_2 = \sqrt{\sum_x a(x)^2}$. Оцените $P(|query(x) - a(x)| > \varepsilon \lVert a \rVert_2)$.
- CountSketch В предыдущих трех задачах, чтобы лучше оценить количество, будем использовать несколько хеш-функций. Пусть мы используем $r$ хеш-функций, для каждой свой массив $cnt_i$, в качестве ответа на запрос будем выдавать $median(cnt_i[h_i(x)])$. Какое $r$ необходимо выбрать, чтобы выполнялось $P(|query(x) - a(x)| > \varepsilon \lVert a \rVert_2) < \delta$?
- Сравните оценки по времени, памяти и точности для CountMin и CountSketch. Сделайте вывод, когда какой из них лучше.
- Поиск $k$ самых частых. Используем тот или иной апроксимационный алгоритм (CountMin или CountSketch), мы хотим найти $k$ самых частых элементов в последовательности $a_1, \ldots, a_n$. Будем поддерживать $set$ из $k$ самых частых, упорядоченный по оценке на число их вхождений. Рассматривая очередной элемент, добавляем его в set, если его оценка на число вхождений становится больше, чем у самого редкого в $set$-е. Оцените вероятность, что для всех $x$ в $set$-е в конце выполнено $a(x) \ge (1-\varepsilon)a(y)$, где $y$ - это $k$-й по частоте встречаемости элемент.
- Изменим алгоритм из предыдущего задания, будем вместо $k$ хранить $2k$ элементов, а в конце оставим $k$ из них. Как изменится вероятность?
- Оцените зависимость вероятности из предыдущих двух заданий от $c$, если вместо $k$ хранится $ck$ элементов, а в конце оставим $k$ из них.
- Обозначим как $BP(n)$ время умножения булевых матриц размера $n \times n$ над $\vee, \wedge$. Обозначим как $MM(n)$ время умножения целочисленных матриц размера $n \times n$ над $+, \times$. Докажите, что $BP(n) = O(MM(n))$.
- Докажите, что можно найти транзитивное замыкание графа за время $O(BP(n))$.
- Пусть $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$.
- Пусть $MM(n)=n^{2+\varepsilon}$, $\varepsilon>0$. Модифицируйте алгоритм построения BPWM, чтобы он работал за $MM(n) \log n$. Почему эта идея не сработает, если $MM(n) = O(n^2)$?
- Докажите лемму с лекции про то, что если в урне $n$ шаров, из которых $w$ белых и $n/2\le wr \le n$, а событие $A$ означает, что из $r$ наугад выбранных из урны шаров оказался ровно один белый, то $P(A) \ge 1/2e$.
- Сохраняется ли вероятность из предыдущего задания, если шары после вытаскивания возвращаются в урну? Если нет, то можно ли получить аналогичную оценку?
- Как воспользоваться алгоритмом построения BPWM для поиска кратчайших путей между всеми вершинами в графе?
- Нижняя оценка на сумму длин путей. Докажите, что можно построить граф, в котором $\Omega(n^2)$ пар вершин, расстояние между которыми $\Omega(n)$.
- Дерево Кинг. Дано взвешенное дерево $T$. Запустим на дереве $T$ алгоритм Борувки, когда множество вершин $S$ объединяется в новую вершину $s$ для каждой вершины из $u$ добавим ребро из $u$ в $s$ с весом, равным минимальному весу ребра, инцидентного $u$ на этом шаге (того ребра, которое выбирает алгоритм Борувки). Докажите, что задача максимума на пути между листьями в полученном дереве эквивалентна задаче максимума на пути в исходном дереве $T$.
- Рассмотрим ветвящееся дерево (у каждой внутренней вершины хотя бы два сына, все листья на одном уровне), пусть в нем $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}$.
- В условиях предыдущей задачи докажите, что $\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$.
- Докажите, что $\sum\limits_{u}\lceil\log(1+|A(u)|)\rceil = O(n + m)$.
- Готовимся к алгоритму линейной верификации MST. Введем операцию на множествах целых чисел: $A \downarrow B = \{b \in B | \exists a \in A : a < b \mbox{ and there is no } b′ \in B \mbox{ with } a < b′ < b\}$. Докажите, что $A\downarrow B \subset B$, $|A \downarrow B| \le |A|$, $(A\cup B)\downarrow C = (A \downarrow C) \cup (B \downarrow C)$, $A \downarrow (B \cup C) \subset (A \downarrow B) \cup (A \downarrow C)$.
- Докажите, что если $A \downarrow B = \varnothing$, то $A \downarrow C = A \downarrow (C \setminus B)$.
- Докажите, что если $A \downarrow B \subset C \subset B$, то $A \downarrow B = A \downarrow C$.
- Докажите, что если $\sup(B \cap C) < \inf(B \setminus C)$, то $A \downarrow (B \cap C) = (A \downarrow B) \cap C$ (будем считать, что $\sup\varnothing = -\infty$, $\inf\varnothing = +\infty$).
- Докажите, что если $A \subset B$, то $A \downarrow C = A \downarrow (B \downarrow C)$.
- Будем хранить множество чисел от 0 до $w-1$, где $w$ - размер машинного слова, как битовую маску. Докажите, что если $A$ задается маской $a$, а $B$ задается маской $b$, то $A \downarrow B$ задается маской $b\&(\sim(a|b){\verb!^!}(a+(a|\sim b)))$.
- Обозначим как $d(u)$ глубину вершины $u$. Обозначим как $w(v)$ вес ребра из $v$ в родителя. Обозначим как $p^j(u)$ вершину, которая получается из $u$ переходом $j$ раз к родителю. Обозначим как $M_v = \{j\,|\,1 \le j \le d(v): w(p^j(v)) > w(p^k(v)) \mbox{ for all } k = j + 1, \ldots, d(v)\}$. Пусть $u$ - предок $v$. Докажите, что максимальный вес ребра на пути из $u$ в $v$ находится на ребре в родителя из вершины $p^j(v)$, где $j$ - единственный элемент множества $\{d(u)\}\downarrow M_v$.
- Обозначим как $D_v = \{d(u) | \mbox{ there is a query path $uw$ that contains $v$}\}$. Пусть $S_v = D_v \downarrow M_v$. Докажите, что в условии предыдущей задачи $\{d(u)\}\downarrow M_v = \{d(u)\} \downarrow S_v$.
- Предложите алгоритм подсчета $D_v$ для всех вершин дерева за $O(n + m)$ (считайте, что битовые операции выполняются за $O(1)$.
- Известно, что у учителя есть $2^k$ яблок для некоторого целого неотрицательного $k$. На глазах у студентов он съедает одно яблоко, а остальное раздает ученикам А и В, чтобы ни один из них не видел, сколько получает другой. А и В не знают числа $k$. Они могут показать друг другу по одному знаку из трёх возможных: почесать голову правой, левой или обеими руками. К удивлению учителя, ученики всегда знают, кто получил больше яблок или что учитель съел единственное яблоко сам. Как такое возможно?
- Петя хочет упростить алгоритм Каргера-Штайна. Он запускает алгоритм Каргера (стягивание по случайному ребру), пока количество вершин не станет равно $t$, а затем запускает алгоритм за $t^3$ поиска минимального глобального разреза. Затем он повторяет алгоритм, пока вероятность успеха не составит хотя бы $1/2$. Какое значение $t$ необходимо выбрать, чтобы минимизировать время работы получившегося алгоритма? Какое будет время работы?
- Докажите, что если в полном двоичном дереве высоты $h$ каждое ребро удаляется с вероятностью $1/2$, то путь от корня до листа сохраняется с вероятностью $\Theta(1/h)$.
- Обобщите предыдущее задание, если ребро удаляется с вероятностью $p$.
- С учетом предыдущего задания модифицируйте алгоритм Каргера-Штайна, чтобы разветвляться когда накопленная вероятность ошибки достигнет $p$. Найдите зависимость времени работы от $p$, какое значение $p$ оптимально выбрать?
- Назовем разрез $\alpha$-оптимальным, если его размер не больше $\alpha C_{min}$, где $C_{min}$ - минимальный разрез. Оцените вероятность, что один запуск алгоритма Каргера (без разветвлений) найдет $\alpha$-оптимальный разрез (в зависимости от $\alpha$).
- Докажите, что в графе не больше $n\choose 2$ различных минимальных глобальных разрезов.
- Сформулируйте и докажите аналогичный предыдущему заданию результат для $\alpha$-оптимальных разрезов.
- Докажите, что для полинома $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$ корней.
- Покажите, что требование, что $F$ поле в предыдущей задаче является существенным, приведите пример полинома степени $d$ над кольцом, которое не является полем, имеющего более $d$ корней.
- Покажите, что в определении PRAS можно заменить константу $3/4$ в требовании, что вероятность попасть в интервал $[1-\varepsilon;1+\varepsilon]$ должна быть $3/4$, на любое другое число, строго большее $1/2$.
- Можно ли в предыдущем задании заменить $1/2$ на $0$?
- Можно ли в решении задания 73 брать среднее значение в качестве оценки?
- Рассмотрим формулу в ДНФ. Обозначим как $t$ количество пар $($терм$,$ удовлетворяющее этот терм назначение переменных$)$. Выберем случайно терм, где вероятность выбрать терм пропорциональна числу удовлетворяющих этот терм назначений. Выберем случайное назначение $a$, удовлетворяющее этот терм. Рассмотрим случайную величину $X = t/cov(a)$, где $cov(a)$ - число термов, удовлетворенных назначением $a$. Докажите, что $EX = Y$, где $Y$ - число удовлетворяющих назначений заданной формулы.
- На базе предыдущего задания предложите альтернативный алгоритм апроксимации числа удовлетворяющих назначений ДНФ.
- Рандомизированный алгоритм для 2SAT. Рассмотрим следующий алгоритм решения задачи удовлетворимости булевой формулы в 2КНФ с $n$ переменными. Выберем случайное значение каждой переменной. Если формула не удовлетворена, выберем случайный не удовлетворенный клоз и инвертируем значение случайной переменной в нем. Докажите, что если удовлетворяющее назначение существует, оно будет найдено за $O(n^2)$ шагов. Указание: зафиксируйте любое удовлетворяющее формулу назначение и рассмотрите задачу как случайное блуждание по прямой, где координата - это число переменных, значение которых совпадает с значением в выбранном назначении.
- Почему алгоритм из предыдущего задания не работает для 3SAT?
- Докажите, что оценку из задания 78 нельзя улучшить: предложите формулу, для которой в среднем понадобится $\Omega(n^2)$ случайных шагов для поиска удовлетворяющего назначения.
- Предложите аналогичный заданию 78 алгоритм поиска раскраски графа в два цвета.
- Почему алгоритм из предыдущего задания не работает для поиска раскраски графа в три цвета?