27 мая 2017

1. За время обучения в ШАД Михаил $20$ раз решал задачи классификации. В каждой задаче он использовал ансамбль из пяти различных классификаторов, причем никакую пару классификаторов он не применял более одного раза. Каково минимально возможное число известных Михаилу классификаторов?
   Решение
   Пусть $k$ — количество классификаторов. Тогда все возможные использования классификаторов можно представить в виде булевой матрицы $20\times k$, в которой элемент $c_{ij}$ равен $1$, если для решения $i$-й задачи классификации используется $j$-й классификатор. По условию задачи в каждой строке такой матрицы должно быть ровно $5$ единиц, а любая пара единиц $(j_1,j_2)$ может встречаться только в одной строке. Нетрудно понять, что $k \geqslant 21$. В самом деле, в каждой строке присутствует $\frac{5\cdot 4}{2} = 10$ уникальных пар классификаторов. Значит, число различных пар классификаторов, которые применялись для решения задач, равно $10\cdot 20 = 200$. С другой стороны, общее число пар классификаторов равно $\frac{k(k-1)}{2}$. Очевидно, должно выполняться условие $200 \leqslant \frac{k(k-1)}{2}$. Следовательно, $k \geqslant 21$. Приведем пример матрицы $21\times 21$, у которой любая из подматриц $20\times 21$ удовлетворяет условию задачи: $$\begin{matrix} 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&1&1&1&1\\ 0&0&0&0&0&0&0&0&0&0&0&0&1&1&1&1&0&0&0&0&1\\ 0&0&0&0&0&0&0&0&1&1&1&1&0&0&0&0&0&0&0&0&1\\ 0&0&0&0&1&1&1&1&0&0&0&0&0&0&0&0&0&0&0&0&1\\ 1&1&1&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1\\ 0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&1&0\\ 0&0&1&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&0&1&0\\ 0&1&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&0&0&1&0\\ 1&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&0&0&0&1&0\\ 1&0&0&0&0&1&0&0&0&0&1&0&0&0&0&1&0&0&1&0&0\\ 0&1&0&0&1&0&0&0&0&0&0&1&0&0&1&0&0&0&1&0&0\\ 0&0&1&0&0&0&0&1&1&0&0&0&0&1&0&0&0&0&1&0&0\\ 0&0&0&1&0&0&1&0&0&1&0&0&1&0&0&0&0&0&1&0&0\\ 0&0&1&0&1&0&0&0&0&1&0&0&0&0&0&1&0&1&0&0&0\\ 0&0&0&1&0&1&0&0&1&0&0&0&0&0&1&0&0&1&0&0&0\\ 1&0&0&0&0&0&1&0&0&0&0&1&0&1&0&0&0&1&0&0&0\\ 0&1&0&0&0&0&0&1&0&0&1&0&1&0&0&0&0&1&0&0&0\\ 0&1&0&0&0&0&1&0&1&0&0&0&0&0&0&1&1&0&0&0&0\\ 1&0&0&0&0&0&0&1&0&1&0&0&0&0&1&0&1&0&0&0&0\\ 0&0&0&1&1&0&0&0&0&0&1&0&0&1&0&0&1&0&0&0&0\\ 0&0&1&0&0&1&0&0&0&0&0&1&1&0&0&0&1&0&0&0&0 \end{matrix}$$ Построить такую матрицу на удивление нетрудно. Пусть изначально у нас все нули. Идем по матрице справа налево и сверху вниз и ставим $1$, если мы можем это сделать (то есть если такой пары еще нет; для первой единицы в строке — если она еще не образует все возможные пары).
   Ответ
   $21$.
2. Существует ли скалярное произведение на пространстве матриц $n\times n\; (n>1)$, относительно которого матрица из всех единиц была бы ортогональна любой верхнетреугольной матрице?
   Решение
   Пространство будет иметь размерность $n^2$ (грубо говоря, вытянем все столбцы в один). Выберем базис следующим образом:

   • $n^2-1$ матриц, у которых на $i,j$ месте $1$, на остальных $0$, $i,j \in \overline{1,n}, (i,j)\neq(n,1)$;
   • одна матрица — матрица из всех едениц.

   Занумеруем векторы базиса следующим образом: матрица из всех единиц будет иметь номер $n^2-n$, остальные векторы $(i-1)\cdot n+j$, где $i$ и $j$ — позиция ненулевого элемента. В таком базисе у верхнетреугольных матриц координата c номером $n^2-n$ будет всегда нулевой. Из формулы скалярного произведения $$<a,b>=\sum_{i=1}^{n^2}a_ib_i,$$ $a_i,b_i$ — координаты в выбранном базисе, следует, что еденичная матрица ортогональна любой верхнетреугольной матрице.
   Ответ
   Существует.
3. Найдите сумму $\sum\limits_{k=0}^\infty (-1)^k \frac{(k+1)^2}{k!}$.
   Решение
   $$\sum\limits_{k=0}^\infty (-1)^k \frac{(k+1)^2}{k!}=\sum\limits_{k=0}^\infty(-1)^k\frac{k^2}{k!}+\sum\limits_{k=0}^\infty (-1)^k\frac{2k}{k!}+\sum\limits_{k=0}^\infty(-1)^k \frac{1}{k!}=(*)$$

   1. $$\sum\limits_{k=0}^\infty(-1)^k\frac{k^2}{k!}=\sum\limits_{k=1}^\infty(-1)^k\frac{k}{(k-1)!}=\sum\limits_{k=1}^\infty(-1)^k\frac{k-1+1}{(k-1)!}=$$ $$=\sum\limits_{k=2}^\infty(-1)^k\frac{1}{(k-2)!}+\sum\limits_{k=1}^\infty(-1)^k\frac{1}{(k-1)!}=$$ $$(-1)^2\sum\limits_{l=0}^\infty(-1)^l\frac{1}{l!}+(-1)\sum\limits_{l=0}^\infty(-1)^l\frac{1}{l!}=0.$$
   2. $$=\sum\limits_{k=0}^\infty (-1)^k\frac{2k}{k!}=2\sum\limits_{k=1}^\infty (-1)^k\frac{1}{(k-1)!}=-2\sum\limits_{l=0}^\infty (-1)^l\frac{1}{l!}=-\frac{2}{e}.$$

   $$(*)=-\frac{2}{e}+\frac{1}{e}=-\frac{1}{e}.$$
   Ответ
   $-\dfrac{1}{e}$.
4. Вася поставил учиться две нейронных сети, каждую на своем GPU, и отправился спать. Времена обучения сетей независимы и равномерно распределены на отрезке $[1;3]$ (часов). Через время $t$ сервер упал и оказалось, что лишь одна сеть успела доучиться. С какой вероятностью $t \leqslant \frac32$? Считайте, что время падения сервера тоже равномерно распределено на отрезке $[1;3]$.
5. Докажите, что для произвольного $a_0 \in (0;2\pi)$ последовательность, заданная условием $$a_{n+1} = \int\limits_0^{a_n} \left( 1 + \frac14 \cos^{2n+1} t \right) dt,$$ имеет предел и найдите его.
6. Пусть $X$ — случайная величина, принимающая значения на отрезке $[0;1]$. Пусть также $m$ — медиана $X$. Рассмотрим бинаризацию этой величины $$\beta (X) = \begin{cases}1,& \textrm{при }X \geqslant m;\\0,& \text{иначе.}\end{cases}$$ Верно ли, что дисперсия $\beta (X)$ не меньше дисперсии $X$? А если $X$ непрерывна?
   Под медианой здесь имеется ввиду число $m$, для которого $P\{X \leqslant m\} = P\{X \geqslant m\}$.
7. Все числа от $1$ до $n=2^k - 1$ записаны неизвестным нам образом в полном бинарном дереве высоты $k$. Будем говорить, что число $t$ лежит между числами $i$ и $j$ в этом дереве, если при удалении $t$ из дерева $i$ и $j$ оказываются в разных компонентах. Предложите алгоритм, определяющий, что за число находится в корне дерева за $O(n \log n)$ операций с помощью запросов вида «Лежит ли $t$ между $i$ и $j$?».
8. В пространстве $\mathbb{R} [x,y]$ многочленов с действительными коэффициентами от переменных $x$ и $y$ действует оператор $y \frac{\partial}{\partial x} + x \frac{\partial}{\partial y}$.
   (a) Докажите, что каждое целое число является его собственным значением.
   (b) Найдите все его собственные значения. Является ли он диагонализуемым?