Список заданий по продвинутым алгоритмам 2021 осень — различия между версиями
Строка 36: | Строка 36: | ||
# $O | p_{ij} = 1, r_i | C_{max}$ | # $O | p_{ij} = 1, r_i | C_{max}$ | ||
# $O2 | p_{ij} = 1, prec | \sum C_i$ | # $O2 | p_{ij} = 1, prec | \sum C_i$ | ||
+ | # Обозначим как $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)=2+\varepsion$, $\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$. | ||
+ | # Сохраняется ли вероятность из предыдущего задания, если шары после вытаскивания возвращаются в урну? Если нет, то можно ли получить аналогичную оценку? | ||
+ | # Нижняя оценка на сумму длин путей. Докажите, что можно построить граф, в котором $\Omega(n^2)$ пар вершин, расстояние между которыми $\Omega(n)$. | ||
+ | # Известно, что у учителя есть $2^k$ яблок для некоторого целого неотрицательного $k$. На глазах у студентов он съедает одно яблоко, а остальное раздает ученикам А и В, чтобы ни один из них не видел, сколько получает другой. А и В не знают числа $k$. Они могут показать друг другу по одному знаку из трёх возможных: почесать голову правой, левой или обеими руками. К удивлению учителя, ученики всегда знают, кто получил больше яблок или что учитель съел единственное яблоко сам. Как такое возможно? | ||
+ | # Вероятностный алгоритм поиска минимума некоторый функции от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $1/2$. Как найти верный ответ с вероятностью $99/100$ за полином от $n$? | ||
+ | # Вероятностный алгоритм проверки некоторого предиката от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $1/2$. Как найти верный ответ с вероятностью $99/100$ за полином от $n$? |
Версия 18:29, 14 октября 2021
- $1 | p_i=1 | L_{max}$.
- $1 | r_i, d_i=d | L_{max}$.
- $1 | prec, r_i, p_i=1 | L_{max}$.
- Рассмотрим задачу $1 | p_i = 1, d_i | -$. Докажите, что подмножества работ, которые можно выполнить, образуют семейство независимых множеств некоторого матроида.
- $1 | p_i = 1, d_i | \sum w_iU_i$. Время $O(n\log n)$.
- $1 | p_i = 1, d_i, r_i | \sum U_i$. Время - полином от $n$.
- $1 | p_i = 1, d_i, r_i | \sum w_iU_i$. Время - полином от $n$.
- $1 | p_i = p, pmtn, r_i | \sum w_iU_i$ за $O(n^{10})$.
- $1 || \sum U_i$
- $1 | r_i, p_i = p | \sum w_iC_i$ за $O(n^7)$
- Обозначение outtree означает, что граф зависимостей представляет собой исходящее дерево: каджая работа зависит не более чем от одной другой. $1 | outtree | \sum w_iC_i$
- Обозначение intree означает, что граф зависимостей представляет собой входящее дерево: от каждой работы зависит не более одной другой. $1 | intree | \sum w_iC_i$
- $P | pmtn, r_i | C_{max}$
- $P | pmtn, r_i | L_{max}$
- $Q | pmtn, r_i | C_{max}$
- $P | p_i = p, r_i, d_i | \sum C_i$ за $O(n^3 \log n)$ (бонус за $O(n^3 \log\log n)$)
- $P | p_i = 1 | \sum w_iU_i$ - доведите доказательство с пары до конца
- $P | p_i = 1 | \sum w_iC_i$
- $P | p_i = 1, pmtn | \sum w_iC_i$
- $Q | pmtn | \sum C_i$
- $Q | pmtn | \sum f_i$ (напомним, что f_i - произвольная неубывающая функция, может быть своя у каждой работы)
- $Q | pmtn | f_{max}$
- $P2 | p_i = 1, prec, r_i | \sum C_i$ за $O(n^9)$
- Сведите задачу $R|pmtn|C_{max}$ к задаче линейного программирования.
- $P|intree, p_i=1|L_{max}$
- $F | p_{ij} = 1 | \sum C_i$
- $F2 | pmtn | C_{max}$
- $F | p_{ij} = 1 | \sum U_i$
- $F | p_{ij} = 1 | \sum w_iU_i$
- $O | p_{ij} = 1 | C_{max}$
- $O | p_{ij} = 1 | \sum C_i$
- $O | p_{ij} = 1 | \sum w_iC_i$
- $O | p_{ij} = 1, d_i | -$
- $O | p_{ij} = 1 | \sum U_i$
- $O | p_{ij} = 1 | \sum w_iU_i$
- $O | p_{ij} = 1, r_i | C_{max}$
- $O2 | p_{ij} = 1, prec | \sum C_i$
- Обозначим как $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)=2+\varepsion$, $\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$.
- Сохраняется ли вероятность из предыдущего задания, если шары после вытаскивания возвращаются в урну? Если нет, то можно ли получить аналогичную оценку?
- Нижняя оценка на сумму длин путей. Докажите, что можно построить граф, в котором $\Omega(n^2)$ пар вершин, расстояние между которыми $\Omega(n)$.
- Известно, что у учителя есть $2^k$ яблок для некоторого целого неотрицательного $k$. На глазах у студентов он съедает одно яблоко, а остальное раздает ученикам А и В, чтобы ни один из них не видел, сколько получает другой. А и В не знают числа $k$. Они могут показать друг другу по одному знаку из трёх возможных: почесать голову правой, левой или обеими руками. К удивлению учителя, ученики всегда знают, кто получил больше яблок или что учитель съел единственное яблоко сам. Как такое возможно?
- Вероятностный алгоритм поиска минимума некоторый функции от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $1/2$. Как найти верный ответ с вероятностью $99/100$ за полином от $n$?
- Вероятностный алгоритм проверки некоторого предиката от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $1/2$. Как найти верный ответ с вероятностью $99/100$ за полином от $n$?