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

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

Вариант 1

1. Найдите $\prod\limits_{k= 1}^{\infty}\cos(x\cdot2^{-k})$
2. Дана матрица $A$ размера $n$ x $n$, где $a_{ij}=(i-j)^2$, $i,j=1,...,n$. Найдите ранг матрицы $A$.
3. Имеется множество $A=${$1,2,3,...,256$}. Найдите размер максимального по мощности подмножества $A'\subset A$, такого, что $A'$ не содержит элементов $x,y$, таких, что $x=2y$.
4. На окружности случайно выбирается $n$ точек. Найдите вероятность того, что все они принадлежат некоторой полуокружности.
5. Назовем двумерный массив действительных чисел $A[1..n][1..n]$ возрастающим, если для любых $k, l$ $A[k][l]\ge A[i][j]$, $i\le k, j\le l$. Задача поиска в квадратном возрастающем массиве формулируется так: для заданного возрастающего массива $A[1..n][1..n]$ и некоторого числа $X$ определить, встречается ли число $X$ в массиве $A$. Покажите, что не существует алгоритма, решающего эту задачу менее чем за $n$ сравнений.
6. У линейного преобразования $n$-мерного пространства существует $n+1$ собственных векторов, таких, что любые $n$ из них линейно независимы. Найдите всевозможные матрицы, которые могли бы задавать такое преобразование.
7. Найдите сумму ряда $\sum\limits_{n=1}^{\infty}\displaystyle\frac{f(n)}{n(n+1)}$, где $f(n)$-количество единиц в двоичном представлении числа $n$.

Вариант 2

1. Последовательность {$a_n$}$_{n=0}^{\infty}$ определена рекурсивно $a_0=1$, $a_{n+1}=\displaystyle\frac{a_n}{1+n\cdot a_n}$. Найдите формулу общего члена последовательности.
2. Дано множество $A=${$1,2,...,n$}. Среди всех его подмножеств равновероятно выбирается $k$ его подмножеств. Найдите вероятность того, что $A_1\cap A_2\cap...\cap A_n=\emptyset$
3. Дан массив длины $n$ из нулей и единиц. Найдите в нем подмассив максимальной длины, в котором количество единиц равно количеству нулей. Ограничения: $O(n)$ по времени, $O(n)$ по дополнительной памяти.
4. Пусть $\int_{0}^{2\pi}\cos(x)\cdot\cos(2x)...\cos(mx)dx$. Для каких $m\in[1,10]$ $I_m\ne0$?
5. Дан неориентированный граф $G$ без петель. Пронумеруем все его вершины. Матрица смежности графа $G$ с конечным числом вершин $n$ (пронумерованных числами от 1 до $n$) - это квадратная матрица $A$ размера $n$, в которой значение элемента $a_{ij}$ равно числу ребер из $i$-ой вершины графа в $j$-ю вершину. Докажите, что матрица $A$ имеет отрицательное собственное значение.
6. Рассмотрим бесконечный двумерный массив {$a_{ij}$}$_{i,j=1}^{\infty}$, состоящий из натуральных чисел, причем каждое число встречается в массиве ровно 8 раз. Докажите, что $\exists (m,n): a_{mn}>mn$.
7. Дана матрица из нулей и единиц, причем для каждой строки матрицы верно следующее: если в строке есть единицы, то они все идут подряд (неразрывной группой из единиц). Докажите, что определитель такой матрицы может быть равен только $\pm1$ или $0$.

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