Компания
297,99
рейтинг
14 июля 2015 в 16:15

Разработка → Как решать вступительный экзамен в Школу анализа данных Яндекса

Лето — время вступительных экзаменов. Прямо сейчас завершается отбор в Школу анализа данных Яндекса — идут собеседования для тех, кто уже сдал экзамен. В ШАД преподают машинное обучение, компьютерное зрение, анализ текстов на естественном языке и другие направления современной 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), для которой
Ответ
0

Решение
Сначала докажем, что последовательность сходится. Если 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 в ту же строку таким образом, чтобы aikik=-(aijij), где δijсимвол Кронекера. Тогда сумма чисел в каждой из строк матрицы A – E будет равна нулю, то есть матрица А – Е будет вырожденной.


Задача 4


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

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

Продолжая рассуждение по индукции, убеждаемся, что определитель исходной матрицы равен определителю единичной, т.е. 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/2 значения ±1. Отметим, что проекции на оси Ох и Оу k-го звена ломаной равны cos α(n-1) и sin α(n-1) соответственно. Тогда квадрат расстояния от начала ломаной до её конца равен

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


Пользуясь тем, что sin α0 = 0 и cos(ξkα)=cos α (в силу нечётности косинуса), по индукции получаем, что M(cos αk)=coskα, M(sin αk)=0. Далее найдём математическое ожидание произведений. Пусть m≥k. С помощью индукции по (m – k) можно доказать, что



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



Отсюда уже нетрудно вывести ответ.
Автор: @st-fedotov
Яндекс
рейтинг 297,99

Комментарии (42)

  • +3
    В последней задаче что-то не то. В конце (после последней формулы) у нас получается
    n*(1+2*cos(a)/(1-cos(a))-2*cos(a)/(1-cos(a))*sum(cos(a)^(n-1)). Но сумма степеней косинусов равна (1-cos(a)^n)/(1-cos(a)), так что в знаменателе в ответе должно получиться (1-cos(a))^2, a не (1+cos(a)^n)…
    • +3
      Спасибо, что обратили внимание. К сожалению, правильные формулы потерялись в процессе оформления. Жаль, конечно, что Хабр не поддерживает TEX. Я всё поправил.
  • +16
    Я чего-то не понимаю, скорее всего не понимаю всего. ©
    • +21
      Пост чувства собственного ничтожества.
      • –3
        Небольшая разминка перед рабочим днём, не более…
      • –2
        Да не, если задуматься, что-то решить можно, но задумываться и вспоминать университетский курс матана и ангема ой как не хочется, тем более он забыт, намертво и сверху заколочен досками, с удовольствием, превиликим.
        • +2
          Зря вы так. Это ведь настоящие достижения человечества.
          • +1
            Может и действительно зря, но видели бы Вы как это всё преподавали…
          • 0
            У меня до сих пор есть желание пройти это все еще раз, хорошо разобравшись. :-)
            Вот только жизнь ждать не будет, увы.
  • +5
    В Задаче 2 вы пишете что плоскость замощена прямоугольниками 10 на 20, но при этом не пишете, каким образом эти прямоугольники размещены относительно друг друга. А ведь если к длинной стороне прямоугольника могут примыкать короткие стороны двух других прямоугольников то решение должно быть другим.
    • 0
      «прямоугольники примыкают сторонами» — обычно означает «сторона к стороне». А не «сторона к двум сторонам». И если есть разумная интерпретация, в которой ответ один и не зависит от дополнительных параметров — лучше считать, что она правильная.
      • +2
        Рад, что вы увидели здесь однозначность.
        • +3
          Вот здесь про это хорошо написано.
          • +3
            В той статье все доведено до абсурда, а тут
            прямоугольники примыкают сторонами
            стороны — во множественном числе, значит и «сторона к двум сторонам» — тоже возможно.
    • 0
      Кроме того, если углы прямоугольников совпадают, то окружность всегда будет иметь общие точки с четным количеством прямоугольников, поскольку любая точка из сторон любого прямоугольника будет принадлежать либо двум, либо четырем (угол) прямоугольникам. Без пояснения, как именно размещены прямоугольники, задача некорректна.
      • +2
        Один прямоугольник может быть пересечен дважды. Но я тоже подумал про неоднозначность размещения.
  • 0
    Попахивает «венгерской математикой»
  • 0
    Задача 6:
    Чемпионом объявляют команду, превзошедшую все другие команды

    В доказательстве многократно используется «набрала больше очков». На самом деле победитель (по условиям) найдется тогда и только тогда, когда одна команда проиграет всем остальным, вторая выиграет только у первой, третья только у второй и первой и т.д. Можно найти вероятность этого события. Она будет отлична от 1, соответственно доказать, что победитель найдется всегда — невозможно.
    • 0
      Там засада, на самом деле в этом «или»:
      если А выиграла у В или у какой-либо команды, выигравшей у В

      То есть отношение команд не ограничивается «превосходством», а возможны три отношения:
      A>B
      A<B
      A~B
      • 0
        Не до конца понял систему правил для определения победителя в задаче 6.
        Каждая пара команд играет по 1 разу.

        Берем 3 команды: A, B, C.
        A выигрывает у B, B выигрывает у C, C выигрывает у A.
        Кто победитель?
        • +2
          Между C и A матч вообще не состоится, т.к. по правилам A уже превосходит C по результатам двух предыдущих игр.
          • 0
            Тогда фраза «Каждая пара команд играет по 1 разу.» должна звучать «Каждая пара не превосходящих друг друга команд играет по 1 разу.»
            Спасибо за уточнение.
          • +1
            Мне кажется, что вы неправы. В тексте явно написано, что играет каждый с каждым. Отношение превосходства не обязательно односторонее. Если А превосходит В, то это не значит, что В не превосходит А.
            • 0
              Тогда скажите пожалуйста, я правильно понял по условию, что все играю со всеми вне зависимости от результатов матчей?
              • 0
                Правильно. Получается полный граф, у каждого ребра — какое-то направление. Чемпион — та вершина, из которой до любой другой можно добраться за один или два шага.
        • +3
          Тогда все 3 команды являются чемпионами, потому что каждая превосходит все другие
          • 0
            Я тоже склоняюсь к такому решению.

    • 0
      Альтернативное доказательство: пузырьковая сортировка всегда выявит максимум.
    • 0
      Победителей может быть много. Так, если играют три команды А, В и С, причём А выиграла у В, В выиграла у С, а С выиграла у А, то все три команды являются победителями.
  • +4
    а 30-40-50-летние могут проходить экзамены? Есть какие-то возрастные ограничения?
    • +3
      Посмотрел на задачи, понял, что не все могут… Всё такое знакомое, но отсутствие необходимости в реальной жизни пользоваться чем-то сложнее: отнять, сложить и поделить, накладывает отпечаток. Т.е. ограничение может больше накладывает не возраст как таковой, а дальность отстояния от окончания ВУЗа и отсутствие повседневной необходимости использовать «вышку».
      • +1
        Да, там уже идёт расслоение — либо ты про это уже забыл, и тогда задачи просто не решатся, либо всё это умеешь — и тогда, скорее всего, тебе будет просто скучно.
    • +2
      Возрастных ограничений при приёме в ШАД нет.
  • 0
    Мне кажется, что даже если тест и для школьников, все равно нельзя давать формулировки в роде вероятности того, что что-то, без указания распределения. Математика — точная наука.
    • 0
      С распределениями здесь тоже всё хорошо. Случайная окружность на плоскости с периодическим рисунком — понятно, что координаты центра распределены равномерно по фундаментальной области. А про ломаную явно сказано «с равной вероятностью».
      • 0
        Я не знаю, что такое фундаментальная область, но в задаче говорится про плоскость, по которой равномерно ничего распределить не получится.
        • 0
          Ну как же — вот она. Для паркета из прямоугольников — будет самим прямоугольником (если брать группу параллельных переносов). А на нём распределить точки равномерно — не проблема.
          • +2
            Да, хороший термин. Однако я же не говорю, что есть проблема с пониманием того, что имелось в виду в задаче. Я только считаю, что формулировки такие нельзя давать.
  • +1
    По-моему задачки совсем не сложные для студента/выпускника очных технических специальностей, где высшая математика преподаётся 2 года. Вопрос только в одном: «зачем?»
    • 0
      Про шестую и восьмую я бы не сказал, что они несложные. И статистика это подтверждает.
      • 0
        Да, 6 и 8 значительно сложнее остальных, возможно, это как раз «лакмусовая бумажка» для экзаменаторов. Но всё это не отменяет главного вопроса.
        • +1
          Отсеять тех, кто, скорее всего, не потянет. А 6 и 8 — отсеять тех, кому будет неинтересно :)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка