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

Вступительный экзамен в Школу анализа данных
2013 год

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

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

1. Последовательность {\(x_n\)}\(_{n=0}^{+\infty}\) задана реккурентным соотношением: \(x_0=0\), \(x_1=1\), \(x_{n+1}=\displaystyle\frac{x_n+nx_{n-1}}{n+1}\). Покажите, что данная последовательность сходится, и найдите ее предел.
2. Имеется 100 некоторых подмножеств множества {0, 1, …, 9}. Докажите, что среди них найдется два подмножества, у которых симметрическая разность имеет мощность не более двух.
3. На единичной окружности {\(x^2+y^2=1\)} выбирается случайная точка P (из равномерного распределения). В единичном круге {\(x^2+y^2\le1\)} выбирается случайная точка Q (также из равномерного распределения). Пусть R – прямоугольник со сторонами, параллельными осям координат и диагональю PQ. Какова вероятность того, что весь прямоугольник лежит в единичном круге?
4. Пусть \(f\) – положительная непрерывная функция на \(R\), причем \(\int_{-\infty}^{+\infty}f(x)dx=1\). Пусть \(\alpha\in(0,1)\), а интервал \([a,b]\) – это интервал минимальной длины из тех, для которых \(\int_{a}^{b}f(x)dx=\alpha\). Покажите, что \(f(a)=f(b)\).
5. Дана матрица \(M\) размера nxn, где \(m_{ij}=a_ia_j\) при \(i\ne j\) и \(m_{ij}=a_i^2+k\), \(i,j=1,…,n\). Найдите определитель матрицы \(M\).
6. Задана битовая матрица nxn, с элементами 0 и 1 (каждый элемент матрицы занимает один бит памяти). Назовем строку (столбец) исходной матрицы плохой (плохим), если в нем встречается хотя бы один ноль. Необходимо в исходной матрице занулить все плохие строки и столбцы. Предложите алгоритм, решающий эту задачу за O(1) дополнительной памяти и оцените его временную сложность.
7. Рассмотрим линейное пространство многочленов на R  от двух переменных степени не выше 2013. Рассмотрим его подпространство V, образованное всеми многочленами \(f\), для которых криволинейный интеграл первого рода \(\oint_{\{x^2+y^2=r^2\}}f(x,y)ds=0\), причем для любого r. Найдите размерность подпространства V.

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

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