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

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

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

1. Докажите, что любая квадратная вещественная матрица является суммой двух обратимых.
2. Может ли непрерывная на всей числовой прямой функция принимать каждое значение (а) дважды? (б) трижды?
3. Каждая из случайных величин X и Y принимает лишь два значения, причем Cov(X,Y) = 0. Докажите, что X и Y независимы.
4. Все ребра неориентированного ациклического графа покрашены в два цвета: красный и синий. Предложите алгоритм, находящий длину максимального пути, в котором любые два соседних ребра разного цвета. Ограничение по времени – О(V+E), где V – число вершин графа, E – число его ребер. Сколько дополнительной памяти требуется вашему алгоритму?
5. Пусть \(\xi,\eta,\lambda\) – независимые случайные величины, равномерно распределенные на отрезке [0;1], а \(t\) – фиксированное число. Найдите \(P\){\(\xi+\eta<t\lambda\)}.
6.  В пространстве многочленов с действительными коэффициентами степени не выше n задана квадратичная форма \(Q(f)=f(1)\cdot f(2)\). Найдите ее сигнатуру (число единиц и минус единиц в нормальном виде).
7. Найдите предел последовательности \(\lim_{n\to\infty}\int_{0}^{1}e^{\{nx\}}x^{2016}dx\), где {t} означает дробную часть числа t (например, {-2/3}={4/3}=1/3).
8. а) Докажите, что во множестве отрезков \(\Lambda=\{[i,j]|i,j=1,…,n,i<j\}\) можно выбрать подмножество \(\Sigma\), содержащее \(O(nlogn)\) отрезков так, чтобы любой отрезок из \(\Lambda\) представлялся в виде объединения не более двух отрезков из \(\Sigma\). б) Докажите, что эта оценка точна, то есть подмножество \(\Sigma\subseteq\Lambda\), удовлетворяющее условиям, должно содержать \(\Omega(nlogn)\) отрезков.

Все материалы для подготовки

смотрите еще Контрольная работа от Яндекс, март 2015 г. и Задачи вступительных экзаменов