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

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

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

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

1. Определим последовательность $x_n$ начальными условиями $x_1=a$, $x_2=b$ и рекуррентной формулой $x_{n+1}=\displaystyle\frac{1}{2}(x_n+x_{n+1})$. Найдите $\lim_{n\to\infty}x_n$.
2. Рассмотрим функцию $\psi(x)=\sum_{k=1}^{\infty}\displaystyle\frac{1}{2^{2[log_2k]}}x^k$, где квадратные скобки означают целую часть числа. Найдите $\int_0^1\psi(x)\psi'(x)dx$.
3. Рассмотрим всевозможные непустые подмножества множества {1,2,3,...,n}. В каждом подмножестве перемножим числа, обратные его элементам. Потом сложим полученное $2^n-1$ число. Найдите полученную сумму.
4. Петя и Вася подбрасывают правильную монетку (вероятность выпадения орла равна 0.5). Петя подбрасывает ее n раз, а Вася - n+1. Найдите вероятность того, что у Васи орлов выпало больше, чем у Пети.
5. Дано некоторое множество положительных чисел мощности континуум. Докажите, что из него можно выбрать счетное подмножество с бесконечной суммой.
6. Дан массив из n чисел. Предложите алгоритм, позволяющий за O(n) операций определить, является ли этот массив перестановкой чисел от 1 до n. Дополнительной памяти не более O(1).
7. Пусть $A_1,A_2,...,A_n$ - конечные множества и $a_{ij}=|A_i\cap A_j|$. Докажите, что матрица $(a_{ij})_{i=1,2,...,n}^{j=1,2,...,n}$ неотрицательно определена.

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

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