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

Вступительный экзамен в Школу анализа данных
3 июня 2017

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

1. Пусть $x$ и $y$ - два ненулевых вектора из $R^n$. Верно ли, что найдется симметричная матрица $A$, для которой $y=Ax$?
2. Непрерывная функция $f(x)$ такова, что $f(0)=f(2)$. Докажите, что для какого-то $x\in[0;2]$ имеет место равенство $f(x)=f(x-1)$.
3. Из равномерного распределения на отрезке $[0;1]$ независимо выбираются две точки $x$ и $y$. При каких $a$ события $max(1-2x,y)<a$ и $max(1-2y,x)<a$ независимы?
4. В компании "Тындекс" у каждого сотрудника не менее 50 знакомых. Оказалось, что есть два сотрудника, знакомые друг с другом лишь через 9 рукопожатий (то есть кратчайшая соединяющая из цепочка из попарно знакомых людей содержит 8 промежуточных людей). Докажите, что в этой компании хотя бы 200 сотрудников.
5. Квадратная матрица $A$ размера nxn имеет различные собственные значения $\lambda_1,...,\lambda_n$. Найдите все собственные значения (в том числе комплексные) матрицы $\begin{bmatrix}0& -A\\A&0\end{bmatrix}$.
6. Вы - воин Света, и сегодня вам нужно победить толпу из $n$ гоблинов, каждый из которых изначально имеет $h_i$ единиц жизни ($1\le i\le n, h_i\in Z$, $0<h_i<H$). Боретесь с гоблинами вы с помощью специального магического посоха. Если ударить таким посохом по гоблину, тот сразу же теряет $p$ единиц жизни, а все остальные гоблины в толпе теряют $q$ единиц каждый (таковы магические свойства посоха). Гоблин считается побежденным, если после очередного удара его здоровье становится меньше или равно нулю. Обычная борьба с нечистью давно вам приелась, и чтобы внести разнообразие в сегодняшнюю битву, вы решили победить всех гоблинов, сделав минимально возможное число ударов посохом. Предложите алгоритм нахождения этого числа ударов. Ваш алгоритм должен иметь асимптотику по времени $O(nlogn)$, затраты по памяти - $O(n)$.
7. Пусть $A$ и $B$ - две случайных булевых матрицы nxn, у которых каждый элемент равен 1 с вероятностью $p$ (значения различных элементов не зависят друг от друга). Сколько в среднем единиц будет в их произведении, если сложение и умножение происходят по модулю 2?
8. Исследуйте на сходимость (абсолютную и условную) ряд $\sum_{k=1}^{\infty}a_k$, где $a_k=\int_{0}^{\frac{\sin k}{k}}\displaystyle\frac{\sin t}{t}dt$

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

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