Вступительный экзамен в ШАД 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 г. и Задачи вступительных экзаменов