211
правок
Изменения
Нет описания правки
# Докажите, что можно найти транзитивное замыкание графа за время $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$.
# Сохраняется ли вероятность из предыдущего задания, если шары после вытаскивания возвращаются в урну? Если нет, то можно ли получить аналогичную оценку?
# Докажите, что если $\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)$.# Продолжение отменилось, так как никто не дошел до этого места :(# $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$ - доведите доказательство с пары до конца# $F | p_{ij} = 1 | \sum C_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$
