Три шага в ШАД: как пройти вступительные и не сойти с дистанции20.03.2025 19:01

Автор: Лыков А., к.ф.-м.н., академический руководитель Школы Высшей Математики и ШАДХелпера.

В статье мы опишем этапы вступительного экзамена в ШАД, прошедшего в 2024 году. Сформулируем рекомендации по подготовке к каждому этапу и в конце разберём интересную задачу с письменного экзамена.

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

На всех этапах проверялись знания по математике, алгоритмам и программированию. На этапе собеседования дополнительно обсуждалась мотивация студента (подробнее — чуть ниже). Время на всех этапах, кроме собеседования, составляло 5 часов.

В таблице ниже мы собрали данные по задачам и проходным баллам.

	Математика	Алгоритмы/Программирование	Проходной балл*
Онлайн-тестирование	9	3	7–8 задач
Письменный экзамен	6	2	26–29 баллов — основной трек, ~20 баллов — альтернативный трек. одна задача максимум 10 баллов
Олимпиада	6	2	3 задачи

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

Онлайн-тестирование. Особенность этого этапа состоит в том, что нужно абсолютно правильно решить большинство задач. Задачи не очень сложные, но ошибаться нельзя. Решения и обоснования не проверялись — учитывался только ответ.

Один мой знакомый сдавал экзамен на мехмате МГУ по случайным процессам в течение пяти часов (вместо обычных двух). Дело было в том, что он решал все задачи, но постоянно совершал арифметические ошибки, что приводило к неверному ответу, и экзаменатор никак не мог решить, какую оценку поставить. Такой стиль решения задач не позволил бы ему пройти онлайн-тестирование в ШАД.

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

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

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

При подготовке к письменному экзамену рекомендуем решать большое количество задач и не злоупотреблять разборами. Понимать решение задачи — не то же самое, что придумать его самостоятельно. Прибегайте к разборам в крайнем случае. Старайтесь смотреть разбор лишь после того, как решили или, по крайней мере, попытались. Если у вас задача не получилась или решение оказалось неверным, поймите почему и сделайте выводы на будущее: одно дело, если вы не догадались до какой-то идеи, другое — если чего-то не знали из теории.

Удобный инструмент для подготовки — сборник задач со вступительных экзаменов в ШАД от ШАДХелпера (Решения вступительных испытаний в ШАД). Также уделяйте время тому, чтобы научиться правильно обосновывать свои решения в письменном виде. Все логические переходы должны быть обоснованы.

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

Собеседование. Собеседование состоит из трёх частей по 30 минут каждая: математика, алгоритмы, мотивация.

На математической секции первые 15 минут — блиц на 15 вопросов, затем 3 задачи на оставшиеся 15 минут. Важно не только решать задачи, но и демонстрировать владение математическим языком:

• уметь выражать свои мысли о решении или подходе к решению;

• знать точные формулировки математических определений и теорем.

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

Очень хорошо, если вы будете обсуждать с товарищами математические сюжеты. В школе ШАДХелпер (https://shadhelper.com/) для тренировки разговорной математической речи практикуют формат «Спикинг».

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

1. у него будут время и силы на учёбу;

2. он пришёл не за очередным сертификатом;

3. учёба в ШАД даст ему сильный профессиональный (или творческий) толчок.

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

На алгоритмическом собеседовании был классический лайвкодинг.

Списывание. Во время вступительных экзаменов действовала система «ЧитерНах»* — абитуриентов, заподозренных в списывании, дисквалифицировали и прекращали с ними работу. Вероятно, такие абитуриенты попадают в чёрный список и больше не могут поступать в ШАД.

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

Приведём ещё один аргумент против списывания. Известно, что:

1. программа обучения в ШАД достаточно сложна;

2. сообщество студентов ШАДа состоит из креативных и самостоятельных людей.

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

**Название вымышленное.

В нашей ранней статье 2022 года (https://habr.com/ru/articles/648497/) мы обсуждали вопросы подготовки с содержательной точки зрения. Также рекомендуем ознакомиться с ней, если вы планируете поступить в ШАД.

В конце статьи приведём интересную задачу с письменного экзамена по теории вероятностей.

Рассмотрим случайный многомерный нормальный вектор $\Psi$ в $\mathbb{R}^n$ с нулевым средним и единичной матрицей дисперсии. Артем и Леша играют в игру с нулевой суммой (число очков у одного игрока всегда равноминус числу очков у другого). Каждый игрок зафиксировал до начала игры по одному вектору (Артем) и (Леша) в $\mathbb{R}^n$ . В начале игры у каждого 0 очков. Леша получает очко в раунде , если

$\text{sign} \langle \psi_k, a \rangle \, \text{sign} \langle \psi_k, l \rangle > 0,» src=«https://habrastorage.org/getpro/habr/upload_files/647/140/c6b/647140c6bd97ed3396f36820259c93af.svg» /><p>а Артем, если меньше, иначе просто происходит переход к следующему раунду. Здесь</p><img alt=$ 0, \end{cases}» src=«https://habrastorage.org/getpro/habr/upload_files/d23/f59/5e0/d23f595e08bef4580fc291c8a926ad6b.svg» />

и $\langle\cdot\, ,\cdot\rangle$ — стандартное скалярное произведение в $\mathbb{R}^n$ .
$\{\psi_i\}_{i = 1}^{\infty}$ — реализации случайного вектора $\Psi$ , полученные независимо друг от друга. В каждом раунде рассмотрим число очков у Артема, деленное на . К чему оно стремится при $k \to \infty$ ? В качестве ответа укажите искомую величину при a = (1,2,3) и l = (1,0,1) .

Решение

Число очков у Артёма после раундов, делённое на :

$A_k = \frac{1}{k}\sum_{i=1}^k \xi_i$

где

$\xi_i = \begin{cases} 1, & \mathrm{sign}\langle \psi_i,a \rangle \mathrm{sign}\langle \psi_i,l \rangle \leqslant 0 \\ -1, & \mathrm{otherwise} \end{cases}$

По усиленному закону больших чисел величины A_k стремятся к $E \xi$ при $k \to \infty$ с вероятностью единица, где

$E \xi =p - (1-p) = 2p-1,$ $p = P \{ \xi = 1 \} = P \{ \mathrm{sign} \langle \Psi, a \rangle \mathrm{sign} \langle \Psi, l \rangle \leqslant 0 \}.$

Приведём два способа подсчёта вероятности .

Способ 1. Алгебраический

Первый способ основан на использовании свойств гауссовских векторов.
Так как вектор $\Psi$ нормальный, то случайные величины $X = \langle \Psi, a \rangle$ и $Y = \langle \Psi, l \rangle$ также образуют нормальный вектор с нулевым средним и

$\sigma_X^2 = DX = \langle a, a \rangle, \quad DY = \langle l, l \rangle, \quad \mathrm{cov}(X,Y) = \langle a, l \rangle.$

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

$Y = \beta X + Z,$

для некоторой константы $\beta$ и нормальной случайной величины независимой с . Константа $\beta$ находится по формуле:

$\beta = \frac{\mathrm{cov}(X,Y)}{DX} = \frac{\langle a, l \rangle}{\langle a, a \rangle}$

Дисперсия :

$\sigma_Z^2 = DZ = DY - \beta^2 DX = \langle l, l \rangle - \frac{\langle a, l \rangle^2}{\langle a, a \rangle}.$

Продолжим вычисление :

$p = P \{\mathrm{sign}X \cdot \mathrm{sign}Y \leqslant 0 \} = P \left \{ \frac{Y}{X} \leqslant 0 \right \} = P \left \{ \beta + \frac{Z}{X} \leqslant 0 \right \} = P \left \{ \beta + \frac{ \sigma_Z}{ \sigma_X} \frac{z}{x} \leqslant 0 \right \},$

где z, x — независимые стандартные нормальные случайные величины. Хорошо известно***, что их отношение $\eta= z/x$ имеет распределение Коши с плотностью

$p_{ \eta} (x) = \frac{1} {\pi} \frac{1} {1+x^2}.$

Получаем, что

$p = P \left \{ \eta \leqslant - \beta \frac{\sigma_X}{\sigma_Z} \right \} =\int_{- \infty}^{- \beta \frac{\sigma_X}{\sigma_Z}} p_{ \eta}(x) dx= \frac{1}{2}+\frac{1}{\pi} \mathrm{arctg} \left(- \beta \frac{\sigma_X}{\sigma_Z} \right)$ $= \frac{1}{2} + \frac{1}{\pi} \mathrm{arctg} \left(- \frac{ \langle a, l \rangle}{\sqrt{\langle l, l \rangle \langle a, a \rangle - \langle a, l \rangle^2}} \right) = \frac{1}{2} + \frac{1}{\pi} \mathrm{arctg} \left(-\frac{\cos \alpha}{\sin \alpha} \right)$

где $\alpha \in [0, \pi]$ — угол между векторами a, l и

$\cos \alpha = \frac{ \langle a, l \rangle}{\sqrt{ \langle l, l \rangle \langle a, a \rangle}}.$

Продолжим вычисления

$p = \frac{1}{2} + \frac{1}{\pi} \mathrm{arctg} \frac{\sin \left(\frac{\pi}{2} + \alpha \right)}{\cos \left(\frac{\pi}{2}+ \alpha \right)} = \frac{1}{2} + \frac{1}{\pi} \left( \alpha - \frac{\pi}{2} \right) = \frac{\alpha}{\pi}= \frac{1}{\pi} \mathrm{arccos} \frac{\langle a, l \rangle}{\sqrt{\langle l, l \rangle \langle a, a \rangle}}.$

При значениях a, l из условия получаем:

$E \xi = 2p-1 = -0.5456289483$

***Пишите в комментариях свои доказательства этого факта.

Способ 2. Геометрический

Второй способ вычисления вероятности основан на сведении задачи к геометрическим вероятностям.

Предположим вначале, что все вектора заданы на плоскости. Заметим, что вероятность зависит только от модулей и . Поэтому, без потери общности, можно считать, что концы этих векторов лежат на единичной окружности с центром в начале координат. Для определённости положим, что совпадает с e_1 . Заметим, что

$p = P \{ \mathrm{sign} \langle \frac{\Psi}{|\Psi|}, a \rangle \mathrm{sign} \langle \frac{\Psi}{|\Psi|}, l \rangle \}= P \{\mathrm{sign}\langle V, a \rangle \mathrm{sign} \langle V, l \rangle \leqslant 0 \}$

где мы обозначили $V = \frac{\Psi}{|\Psi|}$ .

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

Рис. 1

На рисунке 1 мы закрасили сектора круга, опирающиеся на соответствующие дуги окружности, $\alpha \in [0, \pi]$ — угол между векторами a, l и

$\cos \alpha = \frac { \langle a, l \rangle} { \sqrt{ \langle l, l \rangle \langle a, a \rangle}}.$

Жёлтая линия — перпендикуляр к вектору Артёма . Если точка лежит на нижней закрашенной дуге, то образует тупой угол с и острый с . Если на верхней, то наоборот. Длина закрашенных дуг равна $2\alpha$ . Значит искомая вероятность

$p = \frac {2 \alpha} {2 \pi} = \frac {\alpha} {\pi}.$

Наши построения работают для $\alpha \leqslant \frac { \pi} {2}$ . Аналогичные рассуждения применимы и для $\mathbb{R}^n$ .

Теперь перейдем к общему случаю векторов в $\mathbb{R}^n$ .
Выберем ортонормированный базис в $\mathbb{R}^n$ таким образом, чтобы первые два вектора лежали в плоскости, натянутой на a, l . Обозначим $\Psi'$ проекцию $\Psi$ на эту плоскость. Тогда легко видеть, что

$p = P \{ \mathrm{sign} \langle \Psi', a \rangle \mathrm{sign} \langle \Psi', l \rangle \leqslant 0 \}.$

$\Psi'$ является стандартным нормальным вектором на плоскости. Поэтому задача свелась к двумерном случаю, рассмотренному на предыдущем шаге.

Тем самым задача полностью решена.