Школа анализа данных ответы

Обновлено: 02.07.2024

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

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

  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 xdx
  6. Показать, что у целочисленной матрицы не бывает рациональных (нецелых) собственных чисел.
  7. На круговой дороге стоят канистры с бензином. Есть машина с известным расходом топлива и пустым баком неограниченной ёмкости. За O(n) операций выяснить, от какой канистры надо начать, чтобы, собирая топливо, проехать всю дорогу и не остановиться пустым (или сказать, что это невозможно).

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

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

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

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

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

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

Набор проходит в три этапа:

  1. Онлайн-тестирование: решение заданий теста за 5 часов;
  2. Для поступающих в московское отделение второй этап состоит из двух частей: первая – математика и алгоритмы, вторая – программирование и основы анализа данных;
  3. Заключительный этап – очное собеседование, во время которого придется решать задачи по математике, алгоритмам и программированию.

Шаг 1: Выясните, каких знаний вам не хватает

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

Шаг 2: Математическая подготовка

Алгeбра

  • Определение, четность, произведение подстановок. Разложение подстановок в произведение транспозиций и независимых циклов.
  • Комплексные числа. Геометрическое изображение, алгебраическая и тригонометрическая форма записи, извлечение корней, корни из единицы.
  • Системы линейных уравнений. Прямоугольные матрицы. Приведение матриц и систем линейных уравнений к ступенчатому виду. Метод Гаусса.
  • Линейная зависимость и ранг. Линейная зависимость строк (столбцов). Основная лемма о линейной зависимости, базис и ранг системы строк (столбцов). Ранг матрицы. Критерий совместности и определенности системы линейных уравнений в терминах рангов матриц. Фундаментальная система решений однородной системы линейных уравнений.
  • Определитель квадратной матрицы, его основные свойства. Критерий равенства определителя нулю. Формула разложения определителя матрицы по строке (столбцу).
  • Операции над матрицами и их свойства. Теорема о ранге произведения двух матриц. Определитель произведения квадратных матриц. Обратная матрица, ее явный вид (формула), способ выражения с помощью элементарных преобразований строк.
  • Векторное пространство, его базис и размерность. Преобразования координат в векторном пространстве. Подпространства как множества решений систем однородных линейных уравнений. Связь между размерностями суммы и пересечения двух подпространств. Линейная независимость подпространств. Базис и размерность прямой суммы подпространств.
  • Линейные отображения, их запись в координатах. Образ и ядро линейного отображения, связь между их размерностями. Сопряженное пространство и сопряженные базисы. Изменение матрицы линейного оператора при переходе к другому базису.
  • Билинейные функции, их запись в координатах. Изменение матрицы билинейной функции при переходе к другому базису. Ортогональное дополнение к подпространству относительно симметрической билинейной функции. Связь между симметричными билинейными и квадратичными функциями. Существование ортогонального базиса для симметрической билинейной функции. Нормальный вид вещественной квадратичной функции. Закон инерции.
  • Евклидовы пространства. Неравенство Коши-Буняковского. Ортогональные базисы. Ортогонализация Грама-Шмидта. Ортогональные операторы.
  • Собственные векторы и собственные значения линейного оператора. Собственные подпространства линейного оператора, их линейная независимость. Условие диагонализируемости оператора.

Математически анализ

  • Пределы и непрерывность. Пределы последовательностей и функций. Непрерывные функции.
  • Ряды. Числовые и функциональные ряды. Признаки сходимости (Даламбера, Коши, интегральный, Лейбница). Абсолютно и условно сходящиеся ряды.
  • Дифференцирование. Дифференцирование функций. Применение производной для нахождения экстремумов функций. Формула Тейлора.
  • Функции многих переменных. Частные производные. Градиент и его геометрический смысл. Гессиан. Метод градиентного спуска. Поиск экстремумов функций от многих переменных.
  • Интегрирование. Определенный и неопределенный интегралы. Методы интегрирования функций. Первообразные различных элементарных функций. Кратные интегралы (двойные, тройные), замена координат, связь с повторными.
  • Элементы функционального анализа: нормированные, метрические пространства, непрерывность, ограниченность.

Комбинаторика

  • Основные правила комбинаторики. Правило подсчета количества комбинаторных объектов. Принцип Дирихле. Примеры.
  • Множества. Круги Эйлера, операции на множествах. Формула включений и исключений. Примеры.
  • Сочетания. Размещения, перестановки и сочетания. Бином Ньютона. Треугольник Паскаля. Сочетания с повторениями.

Теория вероятностей

  • Основные понятия теории вероятностей. Определение вероятностного пространства, простейшие дискретные случаи (выборки с порядком и без него, упорядоченные и неупорядоченные), классическая вероятностная модель. Случайная величина, функция распределения.
  • Условные вероятности. Определение условной вероятности, формула полной вероятности, формула Байеса.
  • Математическое ожидание, дисперсия, корреляция. Определение математического ожидания, дисперсии, ковариации и корреляции, их свойства.
  • Независимость событий. Попарная независимость и независимость в совокупности.
  • Основные теоремы теории вероятностей. Неравенство Чебышева. Закон больших чисел. Центральная предельная теорема.
  • Распределения. Стандартные дискретные и непрерывные распределения, их математические ожидания, дисперсии и свойства: биномиальное; равномерное; нормальное; пуассоновское; показательное; геометрическое.

Шаг 3: Программирование

  • Простейшие конструкции языка программирования. Циклы, ветвления, рекурсия.
  • Анализ алгоритмов. Понятие о сложности по времени и по памяти. Асимптотика, O-символика. Инварианты, пред- и пост- условия. Доказательство корректности алгоритмов.
  • Простейшие структуры данных. Массивы, стеки, очереди, связные списки, Сравнение временных затрат при различных типах операций.
  • Строки и операции над ними. Представление строк. Вычисление длины, конкатенация.
  • Сортировки. Нижняя теоретико-информационная оценка сложности задачи сортировки. Алгоритмы сортировки вставками, пузырьком, быстрая сортировка, сортировка слиянием. Оценка сложности.
  • Указатели.Указатели и динамическое управление памятью.

Курсы для подготовки:

Шаг 4: Анализ данных

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

  • Основные машинного обучения: классификация, регрессия, ранжирование, кластеризация. Обучение с учителем и без учителя.
  • Предобработка и очистка данных. Работа с пропущенными значениями.
  • Feature Engineering. Работа с категориальными признаками.
  • Переобучение: как его обнаружить и как с ним бороться. Разделение на обучающую и тестовую выборки. Методы регуляризации.
  • Сравнение моделей. Метрики в задачах классификации и регрессии. Методология подборара гиперпараметров.
  • Основные модели классификации и регрессии: линейные модели, решающие деревья. Ансамбли алгоритмов.

Курсы для подготовки:

Шаг 5: Практика

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

Примеры упражнений:

Двухгодичная программа Яндекса появилась в 2007 году и стала первым местом в России, где учат анализу данных. Курсы ШАДа легли в основу магистерских программ крупных университетов, таких как ВШЭ и МФТИ.

Главное о ШАДе

Преподаватели

Лекции и семинары в ШАДе проводят сотрудники Яндекса, преподаватели ведущих университетов и исследователи, работающие в современных областях компьютерных наук.

География ШАДа

Что делают студенты после ШАДа

Выпускники ШАДа работают в крупнейших мировых IT-компаниях. Среди них — Google, Apple, Яндекс и Facebook. А также становятся учёными в ведущих университетах России и за рубежом.

Подробнее о ШАДе

Сотрудничество

МФТИ

ВШЭ

БГУ

МГУ

ЦЕРН

УРФУ

РЭШ

ННГУ

Филиал Школы Анализа Данных в Нижнем Новгороде открылся в 2017 г. Занятия ведут преподаватели института информационных технологий, математики и механики ННГУ им. Н.И.Лобачевского и сотрудники Нижегородского офиса Яндекса.

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

1. В ряд выложены пять красных, пять синих и пять зеленых шаров. С какой вероятностью никакие два синих шара не лежат рядом?

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

Задачи по алгоритмам очень хороши тем, что они проверяют не только умение понятно описать некую процедуру, но и объяснить, почему она работает.

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

3. Докажите, что среди шести человек обязательно найдутся трое попарно знакомых или трое попарно незнакомых.

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

  • четное число, гласная буква;
  • нечетное число, что угодно.

И не подходят карточки вида:

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

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

6. Квадратная матрица такова, что след tr(AX) = 0 для любой матрицы X того же размера, имеющей нулевой след (след матрицы — сумма элементов на главной диагонали).

Докажите, что матрица является скалярной (т. е. имеет вид λE для некоторого λ, где E — единичная матрица).

Таким образом, встретив подобную задачу, стоит сначала взять какие-нибудь конкретные (и желательно очень простые) матрицы X с нулевым следом и попробовать понять, что же нам дает условие tr(AX) = 0. В качестве таких матриц удобно взять матричные единицы (и матрицы, у которых на диагонали все нули, кроме двух элементов, равных 1 и (-1).

Собственно говоря, на этом задача и закончится: из условий tr(AX) = 0, которые вы распишете для таких матриц, сразу будет следовать ответ.

Читайте также: