Компания
493,49
рейтинг
24 апреля 2014 в 18:40

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

16 апреля открылся новый набор в Школу анализа данных Яндекса, который продлится до 15 мая. В этом посте я хочу рассказать вам, как сложилась судьба тех, кто уже закончил ШАД, а также впервые публично разберу все задания нашего письменного вступительного экзамена. Как всегда, желающим надо будет заполнить анкету и выполнить задание на сайте Школы, сдать письменный экзамен и пройти собеседование.

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

Истории: одна о гуглере и одна — о сотруднике Яндекса

С момента создания ШАД её закончили 260 специалистов в области computer science. Мы попросили двух выпускников Школы рассказать о том, что им дало обучение в ней, и дать несколько советов тем, кто решил поступать.

Андрей Петров, разработчик в мюнхенском офисе Google.
imageКогда я был студентом, у меня сложилась иллюзия, что программировать я уже умею, а Computer Science — это просто. Действительно, ведь я создавал сайты с динамическим контентом, писал игры, получал призы на олимпиадах и без проблем сдавал экзамены в университете. Однако это было лишь хобби, а я был любителем. Чтобы начать путь профессионала, я пошёл в школу Яндекса.

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

Если вы раздумываете, стоит ли поступать, и пребываете в таких же иллюзиях, как я, то теперь вы знаете, что делать. Даже если никаких иллюзий нет, это всё равно крайне полезно и интересно. И в науке анализа данных, и в IT-индустрии нужны профессионалы. Чтобы примкнуть к их числу, придётся проделать немалый путь, а поступление в ШАД — это серьёзный шаг вперёд в этом направлении.


Алексей Умнов, выпускник ШАД. Разработчик в группе морфологии Поиска в Яндексе, аспирант ВМК МГУ.
imageВ ШАДе я получил множество полезных теоретических и практических знаний. Они пригодились мне как в проектах внутри Яндекса, так и в других областях. Например, в научной деятельности я очень активно использую знания, полученные на курсе машинного обучения, а также различные навыки программирования. Стоит также отметить, что весь материал, даваемый в ШАДе, достаточно современный, что очень важно для такой быстро развивающейся области, как Computer Science.

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


Разбор вступительных задач

На этот раз мы решили впервые публично разобрать все задания письменного вступительного экзамена в Школу анализа данных. К нему допускаются только те, кто успешно справился с заданием в анкете. В прошлом году из 617 человек приглашение на него получили 284, а успешно сдали и дошли до собеседования — 132.

Задача 1


Последовательность определена рекурсивно.



Найдите формулу общего члена последовательности.

Решение
Введем обозначение Тогда

Кроме того, . Получаем, что

Отсюда получаем

Задача 2


Даём множество A = {1,2,...,n}. Среди всех его подмножеств равновероятно выбираем k его подмножеств A1,…,Ak. Найдите вероятность того, что A1 ∩ A2 ∩ … ∩ Ak = ∅.

Решение

Рассмотрим элемент iA. Очевидно, подмножеств в A, содержащих i и не содержащих i, равное количество. Таким образом вероятность того, что i лежит в Aj равна 1/2. Эти вероятности независимы для разных j. Получаем, что вероятность того, что i содержится в A1 ∩ A2 ∩ … ∩ Ak равна 1/2k. Соответственно, вероятность того, что i не содержится в A1 ∩ A2 ∩ … ∩ Ak, равна 1 — 1/2k. Эти вероятности независимы в разных i. Получается, что вероятность того, что ни один из номеров i не попал в A1 ∩ A2 ∩ … ∩ Ak равна (1 — 1/2k)n.

Задача 3


Дан массив длины n из нулей и единиц. Найдите в нём подмассив макисмальной длины, в котором количество единиц равно количеству нулей. Ограничения: O(n) по времени и O(n) по дополнительной памяти.

Решение

Обозначим исходный массив через a[・]. Заведём еще четыре массива длины n: b[・], c[・], d[・] и e[・]. Пройдём по возрастанию индексов и заполним массив b[・] по правилу: b[0] = 2 ・ a[0] — 1, b[i] =b[i — 1] + 2a[i] — 1 при i > 0. Иными словами, если в массиве a[・] заменить нули на -1, то в массиве b[・] будут стоять суммы от a[0] до a[i]. Заполним массивы c[・] и d[・] минус единицами. Далее идём по возрастанию номеров по массиву b[・]. Если b[i] = k, то d[k] = i, если при этом выполнено c[k] = -1, то присваиваем c[k] = i.

Далее, когда мы прошли по всему массиву b[・], заполним массив e[・] по правилу e[i] = d[i] — c[i]. Заметим, что если в массиве a[・] есть подмассив от a[m] до a[l], в котором равное количество единиц и нулей, то b[m] = b[l] = k. И тогда c[k] — это минимальный номер i такой, что b[i] = k, а d[k] — максимальный. Соответственно, e[k] — максимальное расстояние между m и l, где b[m] = b[l] = k. Найдём максимум массива e[・]. (Очевидно, это можно сделать за O(n) операций.) пусть он равен e[j]. Тогда искомы подмассив — это подмассив от a[c[j]] до a[d[j]]

Задача 4


Пусть

Для каких m ∈ [0, 10] Im≠0?

Решение

Многократно воспользуемся формулой:


С помощью этой формулы получим:
где ai = 1 ± 2 ± 3 … ± m ∈ Z. Несложно убедиться, что чётности всех чисел ai будут одинаковы. Более того, в случаях m = 4k и m = 4k + 3 все ai чётны. Если ai ≠ 0, то

Значит, при m = 4k + 1 и m = 4k + 2, Im = 0. Если же m = 4k или 4k + 3, то среди ai обязательно есть ноль, так как между числами 1, 2, …, m можно так расствить знаки «+» и «—», чтобы получился ноль. Действительно,

(1 − 2 − 3 + 4) + (5 − 6 − 7 + 8) +... + ((4k − 3) − (4k − 2) − (4k − 1) + 4k = 0,
(1 + 2 − 3) + (4 − 5 − 6 + 7) +... + (4k − (4k + 1) − (4k + 2) + (4k + 3)) = 0
.

Таким образом, m = 4k и 4k + 3, Im = 0. Ответ: при m = 0,3,4,7,8.

Задача 5


Дан неориентированный граф G без петель. Пронумеруем все его вершины. Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-ой вершины графа в j-ю вершину.

Докажите, что матрица A имеет отрицательное собственное значение.

Решение

Утверждение задачи не свосем верно. Если в графе нет рёбер, то матрица нулевая и все собственные значения равны нулю. Если же рёбра есть, то A — симметрическая матрица с неотрицательными элементами и нулями на диагонали. Докажем, что у такой матрицы есть неотрицательное собственное значение.

Известный факт, что симметрическая матрица диагонализуема в вещественном базисе. (Все собственные значения вещественны.) Допустим, что все собственные значения A неотрицательны. Рассмотрим квадратичную форму q с матрицей A в базисе {e1, … ,en}. Тогда эта квадратичная форма неотрицательно определена, так как все собственные значения неотрицательны. То есть С другой стороны, пусть aij≠ 0. Тогда q(ei — ej) = aii — 2aij + ajj= -2aij < 0. Это противоречит неотрицательно определённости q. Значит исходное предположение неверно, и у A есть отрицательное собственное значение.

Задача 6


Рассмотрим бесконечный двумерный массив , состоящий из натуральных чисел, причём каждое число встречается ровно 8 раз. Докажите, что ∃ (m,n): amn > mn.

Решение

Допустим, что . Выберем некоторое k ∈ N и рассмотрим кривую на плоскости y = k/x. Если i,j ∈ N и точка (i,j) лежит под кривой y=k/x, то aij ≤ ij ≤ i・k/i= k. Таким образом, количество целых точек под кривой y = k/x должно быть не больше 8k. С другой стороны, количество целых точек под этой кривой не меньше, чем При достаточно большом k это число больше 8k. Таким образом, мы получаем противоречие. Следовательно, найдётся пара (m,n) такая, что : amn>mn.

Задача 7


Дана матрица из нулей и единиц, причём для каждой строки матрицы верно следующее: если в строке есть единицы, то они все идут подряд (неразрывной группой из единиц). Докажите, что определитель такой матрицы может быть равен ±1 или 0.

Решение

Переставляя строки, мы можем добиться того, чтобы позиции первых (слева) единиц не убывали сверху вниз. При этом определитель либо не изменится, либо поменяет знак. Если у двух строк позиции первых единиц совпадают, то вычтем ту, в которой меньше единиц из той, в которой больше. Определитель при этом не меняется. Такими операциями мы можем добиться того, что позиции первых единиц строго возрастают сверху вниз. При этом либо матрица окажется вырожденной, либо верхнетреугольной с единицами на диагонали. То есть, определитель станет либо 0, либо 1. Так как определитель при наших операциях либо не менялся, либо поменял знак, изначальный определитель был ±1 или 0.

Ещё пара слов о школе

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

В прошлом году мы получили 617 заявок на поступление, 284 человека были приглашены на письменный экзамен. Но это не последнее испытание для поступающих в Школу. По результатам экзамена мы приглашаем на собеседования. Из 132 человек, которые его успешно сдали и дошли до собеседований, на первый курс было зачислено 97 человек.

Как многие из вас могут помнить, ШАД появилась в 2007 году. Сейчас у нас есть филиалы в Екатеринбурге, Киеве, Минске и Новосибирске. В Санкт-Петербурге отделение ШАД открыто при Computer Science Center.

Обучение на курсах длится два года. Программа разделена на три типа курсов: теоретические («Дискретный анализ», «Комбинаторика», «Вероятность», «Теория сложности»), практические («Обучение программированию на С++», «Java», «Параллельные и распределенные вычисления») и смешанные («Алгоритмы и структуры данных», «Машинное обучение», «Компьютерная лингвистика» и т.д.). Учиться можно и на заочном отделении, общаясь с преподавателями по электронной почте и пользуясь видеолекциями.
Автор: @sgayf
Яндекс
рейтинг 493,49

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

  • +2
    Возможно ли узнать проходные баллы после онлайн теста и самого экзамена, для прохода в следующий этап отбора?
    • 0
      В прошлом году мы получили 617 заявок на поступление, 284 человека были приглашены на письменный экзамен.

      Подозреваю, что необходимо решить все задачи верно.
    • +1
      На Дне открытых дверей это рассказывали. Требуется решить минимум 4 задания. Если больше — то собеседование формальность, если меньше — то не факт что пригласят на собеседование или на собеседовании дадут дополнительные задания.
      • 0
        Спасибо за информацию.
      • 0
        А сколько времени давали на экзамен?
        • +1
          4 часа.
    • +2
      Про экзамен уже написали. В прошлом году приглашали некоторых людей, у которых было меньше 3 решённых задач. Но для того, чтобы почти 100% поступить надо было 4 или больше решить. В онлайн тесте примерно 7 из 12. Но это всё очень примерно и в этом году может быть совсем по-другому. Реальные проходные балы будут определены после закрытия теста и окончания экзаменов в зависимости от статистики.
  • –16
    Народ, а это у Я прокатывает? PR чистой воды и фотка «ботан & ботан»?
    • +6
      А в чём тут пиар чистой воды?

      Тут зовут в ШАД — очень серьёзную и хорошую образовательную программу, которую организует Яндекс. Вы образование считаете пиаром чистой воды? Или разбор задач?
      • –10
        Мне кажется образование это не решение n-го количества задач, а желание человека узнать что-то новое и критерии отбора здесь по меньшей мере не уместны! Вы конечно мне сразу возразите, что мол слишком вас много таких желающих, на что я бы ответил — мы живем в 21 веке и донести инфу можно до всех и сразу. Спрашивается — зачем весь этот отбор? Мне на ум приходит только одно — отобрать и обучить кандидатов для работы в Я.
        • +8
          Давайте честно скажем, организовать онлайн и офлайн обучение — сильно разные вещи.
          И сделать собранное онлайн-образование пока ни у кого не получилось, есть только отдельные курсы.
          Мы в эту сторону тоже движемся — некоторые наши курсы можно смотреть онлайн shad.yandex.ru/lectures/, дальше будет больше.

          А пока обучаем людей вживую, потому, что многое можно пока делать хорошо только так. Вы же не призываете прямо завтра закрыть Оксфорд или MIT? И не считаете их деятельность пиаром чистой воды?

          Про «обучить кандидатов для работы в Я» — обратите внимание, мы специально привели и историю гуглера. ШАД никому не навязывает, как свои знания потом использовать.

          А в ваших словах, если честно, слишком много критики и слишком мало конструктива. Судя по «ботан и ботан», у вас самого учиться особенного желания тоже нет. Объясните, чего вы пытаетесь своими высказываниями добиться?
          • –14
            «А пока обучаем людей вживую, потому, что многое можно пока делать хорошо только так....» — тогда вы явно отстали и я не понимаю зачем вся эта полемика. Вы пытаетесь оправдаться при этом унизя меня и мои знания, наверняка явно не зная учусь я или нет, да и вообще не анализируя что я написал и в каком стиле. А дальше не хочу «кидаться цицатами» в вашем стиле, поэтому закончим, все кто мог сделать выводы уже это сделали! Простите за тавтологию. И удачи в обучении.
            • +2
              А в чем отсталость? Это факт, что очное общение — наиболее эффективный способ коммуникаций. И чем сложнее разбираемый материал, тем больше будет сказываться качество «канала» коммуникаций на итоговое качество усвоения новых знаний.

              А онлайн образование(типа всяких курсер) пока, как правило, не дает глубоких знаний в рассматриваемых областях.

              Да и чего плохого в том, чтобы Я хантили участников своих обучающих программ?
          • 0
            Не соглашусь с «ни у кого не получилось» — будучи школьником учился в заочной физ.-мат. школе при МФТИ. Хотя чисто «онлайновым» такой вариант назвать нельзя — выполненные задания проверяет человек, задания не тестовые, поэтому автоматизировать проверку невозможно, — тем не менее охват его гораздо выше, чем мог бы быть в очном варианте. И уровень материала там был очень высокий. В качестве общественной нагрузки что-то похожее мог бы практиковать и Яндекс.
            • 0
              Учиться можно и на заочном отделении, общаясь с преподавателями по электронной почте и пользуясь видеолекциями.
  • +19
    Я себя чувствую таким глупым неучем…
  • 0
    Для задачи 3 вы привели ответ, а какое решение?
    Как дойти до такого алгоритма, не зная его?
    • +1
      Довольно просто.
      Сразу будем работать с массивом B, состоящим из 1 и -1. Нам нужно найти в нём отрезок максимальной длины с нулевой суммой. Рассмотрим график частичных сумм B[0]+B[1]+...+B[n-1] (он выглядит, как изломанная линия). На нём надо найти две точки, находящиеся на одном уровне, и с наибольшим расстоянием между ними. Легко понять, что нам достаточно для каждого уровня (т.е. значения частичной суммы) запомнить, когда мы впервые пришли на этот уровень, и, каждый раз, когда мы будем оказываться на этом уровне, проверять, сколько элементов массива оказалось между первым его посещением и текущим моментом. Максимум этого значения и даст ответ.
    • 0
      По сути, в массиве B хранится разность между числом единиц и числом нулей в предшествующем участке массива (от начала и до i).

      Если представить массив B в виде графика, у него, в общем случае, будут подъемы и спады, и нас интересуют те случаи, когда одному значению ординаты (т.е. B(i)) соответствуют два разных значения абсциссы (т.е. i). В этом случае между этими значениями [индексов] исходный массив должен иметь нулевую разность единиц и нулей, и нам нужно найти случай, когда значения абсциссы отстоят друг от друга максимально далеко.

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

      Для этого мы в массиве D запоминаем последнее значение ординаты, а в массиве С — первое. Затем находим разность между ними и максимум среди разностей.

      (Я, если честно, сам додумался только до массива B :) ).
  • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      Да, пожалуй так как вы пишете элегантнее.
  • +3
    Дошел до 4-й. Озадачился. У меня получилось, что ответ — m=3,4,7,8 (те, для которых сумма 1+2+..+m чётна), и Maple со мной согласен. Что мы делаем не так?
    • НЛО прилетело и опубликовало эту надпись здесь
      • +2
        Извините, я перепутал знак в выкладке и приведённое решение было не верно. Спасибо за указание. Сейчас исправил и с вашим ответом сходится.
  • +8
    Честно говоря, довольно сложно уловить связь между этими задачами и тем, что «разработка — это не написание кода, а соблюдение стиля, использование практик, поддержка документации и тестирование ПО.» Какая тут может быть логика?
    • +2
      Вы о какой логике? На технический специальностях от 1/3 до 1/2 предметов — гуманитарные, с заметным уменьшением часов на действительно полезные предметы.
      Ну а Яндекс видимо решил, что им нужны люди, которые хорошо знают матан и логические задачки. Или люди со свежими мозгами нужны, которые еще не задают вопросов — а зачем, почему, ну и прочие.

      И кстати, возможно есть причина для этого — разработчик, это обычно человек, который способен саморазвиваться, и брать таких на обучение сложно, ведь посмотрев список: ну Java, C++ — люди возьмут пару книжек по этим языкам, или просто почитают документацию — да и все, а всяким мелочам уже при написании программ можно научиться. Параллельные вычисления, алгоритмы и структуры данных — книжек тоже много есть, про теорию вероятности, теорию сложности — тоже все есть. В итоге человеку просто будет не понятно, зачем ему ходить / слушать какие-то лекции целых 2 года, когда он может взять и прочитать книги (чаще всего это значительно быстрее, и знания менее поверхностные получаются).
  • +1
    В задаче 1, по-моему, формула должна быть не
    аn = 2 / (n*(n+1) + 2), а
    аn = 2 / ((n-1)*n + 2).

    Ведь в формуле
    bn = b0 + 1 + 2 +… + n

    последнее число должно быть не n, а (n-1):
    bn = b0 + 1 + 2 +… + (n-1)
    • +1
      Поскольку моему комментарию поставили минус, уточню:

      Чему равно a1? По рекуррентной формуле, очевидно:
      a1 = a0+1 = a0 / (1 + 0 * a0) = 1 / (1 + 0) = 1

      По формуле an = 2 / (n * (n+1) + 2) получается:
      a1 = 2 / (1 * 2 + 2) = 1 / 2

      По моей формуле:
      a1 = 2 / (0 * 1 + 2) = 1

      Так получается из-за того, что из формулы
      bn+1 = bn + n

      следует
      bn+1 = b0 + 1 + 2 +… + n

      а вовсе не
      bn = b0 + 1 + 2 +… + n
      • +1
        Да, я согласен, надо было суммировать до n-1 и в ответе будет минус вместо плюса. Сейчас исправлю. Спасибо!
  • 0
    Спасибо за интересную статью.
    Подскажите, какие разделы математики наиболее затрагиваются при поступлении и обучении?
    • 0
      Вы можете посмотреть программу для поступления на сайте shad.yandex.ru/admission/
  • 0
    А, есть ли какие-то возрастные ограничения для «школьников»? То есть, в каком возрасте учиться в Школе уже «поздно»?
    • 0
      Нет, есть ограничения снизу: учиться может тот, кто окончил как минимум 2 курса ВУЗа. Ограничений сверху нет. Более того многие из ШАДовцев — это взрослые люди давно уже закончившие институт, так что это вполне в порядке вещей.
  • 0
    Спасибо за статью, подался!

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

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