Вступительный экзамен в ШАД июнь 2014

Вступительный экзамен в ШАД 2014

Вступительный экзамен в Школу анализа данных
1 июня 2014

Экзамен длится 4 часа

Условия задач

Пусть $M\subseteq R$ - множество из $n$ элементов. Пусть, далее, $S_M=$ { $\frac{x+y}{2}|x,y\in M, x\ne y$ }. Найдите наименьшую возможную мощность множества $S_M$ (одинаковые элементы множества считаются одним элементом).
На окружности выбираются 3 случайные точки. С какой вероятностью центр окружности лежит внутри треугольника с вершинами в этих точках?
Квадратная матрица $A$ размера 9x9 над полем характеристики, отличной от 2, такова, что $A^2=E$ . Найдите ранг матрицы $E-A$ , если известно, что ранг матрицы $E+A$ равен 7.
В полукруге есть $n$ неизвестных нам точек. Разрешается задавать вопросы вида "каково расстояние от точки $X$ до ближайшей из этих точек?". Если расстояние оказывается нулевым, то точка считается угаданной. Докажите, что хотя бы одну из этих точек можно угадать не более чем за $2n+1$ вопрос.
Найдите предел $\lim_{\lambda\to+0}\displaystyle\frac{1}{\ln\lambda}\int_{\lambda}^{a}\frac{\cos x}{x}dx$
Пусть $A$ и $B$ - квадратные матрицы размера 2х2. Рассмотрим линейный оператор $F$ на пространстве матриц 2x2, действующий по правилу $F(M)=A\cdot M\cdot B$ . Матрица $A$ имеет 2 различных собственных значения $\lambda_1$ и $\lambda_2$ , а $B$ - 2 различных собственных значения $\mu_1$ и $\mu_2$ . Найдите собственные значения оператора $F$ , если (а) матрицы $A$ и $B$ - диагональные; (б) матрицы $A$ и $B$ - произвольные.
Квадратная матрица nxn заполнена натуральными числами. Предложите алгоритм, находящий два элемента этой матрицы, не лежащих ни в одной строке, ни в одном столбце, с максимально возможным произведением. Ограничение по времени - $O(n^2)$ , по памяти - $O(n)$ .
Игральную кость с $n$ гранями (и числами от 1 до $n$ на этих гранях) подбрасывают до тех пор, пока сумма выпавших очков не станет больше или равна $n$ . Все грани кости выпадают с одинаковой вероятностью. Найдите математическое ожидание числа бросков.