Задачи вступительного экзамена в шад - Помощь в подготовке к экзаменам и поступлению

ВСЕ ЭЛЕКТРОННЫЕ МАТЕРИАЛЫ ДЛЯ ПОДГОТОВКИ | ШАД ЯНДЕКСА

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

Что есть материалах по подготовке к ШАДу:

1_Online_Test – мои решение задач с теста на Питоне
2_Exams – задачи с экзаменов 2012-2018 и их решения. Еще советую посмотреть supershad – там формат поудобнее.
3_Interviews – задачи с интервью прошлых лет и их решения. Еще источник
4_Books – все книги, перечисленные в программе для поступления в ШАД, плюс еще много разных полезных книг, которыми я пользовался при подготовке
5_Formulae – различные конспекты, формулы и шпаргалки. Если нужно освежить в памяти отдельные темы или нет времени целиком прочитать книги
6_Problemsets – задачи, близкие к экзаменам и интервью в ШАД. Сейчас там лежат листки по теорверу ФКН Вышки. Добавлю еще материалы, если найду
More_materials – дополнительные материалы по подготовке, на которые наткнулся в Интернете. Сам не успел ими воспользоваться, но подозреваю, что интересные задачи там найдутся

Папка большая (700 МВ), поэтому не знаю, сколько проживет ссылка. Пишите в комментах, постараемся ее оживлять.

Если еще не подписались на наш канал в YouTube, самое время это сделать вот здесь! В начале августа узнаем, к чем привела вся эта эпопея =)

Как попасть в инвестиционный банк. Личный опыт

Расскажу, как я подходил к отбору в инвестиционные локальные и Bulge Bracket банки, попал в ВТБ и Goldman Sachs, а также поделюсь материалами для подготовки. [Читать подробнее об курсе Investment Banking Interview Prep] О себе После окончания МГИМО получил оффер в IBD и Structuring департаменты банка VTB Capital. В итоге присоединился к команде Structuring, где занимался решениями в области сложных M&A / Private Equity сделок, а также структурным финансированием и управлением рисками на валютных, процентных и товарно-сырьевых рынках. Уже через …

CV | CL | Fit

17.10.2015

Why Consulting?

Нужен структурированный ответ, а не поток сознания Прежде чем отвечать на этот вопрос, стоит сделать небольшое исследование (поиск в интернете, общение с консультантами, профессиональная литература) и понять для себя, что представляет из себя работа в консалтинге и какие её аспекты тебе интересны больше всего и / или перекликаются с твоим предыдущим профессиональным или студенческим опытом. О том, что такое консалтинг, написано множество книг, и настоятельно рекомендую прочитать несколько из них, как минимум The McKinsey Approach to Problem-Solving (всего 27 страниц!). В целях …

MBA

01.11.2015

01. MBA: выбор программы, план подготовки

Первая статья из серии “Из Бутово в Стэнфорд” Ноябрь 2015. Я начинаю рассказ о поступлении на MBA в режиме (почти) реального времени! Сидя дома в Южном Бутово (отсюда название), по выходным буду последовательно готовить пакеты документов на программы Stanford GSB MBA и Wharton MBA 2016-2018 и параллельно рассказывать вам о всех деталях подготовки, трудностях, с которыми я буду сталкиваться, полезных материалах и идеях и прочих life hacks – и, конечно, о всех шишках, которые набью по дороге. В итоге из …

Источник

Привет! Меня зовут Азат, я студент 3 курса Факультета Компьютерных Наук ВШЭ. На днях ко мне обратился знакомый с Экономики ВШЭ и попросил помочь с решением задач вступительного экзамена в ШАД. Мы с однокурсником Даниилом посмотрели на задания, они показались нам довольно сложными, но очень интересными, захотелось поломать над ними голову. В итоге мы прорешали 1 из вариантов 2019 года и хотим показать наши решения миру.

Задача 1

Заполните третий столбец матрицы

$frac{1}{6} left( begin{array}{ccc} 5&-2&?\-2&2&?\-1&-2&? end{array} right)$

если известно, что это матрица ортогональной проекции на некоторую плоскость.

Решение

Назовём эту матрицу

$A$ , воспользуемся свойством ортогональных проекторов:

$A^2=A$ и займёмся арифметикой:

$A^2 = frac{1}{36} left( begin{array}{ccc} 5&-2&x\-2&2&y\-1&-2&z end{array} right) left( begin{array}{ccc} 5&-2&x\-2&2&y\-1&-2&z end{array} right) = frac{1}{36} left( begin{array}{ccc} 29-x & * & * \ -14-y & * & * \ -1 - z & * & * end{array} right)$

$= frac{1}{6} left( begin{array}{ccc} 5&-2&x\-2&2&y\-1&-2&z end{array} right) = A$

Нам необязательно считать 2 и 3 столбец, информации в первом достаточно для решения, на экзамене так можно было бы сэкономить время.

Получаем тривиальную систему:

$left{ begin{array}{l} 29-x = 5 cdot 6 \ -14-y = -2 cdot 6 \ -1-z = -1 cdot 6 end{array} right. Leftrightarrow left{ begin{array}{l} 29 - x=30 \ -14 -y = -12 \ -1-z = -6 end{array} right. Leftrightarrow left{ begin{array}{l} x = -1 \ y=-2 \ z = 5 end{array} right.$

Таким образом, мы заполнили 3 столбец, получив в итоге матрицу

$A = frac{1}{6} left( begin{array}{ccc} 5&-2&-1\-2&2&-2\-1&-2&5 end{array} right)$

Задача 2

Что вы можете сказать о сходимости (абсолютной или условной) ряда

$sum_{n=1}^{infty} (n+2019)a_n$ , если известно, что ряд

$sum_{n=1}^{infty} (n-2019)a_n$ сходится (а) абсолютно, (б) условно?

Решение

Введём обозначения:

$S = sum_{n=1}^{infty} (n+2019)a_n, T = sum_{n=1}^{infty} (n-2019)a_n.$

$S' = sum_{n=1}^{infty} |n+2019| |a_n|, ; T' = sum_{n=1}^{infty} |n-2019| |a_n|$

$A = sum_{n=1}^{infty} a_n, ; A' = sum_{n=1}^{infty} |a_n|$

Докажем вспомогательное утверждение (1).

Ряд

$sum_{n=1}^{infty}(n + a)a_{n}$ сходится

$Rightarrow A' = sum_{n=1}^{infty}a_{n}$ сходится

Для этого представим второй ряд как

$sum_{n=1}^{infty} frac{(n+a)a_{n}}{n+a}$ (кроме, может быть, выколотой точки -a).

Заметим, что ряд можно представь как

$sum_{n=1}^infty alpha_n beta_n$ , где

$alpha_n = frac{1}{n+a}, beta_n =(n + a)a_n$ . Отбросим члены до

, это не повлияет на сходимость. Тогда выполнены все условия признака Дирихле сходимости ряда. А именно:

1. Последовательность частичных сумм

$B_n = sum_{k=1}^n beta_k$ ограничена, так как ряд

$sum_{n=1}^infty beta_n$ сходится.
2.

$alpha_n geqslant alpha_{n+1}$
3.

$lim_{ntoinfty} alpha_n = 0$

Значит, ряд сходится. Хорошо, теперь приступим к заданию.

a) T сходится абсолютно, то есть ряд

$T' = sum_{n=1}^{infty} |n - 2019| |a_n|$ сходится. Разобьём эту сумму:

$T' = sum_{n=1}^{2018} |n - 2019| |a_n| + sum_{n=2019}^{infty} |n-2019| |a_n| = ldots$

Мы можем без влияния на сходимость заменить первые

элементов, тогда получим:

$ldots = sum_{n=1}^{2018} (n - 2019) |a_n| + sum_{n=2019}^{infty} (n-2019) |a_n| = sum_{n=1}^{infty} (n - 2019) |a_n|$

Отсюда, пользуясь утверждением (1), получаем что

$sum_{n=1}^{infty} |a_n|$ сходится.

Выкинем первые

членов каждого из этих рядов (опять же, это не влияет на их сходимость) и рассмотрим разность:

$S'-T' = sum_{n=2019}^{infty} ((n+2019) - (n-2019))|a_n| = 4038 sum_{n=2019}^{infty} |a_n|$

А мы уже знаем, что ряд

$A' = sum_{n=1}^{infty} |a_n|$ сходится. Тогда получается, что ряд

— это сумма 2 сходящихся рядов. Ну значит и он сам сходящийся.

б)

$ T $ сходится условно, то есть ряд

$ T $ сходится, а ряд

$ T' $ — нет.

Докажем, что тогда ряд

$ S $ тогда тоже сходится условно.

Опять же, из сходимости ряда

$ T $ с помощью утверждения (1) следует сходимость ряда

$ A $ . Из тех же соображений о разности, что и в предыдущем пункте, применённых теперь к

$ S $ и

$ T $ , получим, что ряд

$ S $ сходится. Осталось лишь доказать, что ряд

$ S' $ не сходится.

Будем действовать от противного. Пусть

$ S' $ сходится. Тогда, отбросив первые

членов

$ S' $ и

$ T' $ , поймём, что:

$sum_{n=2019}^{infty} |n-2019||a_n| leq sum_{n=2019}^{infty} |n+2019||a_n|$

так как

Но эти ряды положительные, поэтому если сходится больший из них, то сходится и меньший. Значит

$ T' $ сходится, противоречие.

Задача 3

Алёна очень любит алгебру. Каждый день, заходя на свой любимый алгебраический форум, она с вероятностью

$frac14$ находит там новую интересную задачу про группы, а с вероятностью

$frac{1}{10}$ интересную задачку про кольца. С вероятностью

$frac{13}{20}$ новых задач на форуме не окажется. Пусть

$X$ — это минимальное число дней, за которые у Алёны появится хотя бы одна новая задача про группы и хотя бы одна про кольца. Найдите распределение случайной величины

$X$ . В ответе должны участвовать только компактные выражения (не содержащие знаков суммирования, многоточий и пр.).

Решение

Нам нужно найти

. Для этого надо понять на пальцах, в каком случае

. Первый случай — когда в каждый из предыдущих

дней либо не было задач, либо были только про группы, а в

$k$ -ый попалась задача про кольца. Второй случай — когда в каждый из предыдущих

дней либо не было задач, либо были только про кольца, а в

$k$ -ый попалась задача про группы. На самом деле мы оба раза учли не подходящий случай, когда все предыдущие

$k-1$ дней задач не было вообще. С поправкой на это ответ будет таким:

$P[x=k] = left( left( frac{13}{20} + frac{1}{4} right)^{k-1} - left( frac{13}{20} right)^{k-1}right) cdot frac{1}{10} +$

$left( left( frac{13}{20} + frac{1}{10} right)^{k-1} - left( frac{13}{20} right)^{k-1}right) cdot frac{1}{4}$

Задача 4

Дан массив

вещественных чисел, отсортированный по возрастанию, а также числа

$p$ ,

$q$ ,

$r$ . Предложите алгоритм, строящий массив

, состоящий из чисел

, где

, также отсортированный по возрастанию. Ограничение по времени —

$O(n)$ , по дополнительной памяти —

$O(n)$ .

Решение

Сначала предположим, что

Изобразим нашу функцию.

Заметим, что:

$forall x: x > -frac{q}{2p}$ после применения

порядок остаётся прежним.
2.

$forall x: x leq -frac{q}{2p}$ после применения

порядок будет обратным.

То есть для «правой» части после применения к каждому значению функции

$f$ подпоследовательность остаётся правильно отсортированной, для левой части она становится отсортированной в обратном порядке.

Тогда бинпоиском за

найдём место в

$ A $ , в котором массив делится на эти самые доли. Сделаем reverse левой части. Применим ко всем элементам функцию

$ f $ . Получили 2 отсортированных массива. С помощью процедуры merge за

по времени и по памяти получим целиком отсортированный массив.

В случае

решим задачу для

$ -f $ , а затем сделаем reverse всего массива и домножим каждое значение

на -1. Получим правильный результат.

В случае

порядок зависит от знака

$ q $ .

$q > 0 Rightarrow f(x_i) leq f(x_{i+1}) , forall i$
2.

$q < 0 Rightarrow f(x_i) geq f(x_{i+1}) , forall i$

И построение в этом случае сводится к применению функции ко всем значениям. Только в случае

за

надо ещё сделать reverse. В случае когда

порядок уже правильный.

Задача 5

Вещественнозначная функция

$ f $ определена на отрезке

и дифференцируема на нём. Докажите, что найдётся точка

, для которой

Решение

Давайте докажем от противного. Пусть

Сначала посмотрим, что будет происходить при равенстве:

$frac{df}{dx} = 1 + f^2 Leftrightarrow int frac{df}{1+f^2} = int dx$

Обозначим эту функцию как

. Заметим, что

. То есть мы пользуемся тем, что функция

$ f $ растёт не менее быстро, получаем, что и разница с изначальной точкой будет не меньше, чем у

$ g $ .

Функция

$ g $ у нас имеет константу

$ C $ . Примем значение этой константы таким, что

. Тогда:

Мы знаем, что

. Тогда на

существует хотя бы одна точка

$ x' $ такая, что

$x'+C = frac{pi}{2} + pi k$ (потому что шаг

). В этой точке

. При этом мы знаем, что

Получили, что в какой-то из точек

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

Задача 6

Квадратная вещественная матрица

$ A $ такова, что

$A^text{T} = p(A)$ , где

— многочлен с ненулевым свободным членом. Докажите, что

$ A $ обратима. Верно ли, что для любого оператора

$varphi : mathbb{R}^n to mathbb{R}^n$ найдётся многочлен

и некоторый базис, в котором матрица

удовлетворяет условию

$A^text{T} = p(A)$ ?

Решение

В начале, покажем, что

, распишем подробно:

Отсюда можно получить, что

1. Будем доказывать от противного. Пусть матрица

$ A $ необратима. Тогда существует вектор

такой, что

. Тогда ещё можно сказать, что

. Теперь распишем это:

$= p_n (x^T A^T) (A^T)^{n-1} x + ldots + p_1 x^T A^T x + p_0 x^T E x$

Теперь пользуемся тем, что

Но мы знаем, что

. Получили противоречие.

2. Рассмотрим линейный оператор

$ phi $ с матрицей

$A = begin{pmatrix} 0 & 1 \ 0 & 0 end{pmatrix}$ в стандартном базисе.

Тогда в любом другом базисе матрица будет иметь вид

$B = C^{-1} A C$ , где

$ C $ — матрица перехода.

Заметим, что

, значит

. Тогда

$B^n = C^{-1} A^n C = 0 ; forall n geq 2$ .

Пусть

. Так как все степени выше 1 обнуляются,

При этом

, так как иначе, пользуясь первым пунктом, можем получить, что матрица

$ B $ обратима, а это не так (т.к.

Вспомним, что

Распишем:

Теперь рассмотрим несколько случаев:

Подставим в другое место:

Наша матрица размерности всего 2, поэтому вполне можем расписать поэлементно:

$left{ begin{array}{l} b_{11} + b_{11} = 0 \ b_{12} + b_{21} = 0 \ b_{21} + b_{12} = 0 \ b_{22} + b_{22} = 0 end{array} right. Rightarrow left{ begin{array}{l} b_{11} = b_{22} = 0 \ b_{12} = -b_{21} \ end{array} right.$

Но мы знаем что

. Распишем определитель:

$operatorname{det} B = 0 cdot 0 - b_{12}(-b_{12}) = b_{12}^2 = 0 Rightarrow b_{12} = b_{21} = 0 Rightarrow B = 0$

.
Получили противоречие. Матрица оператора

$ phi $ в стандартном базисе ненулевая, она не может быть нулевой в другом базисе.

Тогда после подстановки получаем

. Тогда

При этом

$(B^T B)_{ii} = sum_{k=1}^n (B_{ki})^2 = 0 ; forall i Rightarrow B_{ki} = 0 ; forall k, i Rightarrow B = 0$

И снова получаем противоречие.

Здесь тогда тоже получаем, что

Значит нет многочлена и базиса в котором матрица

$ A $ оператора

$ phi $ представима, как

. Что и требовалось доказать.

Задача 7

Дан граф с

$ 30 $ вершинами. Известно, что для любых

$ 5 $ вершин в графе есть цикл длины

$ 5 $ , содержащий эти вершины. Докажите, что найдётся

$ 10 $ вершин, попарно соединённых рёбрами друг с другом.

Решение

Сначала покажем, что диаметр графа

Выберем 2 самые удалённые друг от друга вершины

$ u $ и

$ v $ и 3 произвольные. По условию дано, что любые 5 вершин составляют цикл. Значит есть и цикл, состоящий из этих 5 вершин. В этом цикле путь от

$ u $ до

$ v $ будет максимум 2 (видно на картинке). Значит

Теперь зафиксируем произвольную вершину

. Мы уже сделали вывод, что до любой другой вершины графа расстояние от

$ v $ равно либо 1, либо 2. Покажем, что на «‎втором уровне»‎ не больше

$ 2 $ вершин:

Будем доказывать от противного. Пусть есть вершины

. Возьмём ещё одну произвольную вершину

. Снова, эти вершины составляют цикл. Но тогда, как бы мы ни разместили вершины в этом цикле, расстояние от

$ v $ до хотя бы одной из вершин

$ a $ ,

$ b $ или

$ c $ будет равно 1, получили противоречие.

Получили,

, то есть каждая вершина имеет степень не меньше

$ 27 $ .

Теперь попробуем с этой информацией найти клику (вершины, попарно соединённые рёбрами — то, что требуется в условии) длины 10. Найти клику размера 10 в графе

$ G $ — это то же самое, что найти независимое множество (то есть вершины, между которыми вообще нет рёбер) того же размера 10 в обратном графе

Рассмотрим

. Если в изначальном графе

$ G $ у нас степень вершины

$ v $

, то в обратном

Тогда обратный граф состоит из набора «цепей» (1) и «циклов» (2). Другие структуры невозможны из-за жёсткого ограничения

В компонентах вида (1) можно найти независимое множество размера

$left lceil{frac{m}{2}}right rceil$ , вида (2) —

$left lfloor{frac{m}{2}}right rfloor$ .

Пусть

$ k $ — общее количество компонент в обратном графе, а

$ k_1 $ — количество «цепочек». Тогда размер максимального независимого множества будет равен:

$| I | = sum_{i=1}^{k_1} left lceil{frac{m_i}{2}}right rceil + sum_{i=k_1 + 1}^{k} left lfloor{frac{m_i}{2}}right rfloor text{при условии} sum_{i=1}^{k} m_i = 30$

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

$| I | geq sum_{i=1}^{10} left lfloor{frac{3}{2}}right rfloor = 10$

То есть мы показали, что в обратном графе

максимальное независимое множество имеет размер 10 или больше, то есть в графе

$ G $ существует клика размера 10 или больше. Что и требовалось доказать.

Задача 8

Найдите предел

$lim_{n to infty} sum_{k=n}^{5n} C_{k-1}^{n-1} left( frac15 right)^n left( frac45 right)^{k-n}.$

Решение

Здесь нужно по виду формулы догадаться о теории вероятностей.

Введём случайную величину:

$xi_{n} = # text{бросков монетки до выпадания} ; n , text{орлов}$

Пусть монетка неправильная — орёл выпадает с вероятностью

$frac{1}{5}$ .

Тогда

это в точности значение под знаком суммирования:

$P[xi_n = k] = C_{k-1}^{n-1} left( frac15 right)^n left( frac45 right)^{k-n}$

$C_{k-1}^{n-1}$ — это количество возможных размещений

орлов (ещё 1 выпадает в конце).

$left( frac{1}{5} right)^n$ — это вероятность выпадения орлов на выбранных позициях.

$left( frac{4}{5} right)^{k-n}$ — это вероятность выпадения решек на оставшихся позициях.

Тогда наш предел превращается в

$lim_{n to infty} P[xi_n leq 5n].$

Заметим, что вероятность события

можно интерпретировать по-другому. Это вероятность того, что за

$ 5n $ бросков выпадет

орлов.

Введём новую случайную величину:

$S_{5n} = # text{орлов после} , 5n , text{подбрасываний}$

При этом величину можно представить как сумму элементарных:

$S_{5n} = sum_{i=1}^{5n} eta_i, eta_i = I{text{в} , i , text{бросок выпал орёл} }$

Тогда

$mathbb{E} S_{5n} = sum_{i=1}^{5n} mathbb{E} eta_i = 5n cdot frac15 = n$

Применим центральную предельную теорему к

$S_{5n}$ . Получим:

$lim_{n to infty} P[xi_n leq 5n] = lim_{n to infty} P[S_{5n} geq n] = lim_{n to infty} P[S_{5n} - n geq 0] =$

$lim_{n to infty} P[frac{S_{5n} - n}{sigmasqrt{n}} geq 0] = P[eta geq 0], eta sim N(0, 1)$

Вспоминаем, что у нас нормальное распределение симметрично относительно матожидания и получаем итоговый ответ:

$lim_{n to infty} P[xi_n leq 5n] = P[eta geq 0] = frac12$

Заключение

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

Если у вас есть другие идеи решения задач или какие-то замечания, смело пишите мне в телеграм @Azatik1000. Всегда рад ответить!

Азат Калмыков, куратор ШАД Helper

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

Источник

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

Дисциплина — ключ к успеху

Начинайте готовиться сразу, как только определились с темами. Чётко распишите план подготовки, учитывая текущую загрузку, и обязательно сделайте скидку на то, что всё может пойти не так. Занимайтесь регулярно, но без фанатизма. Не нужно зубрить 24/7: в какой-то момент наступит перенасыщение знаниями и от подготовки не будет толка.

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

Выбор трека как стратегия

Есть разные подходы к подготовке в зависимости от выбранного трека, но база неизменна. Повторите все формулировки и определения из программы, откройте варианты и контесты прошлых лет — и решайте все задачи, которые с ходу не даются. Навыки программирования оттачивайте на LeetCode, Codeforces или TopCoder, а умение рассуждать — объясняя решение задач друзьям, далёким от математики. Тренируйтесь, пока не начнёте описывать выводы стройно и понятно, на собеседованиях, помимо знаний, оценивается умение излагать ход мыслей. Учитесь задавать вопросы по задаче, это поможет, если запутаетесь в решении.

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

— Михаил Берновский, студент 1-го курса ШАДа, альтернативный трек.

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

Но это не значит, что альтернативный трек — лёгкий способ попасть в ШАД. При поступлении на него требуется опыт в IT: промышленная разработка или исследования в области data science.

Классический трек и три математических столпа

Есть три больших области знаний, в которых надо ориентироваться: математический анализ, линейная алгебра и теория вероятностей. Хорошая стратегия — досконально изучить хотя бы две, а лучше все три.

Я поступала в ШАД на 4-м курсе мехмата, поэтому математику более-менее помнила. Из книг читала «Комбинаторику» Виленкина и «Основы теории вероятностей» Жуковского. Но это всё не помогает, пока не решишь минимум 100 задач на каждый жанр.

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

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

Пример экзаменационной задачи по математическому анализу.

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

Пример экзаменационной задачи по линейной алгебре.

К экзамену по теории вероятностей, в отличие от матанализа и линейной алгебры, готовиться нужно намного основательнее. Есть много условий и ограничений в теоремах, которые важно повторить. Например, есть разные типы сходимости, и нужно помнить, какой из какого следует, какой — в центральной предельной теореме, а какой — в законе больших чисел. Желательно также повторить основные распределения и уметь с ними работать.

Пример экзаменационной задачи по теории вероятностей.

Альтернативный трек: алгоритмы и IT-опыт

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

Хотя совсем без математики не обойтись. Необходимо уметь объяснять математические задачи, а также знать базовые алгоритмы и определения из матанализа и линейной алгебры. Как минимум, дифференцировать точно нужно уметь.

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

— Леонид Курахтенков, студент 1-го курса ШАДа, альтернативный трек.

Задачи по теории вероятностей здесь будут немного проще, чем в классическом треке. Скорее всего, потребуется вычислить дискретную вероятность — решить «задачу с цветными шариками». Также нужно будет показать, что вы умеете рассуждать логически, не путаете причину и следствие и не считаете, что пример доказывает утверждение.

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

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

Какой опыт необходим для поступления на альтернативный трек? В первую очередь, конечно, индустриальная разработка, ML и продуктовая аналитика. Если у вас есть исследовательский опыт или опубликованные научные статьи, расскажите об этом в своей анкете и на собеседовании.

Как определить мотивацию

Итак, вы прошли все этапы, осталось собеседование по мотивации. Как к нему подготовиться и о чём говорить с куратором? Сначала честно ответьте на вопрос: «Зачем вам ШАД». Вы хотите подняться на новый карьерный уровень, сменить профессиональный трек или углубиться в то направление, которое уже изучаете?

Если вы учитесь в вузе на математической специальности и ищете прикладное применение своим знаниям в IT, то ШАД поможет объединить теорию и практику.

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

— Константин Гордеев, студент 1-го курса ШАДа, классический трек.

Сформулируйте мотивацию заранее, так вы поймёте, какие моменты подсветить на собеседовании, а что звучит не слишком убедительно. Обдумайте на берегу, готовы ли вы вкладываться в учёбу на 200%: важно показать, что вы не просто загорелись идеей поступить в ШАД, но и полны решимости трудиться два года. И если это так — дерзайте!

Полезные материалы

Здесь собран минимум, который пригодится для подготовки к экзаменам. Но, конечно, мы рассчитываем, что вы знакомы со всем списком рекомендуемой литературы.

1. Алгоритмы: построение и анализ (Т. Кормен, Ч. Лейзерсон, Р. Риверст, К. Штайн)

2. Задачи и теоремы линейной алгебры (В. Прасолов)

3. Основные понятия теории вероятностей (А. Колмогоров)

4. Курс теории вероятностей и математической статистики (Б. Севастьянов)

5. Курс комбинаторики А. М. Райгородского в YouTube

6. Тренажёры по написанию кода: Codeforces, LeetCode или TopCoder

7. Контесты прошлых лет

8. Задачи с экзаменов в ШАДе для классического и альтернативного треков

9. Тренировки Яндекса по алгоритмам

10. Разбор задач для поступления в ШАД

11. Архив олимпиады Putman Competition

Также рекомендуем почитать статью Виктора Рогуленко о том, как он готовился к поступлению в ШАД в 2019 году. Ждём ваших заявок и желаем удачи!

Источник

Вступительный экзамен в Школу анализа данных
3 июня 2017

Условия задач

Пусть и — два ненулевых вектора из . Верно ли, что найдется симметричная матрица , для которой ?
Непрерывная функция такова, что . Докажите, что для какого-то имеет место равенство .
Из равномерного распределения на отрезке независимо выбираются две точки и . При каких события и независимы?
В компании «Тындекс» у каждого сотрудника не менее 50 знакомых. Оказалось, что есть два сотрудника, знакомые друг с другом лишь через 9 рукопожатий (то есть кратчайшая соединяющая из цепочка из попарно знакомых людей содержит 8 промежуточных людей). Докажите, что в этой компании хотя бы 200 сотрудников.
Квадратная матрица размера nxn имеет различные собственные значения . Найдите все собственные значения (в том числе комплексные) матрицы $begin{bmatrix}0& -A\A&0end{bmatrix}$ .
Вы — воин Света, и сегодня вам нужно победить толпу из гоблинов, каждый из которых изначально имеет единиц жизни (, ). Боретесь с гоблинами вы с помощью специального магического посоха. Если ударить таким посохом по гоблину, тот сразу же теряет единиц жизни, а все остальные гоблины в толпе теряют единиц каждый (таковы магические свойства посоха). Гоблин считается побежденным, если после очередного удара его здоровье становится меньше или равно нулю. Обычная борьба с нечистью давно вам приелась, и чтобы внести разнообразие в сегодняшнюю битву, вы решили победить всех гоблинов, сделав минимально возможное число ударов посохом. Предложите алгоритм нахождения этого числа ударов. Ваш алгоритм должен иметь асимптотику по времени , затраты по памяти — .
Пусть и — две случайных булевых матрицы nxn, у которых каждый элемент равен 1 с вероятностью (значения различных элементов не зависят друг от друга). Сколько в среднем единиц будет в их произведении, если сложение и умножение происходят по модулю 2?
Исследуйте на сходимость (абсолютную и условную) ряд $sum_{k=1}^{infty}a_k$ , где $a_k=int_{0}^{frac{sin k}{k}}displaystylefrac{sin t}{t}dt$