244
правки
Изменения
Нет описания правки
# Докажите, что можно найти транзитивное замыкание графа за время $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$.
# Сохраняется ли вероятность из предыдущего задания, если шары после вытаскивания возвращаются в урну? Если нет, то можно ли получить аналогичную оценку?
