Изменения
Нет описания правки
# Пусть существует полиномиальный детерминированный алгоритм, который возвращает число совершенных паросочетаний в двудольном графе, степень каждой вершины которого равна хотя бы $\beta n$, где $0 < \beta < 1$. Докажите, что существует полиномиальный детерминированный алгоритм, который возвращает число совершенных паросочетаний в произвольном двудольном графе.
# Рассмотрим алгоритм приближения числа $\pi$. Будем генерировать точки с равномерным распределением в квадрате $1 \times 1$ и считать долю попавших в круг диаметром 1, вписанный в этот квадрат. Оцените число итераций, необходимое, чтобы приблизить $\pi$ с точностью до $\varepsilon$.
# Пусть матрица переходов эргодической марковской цепи является дважды стохастической (сумма элементов каждого столбца также равна 1). Докажите, что стационарное распределение $(1/n, 1/n, \ldots, 1/n)$.
# Пусть матрицы $A$ и $B$ имеют один и тот же собственный вектор $x$ для собственных чисел $\lambda$ и $\mu$, соответственно. Докажите, что $x$ является собственным вектором для $A+B$. Для какого собственного числа?
