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