Вступительный экзамен в ШАД 2013
Условия задач
Вариант 1
- Найдите \(\prod\limits_{k= 1}^{\infty}\cos(x\cdot2^{-k})\)
- Дана матрица \(A\) размера \(n\) x \(n\), где \(a_{ij}=(i-j)^2\), \(i,j=1,…,n\). Найдите ранг матрицы \(A\).
- Имеется множество \(A=\){\(1,2,3,…,256\)}. Найдите размер максимального по мощности подмножества \(A’\subset A\), такого, что \(A’\) не содержит элементов \(x,y\), таких, что \(x=2y\).
- На окружности случайно выбирается \(n\) точек. Найдите вероятность того, что все они принадлежат некоторой полуокружности.
- Назовем двумерный массив действительных чисел \(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\) сравнений.
- У линейного преобразования \(n\)-мерного пространства существует \(n+1\) собственных векторов, таких, что любые \(n\) из них линейно независимы. Найдите всевозможные матрицы, которые могли бы задавать такое преобразование.
- Найдите сумму ряда \(\sum\limits_{n=1}^{\infty}\displaystyle\frac{f(n)}{n(n+1)}\), где \(f(n)\)-количество единиц в двоичном представлении числа \(n\).
Вариант 2
- Последовательность {\(a_n\)}\(_{n=0}^{\infty}\) определена рекурсивно \(a_0=1\), \(a_{n+1}=\displaystyle\frac{a_n}{1+n\cdot a_n}\). Найдите формулу общего члена последовательности.
- Дано множество \(A=\){\(1,2,…,n\)}. Среди всех его подмножеств равновероятно выбирается \(k\) его подмножеств. Найдите вероятность того, что \(A_1\cap A_2\cap…\cap A_n=\emptyset\)
- Дан массив длины \(n\) из нулей и единиц. Найдите в нем подмассив максимальной длины, в котором количество единиц равно количеству нулей. Ограничения: \(O(n)\) по времени, \(O(n)\) по дополнительной памяти.
- Пусть \(\int_{0}^{2\pi}\cos(x)\cdot\cos(2x)…\cos(mx)dx\). Для каких \(m\in[1,10]\) \(I_m\ne0\)?
- Дан неориентированный граф \(G\) без петель. Пронумеруем все его вершины. Матрица смежности графа \(G\) с конечным числом вершин \(n\) (пронумерованных числами от 1 до \(n\)) – это квадратная матрица \(A\) размера \(n\), в которой значение элемента \(a_{ij}\) равно числу ребер из \(i\)-ой вершины графа в \(j\)-ю вершину. Докажите, что матрица \(A\) имеет отрицательное собственное значение.
- Рассмотрим бесконечный двумерный массив {\(a_{ij}\)}\(_{i,j=1}^{\infty}\), состоящий из натуральных чисел, причем каждое число встречается в массиве ровно 8 раз. Докажите, что \(\exists (m,n): a_{mn}>mn\).
- Дана матрица из нулей и единиц, причем для каждой строки матрицы верно следующее: если в строке есть единицы, то они все идут подряд (неразрывной группой из единиц). Докажите, что определитель такой матрицы может быть равен только \(\pm1\) или \(0\).
смотрите еще Вступительные в ШАД 2012 и Контрольная работа от Яндекс, март 2015 г. и Задачи вступительных экзаменов