Здравствуйте! Рады поздравить Вас с поступлением в Школу анализа данных! Ближе к сентябрю куратор Вашего филиала напишет об организационных моментах.

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

Знакомый предложил попытать счастья: «ты можешь». Онлайн-отбор был адъ и мракъ, часа четыре мучился. Хотя, признаться, немного читил: в заданиях по программированию просто переводил программы с псевдокода на C++, да и одну задачу на матрицы, не подобрав ключа, просто решил в лоб ёкселем. Я не знал, что такое «положительный индекс инерции» (правильно я написал это название?) - пришлось отыскивать, это оказалось всего лишь количество положительных элементов в диагональном разложении квадратичной формы.

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

1. Сколько есть способов пройти из (0,0,0) в (n , 2n , 3n ), если можно делать шаги на +1 по любой из осей?
2. Найти 319-ю производную в нуле функции (x²+17) / (x 4 −5x²+4)
3. Сколько перестановок коммутируют с (123)(456)?
4. В равностороннем треугольнике ABC площади 1 выбираем точку M . Найти матожидание площади ABM .
5. ∫ 1 / √1+e x dx
6. Показать, что у целочисленной матрицы не бывает рациональных (нецелых) собственных чисел.
7. На круговой дороге стоят канистры с бензином. Есть машина с известным расходом топлива и пустым баком неограниченной ёмкости. За O(n ) операций выяснить, от какой канистры надо начать, чтобы, собирая топливо, проехать всю дорогу и не остановиться пустым (или сказать, что это невозможно).

Я решил 6 задач - кроме, естественно, интеграла. Правда, переволновался, и 2 и 3 решил неправильно (при правильной методике!)

На собеседовании больше спрашивали про личное: почему ты решил сунуться в Школу, не трудно тебе с работой, ничего, что все моложе тебя? С ответом медлили четыре дня (в первые дни я периодически тряс почту через веб, когда напарник отворачивался). И, наконец, ответили.

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

Отрицательный опыт. Мне стоило успокоиться, тогда задачи 2 и 3 вышли бы. Не стоило решать интеграл вообще - или на подготовке посвятить больше времени интегралам. Наконец, подготовка в том виде, в котором она была, дала мало что. Я подтянул теоремы, вспомнил, как обосновывается та или иная вещь, но из этого добра потребовалась только запись перестановок.

Отбор в школу проходит в три этапа:

1. Онлайн тестирование : после заполнения анкеты поступающего вы получите письмо со ссылкой. На решение заданий теста отводится пять часов.
2. Письменный экзамен : для поступающих в московское отделение ШАД экзамен состоится очно в Москве в конце мая или в начале июня.
   Поступающие в филиалы и на заочное отделение сдадут экзамен онлайн в начале июня. В письменном экзамене могут поучаствовать только те, кто успешно прошли этап онлайн-тестирования.
3. Собеседование : в конце июня - начале июля для всех, кто успешно прошел первые два этапа, пройдут собеседования в отделениях ШАД или по скайпу.

Подготовка

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

• Набор 2012 года
• Набор 2013 года
• Набор 2014 года
• Набор 2016 года
• Набор 2017 года

Платное обучение

Поступающие, хорошо показавшие себя на собеседовании, но не прошедшие по общему конкурсу, смогут начать учиться на платной основе (только в московском отделении). Платная учёба ничем не отличается от бесплатной - нужно выполнять все те же непростые задания, укладываясь в жёсткие сроки. Обучение стоит 110 000 рублей за семестр. Если студент заканчивает семестр на «хорошо» и «отлично», стоимость обучения для него снижается до 55 000 за семестр. Сдавший на «хорошо» и «отлично» две сессии подряд дальше учится бесплатно.

Образование

В 2017 году поступить в ШАД (Школа Анализа Данных) Яндекса.

Здравствуйте!

Меня зовут Владимир, мне 26 лет. У меня несколько высших образований (инженер металлургии и экономика и управление на предприятии). Оба образования я получил в Московском Институте Стали и Сплавов. На данный момент работаю Руководителем проектов в одной из отечественных ИТ-компаний, которая является вендором информационных систем управления производством. На работе я постоянно сталкиваюсь с необходимостью агрегирования и передачи данных, интеграции различных систем с помощью Сервисной Шины Предприятия (ESB). О ШАДе услышал год назад, но предыдущий год был очень загружен - сдача дипломных работ на втором высшем и магистратуре, поступление в аспирантуру. Кроме этого было очень много затяжных, рабочих командировок. На данный момент загружен не так сильно, поэтому думаю наконец-то заняться вопросом подготовки и поступления. На текущую дату ощущаю себя чуть более, чем неготовым полностью;) Весь институтский матан забыт. По комбинаторике и тер.веру изучал материал самостоятельно. По программированию самостоятельно (с помощью курсов на курсере и степике) выучил Python. Думаю, что по сложности и нагрузке подготовка будет распределена следующим образом: Матан - 50%, Комбинаторика и Тер.Вер. - 30%, Программирование - 20%.

Почему решил воспользоваться этим сервисом? Все просто. Думаю, что он поможет мне отслеживать динамику и, возможно, найти людей, которые могут помочь мне, или, которым смогу помочь я:)

Критерий завершения

Зачисление в ШАД. Не обязательно на очное отделение, но желательно на бюджетное место.

Личные ресурсы

Ресурсами для данной задачи являются Время и Информация. С временем туго, т.к. работа, командировки и обучение студентов.

Возможно понадобятся деньги для оплаты курсов или репетитора. Проблем с деньгами особых нет.

Экологичность цели

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

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

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

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

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

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

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

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

Задача 1

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

Ответ

Решение

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

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

Задача 2

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

Ответ

Решение

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

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

Задача 3

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

Ответ

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

Решение

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

Задача 4

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

Ответ

Решение

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

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

Задача 5

Даны два массива целых чисел a и b , причём все элементы b различны. Требуется найти набор индексов i_1 < i_2 <… < i_k , для которого набор a,...,a является перестановкой элементов массива 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

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

Яндекс открывает новый набор в Школу анализа данных . Это бесплатные двухгодичные вечерние курсы для тех, кто хочет получить образование в области обработки и анализа данных и извлечения информации из интернета. Школа требует хорошей математической подготовки и рассчитана прежде всего на студентов и молодых выпускников инженерных и математических специальностей.

Как поступить

Нужно заполнить анкету на сайте школы до 15 мая . После этого вы получите письмо со ссылкой на онлайн-тест по математике и основам программирования. Всех, кто успешно справится с тестом, школа пригласит на письменный экзамен, который состоится в конце мая – начале июня. Лучшим по результатам экзамена предстоит пройти собеседование, по итогам которого будет принято окончательное решение.

Программа обучения

На сайте школы вы можете изучить экзаменационные задания прошлых лет и узнать, к чему стоит готовиться. Познакомиться с преподавателями школы и узнать о новом направлении «Большие данные » можно будет на Дне открытых дверей ШАД . Он состоится 19 апреля в московском офисе Яндекса, для участия необходимо зарегистрироваться.

Занятия в ШАД проводятся по вечерам в будние дни. Учиться в школе можно очно или заочно, по видеолекциям. Во время обучения или после окончания школы студенты могут пройти стажировку в Яндексе.

Школа анализа данных существует с 2007 года и выпустила более 300 специалистов, многие из которых занимаются наукой, работают в Яндексе и других крупных IT-компаниях в России и за рубежом. Отделения ШАД существуют в Санкт-Петербурге (в рамках Computer Science Center), Новосибирске, Екатеринбурге, Минске и Киеве.