Как решать вступительный экзамен в Школу анализа данных Яндекса14.07.2015 16:18

Лето — время вступительных экзаменов. Прямо сейчас продолжается отбор в Школу анализа данных Яндекса. В ШАД преподают машинное обучение, компьютерное зрение, анализ текстов на естественном языке и другие направления современной Computer Science. Два года студенты изучают предметы, которые обычно не входят в университетские программы, хотя пользуются огромным спросом как в науке, так и в индустрии. Учиться можно не только в Москве — у Школы открыты филиалы в Екатеринбурге, Минске, Киеве, Новосибирске, Санкт-Петербурге. Есть и заочное отделение, на котором можно обучаться, смотря видеолекции и переписываясь с преподавателями московской Школы по почте.

Но для того, чтобы поступить в ШАД, нужно успешно пройти три этапа — заполнить анкету на сайте, сдать вступительный экзамен и прийти на собеседование. Ежегодно в ШАД поступают старшекурсники, выпускники и аспиранты МГУ, МФТИ, ВШЭ, ИТМО, СПбГУ, УрФУ, НГУ и не все они справляются с нашими испытаниями. В этом году мы получили анкеты от 3500 человек, 1000 из которых была допущена к экзамену, и только 350 сдали его успешно.

Для тех, кто хочет попробовать себя и понять, на что он способен, мы подготовили разбор вступительного экзамена этого года. С вариантом, который мы выбрали для вас, справились 56% решавших его. В этой таблице вы можете увидеть, сколько человек смогли решить каждое из заданий в нём.

Задание	1	2	3	4	5	6	7	8
Решило	57%	68%	40%	35%	29%	12%	20%	6%

Но для начала хотелось бы объяснить, что мы проверяем экзаменом и как подходим к его составлению. В самые первые годы существования ШАД письменного экзамена не было, так как заявок было ещё немного, и со всеми, кто прошёл онлайн-тестирование, получалось поговорить лично. Но зато и собеседования были дольше; некоторые выпускники вспоминают, как с ними беседовали по шесть часов, предлагая много сложных задач. Потом поступающих стало больше — и в 2012 году появился письменный экзамен.
Созданием варианта занимаются кураторы московской ШАД, одним из которых я являюсь; с подбором заданий им помогают коллеги из филиалов. Число задач в варианте не сильно изменилось за эти четыре года: сначала их было семь, а в прошлом году стало восемь. В каждом варианте есть задачи по математике (от пяти до семи) и задачи на алгоритмы (одна или две).

Что касается математики, мы, конечно же, проверяем, владеют ли поступающие основными разделами программы: алгеброй, математическим анализом, комбинаторикой и теорией вероятностей. Но нам важны не те знания, что достигаются зубрёжкой и забываются через неделю после зачёта или экзамена — вроде ужасных формул из таблицы неопределённых интегралов или функции распределения Стьюдента; именно поэтому мы разрешаем поступающим брать с собой на письменный экзамен любые бумажные источники. Гораздо ценнее понимание сути происходящего, а также умение применять стандартные факты и методы в необычных ситуациях. Вычислительную сложность мы также стараемся свести к минимуму; даже и двузначные числа перемножать приходится нечасто. Так что на экзамене вы не встретите рутинных и утомительных вычислительных упражнений, а многие задания покажутся нестандартными и, может быть, даже олимпиадными.

В части, касающейся алгоритмов, мы избегаем задач, требующих знания специфических структур данных (деревьев поиска, хэш-таблиц и т.д) или алгоритмов (быстрые алгоритмы сортировки, алгоритмы поиска кратчайших путей на графах и т.д.). Кроме того, мы не требуем от поступающих написать реализацию придуманного алгоритма на каком-либо языке программирования; скорее даже наоборот — всячески от этого отговариваем. И действительно, на письменном экзамене нас больше всего интересуют не навыки программирования, а умение внятно описать алгоритм и при необходимости убедить читателя в том, что он удовлетворяет ограничениям на время работы и объём выделяемой памяти. Впрочем, решения, содержащие код на любом языке, который мы в состоянии прочесть, тоже принимаются, но их труднее проверять и, кроме того, они всё равно должны сопровождаться обоснованием корректности.

Задача 1

Найдите предел последовательности (an), для которой

Ответ

Решение

Сначала докажем, что последовательность сходится. Если an < 0, то an-1 < 0, поэтому она ограничена сверху. Сравним an и an+1.

Видим, что при an∈(-1;0) имеет место неравенство an < a(n+1), то есть последовательность возрастает. По теореме Вейерштрасса она имеет предел. Чтобы его найти, перейдём к пределу в нашем рекуррентном соотношении:

откуда предел может быть одним из чисел 0, –1 и 4. Нетрудно понять, что это 0.

Задача 2

На плоскости, замощённой одинаковыми прямоугольниками со сторонами 10 и 20 (прямоугольники примыкают сторонами), рисуют случайную окружность радиуса 4. Найдите вероятность того, что окружность имеет общие точки ровно с тремя прямоугольниками.

Ответ

Решение

Будем следить за положением центра окружности. Ясно, что можно ограничить рассмотрение внутренностью одного прямоугольника. Нетрудно видеть, что для того, чтобы окружность пересекала ровно три прямоугольника, должны выполняться два условия: (1) расстояния от центра до двух ближайших сторон прямоугольника должны быть меньше 4; (2) расстояние до ближайшей вершины прямоугольника должно быть больше 4. Зная это, мы можем изобразить множество точек, удовлетворяющих этим условиям.

Следовательно, искомая вероятность равна

Задача 3

Дима и Ваня по очереди заполняют матрицу размера 2n×2n. Цель Вани — сделать так, чтобы получившаяся в итоге матрица имела собственное значение 1, а цель Димы — помешать ему. Дима ходит первым. Есть ли у кого-нибудь из них выигрышная стратегия?

Ответ

При правильной стратегии выиграет Ваня.

Решение

Получившаяся матрица А будет иметь собственное значение 1, если матрица А — Е будет вырожденной. Добиться этого Ваня может, например, следующим образом. После того, как Дима вписал какой-то элемент aij, Ваня вписывает новый элемент aik в ту же строку таким образом, чтобы aik-δik=-(aij-δij), где δij — символ Кронекера. Тогда сумма чисел в каждой из строк матрицы A — E будет равна нулю, то есть матрица А — Е будет вырожденной.

Задача 4

Найдите определитель матрицы A=(aij), где

Ответ

Решение

Воспользуемся формулой

. Вычтем из каждой строки матрицы предыдущую, а затем из каждого столбца предыдущий. Полученная матрица будет иметь вид:

Продолжая рассуждение по индукции, убеждаемся, что определитель исходной матрицы равен определителю единичной, т.е. 1.

Задача 5

Даны два массива целых чисел a[1…n] и b[1…k], причём все элементы b различны. Требуется найти набор индексов i_1 < i_2 <… < i_k, для которого набор a[i_1],…, a[i_k] является перестановкой элементов массива b, причём разность i_k — i_1 минимально возможная. Ограничение по времени — O (nk) (но, может быть, вы сможете быстрее), по памяти — O (n).

Решение

Это можно сделать в один проход по массиву а. Каждый раз, когда мы встречаем элемент массива b, мы записываем его и его номер в специальные массивы. При этом мы поддерживаем в этих массивах отрезок I, на котором мы надеемся найти все различные элементы b. Ясно, что если очередной элемент массива а совпадает с первым элементом отрезка I, то I уже явно не может быть кратчайшим отрезком, удовлетворяющим условию задачи, и мы можем сдвинуть его левый конец. Если на очередном шаге мы понимаем, что I содержит все различные элементы b, то I — кандидат на ответ; в этом случае мы также сдвигаем его левый конец.

Оценка O (n) по памяти очевидна. Оценка O (nk) по сложности может быть обоснована следующим образом: мы всё делаем в один проход (отсюда n) и на каждом шаге должны искать элемент в массиве b (отсюда k). Ясно, что алгоритм можно улучшить: если вначале отсортировать b и использовать двоичный поиск, получим O (n log k). Если же использовать совершенное хеширование, то можно добиться сложности O (n+k).

Задача 6

В 2222 году волейбольные турниры проводят по новой системе. Говорят, что команда А превосходит команду В, если А выиграла у В или у какой-либо команды, выигравшей у В. Каждая пара команд играет по 1 разу. Ничья исключается волейбольными правилами. Чемпионом объявляют команду, превзошедшую все другие команды. (а) Докажите, что чемпион обязательно найдётся (б) Докажите, что не может быть ровно двух чемпионов.

Решение

Договоримся, что каждая команда за турнир получает очки, равные числу превзойдённых ею команд. Сначала докажем следующую простую лемму:

Лемма.Пусть команда Е не превосходит команду К. Тогда К набрала больше очков, чем Е.

Доказательство. Если Е не превосходит К, то К победила команду Е, а также все команды, которые победила команда Е.

Теперь пусть Х — команда, которую превзошла команда Е. Если Е выиграла у Х, то К также выиграла у Х. Значит, Е превосходит Х. Если же Е выиграла у команды F, которая выиграла у Х, то заметим, что К тоже выиграла у F. Значит, К выиграла у F, которая выиграла у Х, то есть К превосходит Х. Итого, К превосходит все команды, которые превзошла Е, да ещё и Е в придачу, то есть как минимум на одну команду больше, чем Е. Лемма доказана.

(а) Пусть А — команда, заработавшая максимальное число очков. Докажем, что А — чемпион. Допустим, это не так, тогда есть команда В, которую А не превзошла. По лемме получаем, что В заработала больше очков, чем А. Противоречие.

(б) Пусть у нас есть два чемпиона: А и В. Друг с другом они играли; пусть, к примеру, победила А. Так как В превосходит все другие команды (и А в частности), то В победила некоторую команду, которая выиграла у А.

Допустим для начала, что есть команды, которые победили и А, и В. Тогда можно показать, что та из них (назовём её С), которая набрала больше всего очков, и будет третьим чемпионом. В самом деле, пусть Е — команда, которую не превзошла С. Тогда, во-первых Е победила и А, и В, а во-вторых, Е заработала больше очков, чем С. Противоречие.

Пусть теперь нет команд, которые победили и А, и В. Рассмотрим множество всех таких команд, которые победили А, но проиграли В. Отметим, что оно непусто (см. выше). Среди них возьмём команду с наибольшим числом очков. Тогда пользуясь леммой мы можем установить, что эта команда является третьим чемпионом.

Задача 7

Вычислите интеграл

Ответ

Решение

Обозначим искомый интеграл через I. Сделаем замену переменной:

Отсюда

Этот интеграл уже берётся непосредственно.

Задача 8

На плоскости нарисована ломаная с n звеньями. Длина каждого звена равна 1, ориентированный угол между соседними звеньями с равной вероятностью равен α или –α. Найдите математическое ожидание квадрата расстояния от её начальной точки до конечной.

Ответ

Решение

Введём на плоскости систему координат так, чтобы первое звено ломаной было направлено вдоль оси Ох. Пусть αn — ориентированный угол между (n-1)-м звеном ломаной и первым звеном ломаной (т.е. осью Ох). Тогда α0=0, α (n+1)=αn+ξ (n+1)α, где ξn — случайная величина, принимающая с вероятностью ½ значения ±1. Отметим, что проекции на оси Ох и Оу k-го звена ломаной равны cos⁡ α (n-1) и sin⁡ α (n-1) соответственно. Тогда квадрат расстояния от начала ломаной до её конца равен

Наша задача — найти математическое ожидание этой случайной величины. Имеем:

Следовательно,

Отсюда уже нетрудно вывести ответ.