Разбор вступительного экзамена ШАД-2015 и воспоминания выпускника 2017 года

МЕНЮ

Искусственный интеллект
Поиск
Регистрация на сайте
Помощь проекту

ТЕМЫ

Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация

RSS

RSS новости

Введение

В мае далёкого 2015 года я заканчивал бакалавриат факультета общей и прикладной физики МФТИ. В основном я занимаюсь квантовой теорией поля, но в тот момент я решил, что хотелось бы больше вникнуть в современный мир компьютерных наук, что можно попробовать совместить МФТИ с ШАД Yandex (две магистратуры). ШАД тогда уже был у всех на слуху, вокруг только и твердили, какой там жёсткий курс алгоритмов, мне понравился сайт (лол), тематика курсов, и я решился поступать. В этом посте я хотел бы рассказать о том, как происходило моё поступление в ШАД, рассказать своё решение экзаменационного варианта (разборов ШАДовских заданий на просторах рунета не очень-то много) и поговорить о том, что понравилось / не понравилось в этом замечательном заведении.

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

После онлайн-этапа меня пригласили на экзамен. К экзамену я готовился около недели, и сам по себе он доставил мне большое удовольствие. За 4 часа необходимо было решить 7 задач по математике и составить один алгоритм (всего 8 заданий). Метематика требуется самая разнообразная: линейная алгебра, мат. анализ (чуть ли не $inline$epsilon-delta$inline$ формализм), комбинаторика и теор. вер., графы, преобразование Фурье и т.д. Мне кажется, это очень правильно от поступающих требовать именно знания математики, а не каких-нибудь там языков или скиллов (вообще в дальнейшем оказалось, что ШАД ориентирован именно на знание по сути, а не на технические детали).

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

Мой экзамен

Задача 1

Квадратная матица $inline$A$inline$ такова, что $inline$mbox{tr} AX = 0$inline$ для любой бесследовой $inline$X$inline$. Докажите, что матрица $inline$X$inline$ скалярная.

Решение

Эта задача сразу напомнила мне другую, немного более сложную задачу с физтеховского экзамена по линейной алгебре в первом семестре, где нужно было доказать, что коммутирует со всеми матрицами только скалярная матрица. Как и там, здесь нужно воспользоваться тем, что матрица $inline$X$inline$ любая, а значит, рассматривая матрицы $inline$X$inline$ различного вида, мы можем наложить ограничения на марицу $inline$A$inline$.

Сперва рассмотрим матрицу $inline$X$inline$ вида $inline$X_{i j} = delta_{ik} delta_{j l}$inline$, то есть матрицу, у которой все элементы 0 кроме единички, стоящей в $inline$k$inline$-той строке на $inline$l$inline$-той позиции. Так как мы помним, что $inline$X$inline$ — бесследовая матрица, $inline$l eq k$inline$. Тогда уравнение из условия переписывается в виде (если в формуле индекс повторяется дважды, по нему подразумевается суммирование)

$$display$$ mbox{tr}AX = A_{ij} X_{ji} = A_{ij} delta_{ik} delta_{jl} = A_{kl} = 0;(k eq l).$$display$$

То есть, лёгким движением руки мы доказали, что в матрице $inline$A$inline$ вне диагонали стоят только ноли. Если отбросить индексы, то мы всего лишь умножили матрицу $inline$A$inline$ на матрицу специального вида и получили некое ограничение.

Теперь мы знаем, что матрица $inline$A = mbox{diag}(lambda_1, lambda_2, ldots, lambda_n)$inline$ — диагональная. Как доказать, что все её собственные числа равны? Для этого рассмотрим теперь матрицы $inline$X = delta_{i l} delta_{j l} - delta_{i k} delta_{j k}$inline$, то есть матрицы, у которых на $inline$l$inline$-том элементе диагонали стоит $inline$+1$inline$, а на $inline$k$inline$-том — $inline$-1$inline$. Аналогично умножив матрицы и взяв след, мы получаем $inline$lambda_l - lambda_k = 0$inline$ (след оказался равен всего лишь разности пары собственных чисел). По условию для любых $inline$k,;l$inline$ это равенство должно выполняться, откуда следует, что все собственные числа равны, задача решена.

Задача 2

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

Решение

Эта задача меня чуть не убила, на экзамене я придумал ужасно сложное и убогое решение. Вот оно. Рекомендую в процессе чтения рисовать различные варианты в виде графов, тогда становится даже не так ужасно! Рассмотрим произвольную четвёрку студентов $inline$A$inline$, $inline$B$inline$, $inline$C$inline$, $inline$D$inline$. Пусть, от противного, из них никто не знаком со всеми остальными студентами. Но по условию один из студентов (пусть это будет $inline$A$inline$) знает всех оставшихся троих. От противного мы заключили, что есть некий другой студент $inline$X$inline$, которого $inline$A$inline$ не знает.

В этом месте сделаем финт ушами и рассмотрим четвёрку $inline$A$inline$, $inline$B$inline$, $inline$C$inline$, $inline$X$inline$. В этой четвёрке должен быть студент, который знает всех троих. Это не может быть $inline$A$inline$ или $inline$X$inline$, так как они не знакомы, поэтому пусть $inline$B$inline$ знает всех троих (не важно, это может быть и $inline$C$inline$, пока симметрия между ними не нарушена).

Так как мы работаем от противного, то каждый студент в четвёрке $inline$ABCD$inline$ не знает кого-либо. Если в случае с $inline$A$inline$ мы были вынуждены взять незнакомца со стороны, то в случае с $inline$B$inline$ возможны два случая. Если $inline$B$inline$ не знает кого-то изнутри четвёрки $inline$ABCD$inline$, то это может быть только $inline$D$inline$, так как $inline$A$inline$ и $inline$C$inline$ он уже знает. Но в этом случае рассмотрим четвёрку $inline$AXBD$inline$. С учётом того, что $inline$A$inline$ не знает $inline$X$inline$ и $inline$D$inline$ не знает $inline$B$inline$, мы не можем удовлетворить условию о том, чтобы хотя бы один студент в четвёрке знал всех остальных троих.

Таким образом, $inline$B$inline$ и $inline$D$inline$ должны быть знакомы, а у $inline$B$inline$ должен быть незнакомый студент со стороны $inline$Z$inline$. Но тут и наступает конец. Рассмотрим четвёрку $inline$ABXZ$inline$. В ней невозможно устроить так, чтобы кто-то знал троих остальных студентов так как незнакомы $inline$A$inline$ и $inline$X$inline$, $inline$B$inline$ и $inline$Z$inline$, задача решена.

Задача 3

На окружности выбираются две случайные точки $inline$A$inline$, $inline$B$inline$, найди матожидание площади наименьшего из сегментов, на которые хорда $inline$AB$inline$ разбивает круг.

Решение

Как говорилось в одном анекдоте про прапорщика, «а что тут думать? трясти надо!». Зафиксируем точку $inline$A$inline$, а точку $inline$B$inline$ параметризуем углом $inline$varphi$inline$ между радиус-векторами $inline$OA$inline$ и $inline$OB$inline$. Рассмотрим углы $inline$varphi in [0, pi]$inline$. Площадь меньшего сегмента тогда будет равна $inline$S(varphi) = varphi R^2 / 2 - (1/2) R^2 sin varphi $inline$, тогда

$$display$$ar{S(varphi)} = frac{1}{pi}intlimits_{0}^{pi} dvarphi S(varphi) = (R^2 / 2 pi) intlimits_{0}^{pi} dvarphi (varphi - sin varphi) = frac{R^2}{2 pi} left(frac{pi^2}{2} - 2 ight) = pi R^2 / 4 - R^2 / pi.$$display$$

Задача 4

Дан массив из $inline$n$inline$ натуральных чисел. Предложите способ сортировки его по остатку от деления на 5 за линейное время и константную память.

Решение

В этом месте руки похолодели, я-ж не программист! Но спокойно, я же говорил, это экзамен по математике. Сортировку нужно делать in-place, так как дополнительно можно затратить только константу памяти. Зафиксируем некий текущий остаток $inline$r$inline$ (сначала $inline$r = 0$inline$, в конце $inline$r = 4$inline$) и пойдём по массиву от начала до конца указателем $inline$j$inline$. Также заведём так называемый индекс вставки $inline$i$inline$, который изначально указывает на начало массива и затем только увеличивается.

Если элемент массива $inline$A[j]$inline$ имеет остаток $inline$r$inline$, мы должны поменять его местами с $inline$A[i]$inline$. После этого индекс $inline$i$inline$ мы увеличиваем до тех пор, пока $inline$A[i] = r (mbox{mod}) 5$inline$ и останавливаем в тот момент, когда это равенство нарушается. Затем снова растим индекс $inline$j$inline$, пока снова не найдём $inline$A[j] = r (mbox{mod} 5)$inline$, чтобы его перекинуть на позицию $inline$i$inline$.

В данном алгоритме есть некий инвариант, а именно, позади индекса $inline$i$inline$ все числа уже расставлены правильно (отсортированы по остатку). При одном проходе $inline$j$inline$ по всему массиву, позади $inline$i$inline$ будут лежать все элементы, которые при делении на $inline$5$inline$ дают в остатке $inline$0$inline$. При очередном проходе та же участь постигнет тех, кто делится с остатком $inline$1$inline$ и так далее. Всего потребуется 4 прохода (пятый будет уже не нужен).

Задача 5

Исследуйте на сходимость и абсолютную сходимость ряд

$$display$$sumlimits_{n = 0}^{+infty} sin pi sqrt{n^2 + 1}. $$display$$

Решение

ШАД, ты серьёзно? Ну это-то зачем? Ладно… Запишем

$$display$$ sin pi sqrt{n^2 + 1} =sin pi n sqrt{1 + 1/n^2} = sin left(pi n + frac{pi}{2 n} + mathcal{o}(n^{-2}) ight) = (-1)^n sin left( frac{pi}{2 n} + mathcal{o}(n^{-2}) ight) = = (-1)^n left(frac{pi}{2 n} + mathcal{o}(n^{-2}) ight).$$display$$

Видно, что ряд сходится условно. Слагаемое $inline$mathcal{o(n^{-2})}$inline$ сходится по интегральному признаку, а слагаемое $inline$(-1)^n / n $inline$ сходится по признаку Дирихле. Если же рассмотреть абсолютную сходимость, надо вспомнить свойство $inline$|a + b| geqslant |a| - |b|$inline$. Слагаемое $inline$b = mathcal{o(n^{-2})}$inline$ всё ещё сходится по тому же интегральному признаку, а вот слагаемое $inline$ a sim 1/n $inline$ расходится как сумма гармонического ряда, и потому весь ряд не сходится.

Задача 6

У вас имеется неограниченное количество костей в виде всех возможных правильных многогранников. Можно ли, однократно просив некоторый набор таких костей, симулировать бросок (а) правильной 7-гранной кости, (б) правильной 15-гранной кости?

Решение

Эту задачу на самом экзамене я не успел даже прочесть, так что это было вроде домашней работы. Всего правильных многогранников пять: пирамида (4), куб (6), октаэдр (8), додекаэдр (12), икосаэдр (20). Заметим, что мы можем симулировать бросок $inline$5$inline$-гранной кости, беря остаток от деления на пять того, что выпало на икосаэдре. Аналогично, мы можем симулировать бросок трёхгранной кости, деля остаток от деления на $inline$3$inline$ от всего, что падает на пирамиде. Тогда, если $inline$d_3$inline$ и $inline$d_5$inline$ — результаты бросков таких костей, то результат броска $inline$15$inline$-гранной кости мы будем пересчитывать как $inline$d_{15} = 5 (d_3 - 1) + d_5.$inline$ Заметим, что здесь все исходы равновероятны, то есть это действительно правильная кость.

Тем не менее, бросок $inline$7$inline$-гранной кости симулировать нельзя. К данному моменту стало ясно, что если у нас честный кубик $inline$d_i$inline$, то мы можем симулировать любые делители $inline$i$inline$, а также, если у нас есть два честных кубика $inline$d_i$inline$ и $inline$d_j$inline$, мы можем симулировать произведение $inline$d_{ij}$inline$. Именно поэтому мы можем просимулировать любое число, раскладывающееся на простые множители $inline$2$inline$, $inline$3$inline$ и $inline$5$inline$ (других среди платоновых тел нет).

Предположим, что мы хотим просимулировать число, которое не раскладывается на произведение таких простых множителей. Кинем для этого $inline$N$inline$ костей $inline$d_{i_1},;d_{i_2},;ldots,;d_{i_N}$inline$, и числа, выпавшие на всех $inline$N$inline$ костях, запишем в один вектор, описывающий точку в гиперкубе размером $inline$i_1 imes i_2 imes ldots imes i_N$inline$. Если мы хотим симулировать $inline$7$inline$-гранную кость, мы должны точки в этом пространстве поделить на $inline$7$inline$ групп равного размера, что сделать нельзя, ведь иначе произведение $inline$i_1 imes i_2 imes ldots imes i_N$inline$ должно будет делиться на $inline$7$inline$, а такого мы ещё не получили.

Задача 7

Пусть $inline$A$inline$, $inline$B$inline$ — квадратные вещественные матрицы. Доказать, что $inline$ mbox{det}left(E - AB ight) = mbox{det}left(E - BA ight).$inline$

Решение

Здесь мне очень помогла формула, которую ужасно любят в теор. физике, и я сильно рекомендую её взять на вооружение тем, кто пойдёт на экзамен. Для любой матрицы $inline$A$inline$, у которой все собственные значения положительны, справедливо $inline$mbox{det}A = exp mbox{tr} log A.$inline$

Как же здесь применить нашу формулу? Я скажу сразу, мы будем раскладывать логарифм в ряд. Под логарифмом у нас будет стоять выражение вида $inline$E - AB$inline$, которое можно раскладывать в ряд, только если $inline$|AB|_2 < 1$inline$. Это совершенно полностью соответствует радиусу сходимости логарифма, но только во многомерном пространстве.

Для начале давайте переформулируем задание и докажем, что $inline$ mbox{det}left(E - lambda AB ight) = mbox{det}left(E - lambda BA ight) $inline$ для любого вещественного числа $inline$lambda$inline$, и дальше просто возьмём $inline$lambda = 1.$inline$ Зачем это нужно? Это нужно для того, чтоб сделать норму матриц $inline$|AB|_2$inline$ меньше $inline$1$inline$. Когда рассмотрено очень маленькое $inline$lambda$inline$, можно смело написать такую цепочку (под следом матрицы можно передвигать по циклу):

$$display$$mbox{det}left(E - lambda AB ight) = exp mbox{tr} log(E - lambda AB) = exp mbox{tr}left(-lambda AB - frac{lambda^2 (AB)^2}{2} - frac{lambda^3 (AB)^3}{3} - ldots ight) = = exp mbox{tr}left(-lambda BA - frac{lambda^2 (BA)^2}{2} - frac{lambda^3 (BA)^3}{3} - ldots ight) = mbox{det}(E - lambda BA).$$display$$

Здесь мы нагло использовали свойство $inline$mbox{tr}(AAAAAldots AAABBBBBldots BBB) = mbox{tr}(BBBBBldots BBBAAAAAldots AAA).$inline$

Хорошо, мы доказали эту формулу для некоторого отрезка $inline$lambda$inline$ вблизи ноля. Как же теперь распространить её на все $inline$lambda$inline$, в частности $inline$lambda = 1$inline$? Заметим, что в левой и правой части доказанной формулы стоят многочлены по $inline$lambda$inline$ (ведь в определитель входят только произведения)! То есть, мы доказали, что два многогочлена совпадают на отрезке, но отсюда сразу следует, что они совпадают всюду на числовой прямой.

Задача 8

За столом сидят $inline$n$inline$ старателей, перед каждым из которых лежит кучка золотого песка. Каждую минуту все старатели берут половину песка из левой кучки и половину из правой кучки и кладут себе. Опишите асимптотическое поведение количества песка в кучках для произвольного $inline$n$inline$.

Решение

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

$$display$$a(x, t + 1) = frac{a(x - 1, t) + a(x + 1, t)}{2},$$display$$

где $inline$a(x, t)$inline$ — количество золота у старателя, сидящего в позиции $inline$x$inline$ во время $inline$t$inline$. Координата $inline$x$inline$ замкнута в окружность, $inline$x = 0, 1, ldots, n - 1$inline$.

Такие вещи решаются множеством способов, но самый естественный — дискретное преобразование Фурье. Мы имеем дело с функцией, периодической по $inline$x$inline$, и её можно и нужно разложить в конечную сумму Фурье по $inline$x$inline$:

$$display$$a(x, t) = frac{1}{N} sumlimits_{k = 0}^{n - 1} sumlimits_{omega = 0}^{T - 1} ilde{a}(k, t) e^{2 pi i k x / n} .$$display$$

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

$$display$$ ilde{a}(k, t + 1) = frac{e^{2 pi i k / n} ilde{a}(k, t) + e^{-2 pi i k / n} ilde{a}(k, t)}{2} = cos(2 pi k /n) ilde{a}(k, t).$$display$$

Для фиксированного $inline$k$inline$ это само по себе уравнение, которое аналогично решается ещё одним преобразованием Фурье. Будем обозначать преобразование Фурье по координате тильдой, а по координате + времени — крышечкой. Записав

$$display$$ ilde{a}(k, t) = frac{1}{T}sumlimits_{omega = 0}^{T - 1} hat{a}(k, omega)e^{2 pi i omega t / T},$$display$$

подставив это в последнее уравнение и снова уравняв экспоненты, мы получаем

$$display$$e^{2 pi i omega} = cos (2 pi i k).$$display$$

Мы получили так называемое дисперсионное соотношение. То есть, плоские волны здесь могут быть не с произвольными $inline$k,;omega$inline$, а только с теми, которые подчиняются этой формуле. Это дисперсионное соотношение — переформулировка исходного уравнения в новом базисе. Пусть мы зафиксировали какой-то импульс $inline$k$inline$ и пытаемся найти соответствующую частоту $inline$omega$inline$, которая может существовать в такой системе.

Если косинус справа по модулю будет меньше единицы, то в комплексную экспоненту придётся подставлять комплексную частоту $inline$omega = omega' + i omega''$inline$ (у которой будет мнимая часть). Как легко видеть, мнимая часть этой экспоненты тогда будет положительной ($inline$omega'' > 0$inline$), тогда в экспоненту она войдёт как $inline$-2 pi omega'' / T$inline$ и уменьшит её модуль вслед за косинусом. Но, к счастью, такие частоты быстро отправятся на покой. Действительно, если мы посмотрим, какой вклад будут давать моды с такими частотами, мы увидим, что они будут по времени экспоненциально затухать. Такие моды в асимптотику давать вклада не будут.

Поэтому у нас остаётся два случая. Если $inline$n$inline$ — нечётное, то косинус бывает равным $inline$1$inline$ по модулю лишь однажды, когда $inline$k = 0$inline$. В этом случае $inline$omega = 0$inline$. Эта плоская волна — всего лишь среднее. Получается, при нечётных $inline$n$inline$ никакой антересной динамики в бесконечности нет: богатство старателей сходится к среднему от того, что было изначально:

$$display$$ a(x, t) o frac{1}{N} sumlimits_{b = 0}^{n - 1} a(b, 0).$$display$$

Если же $inline$n$inline$ нечётное, то косинус ещё может быть равен $inline$-1$inline$, если $inline$k = n / 2$inline$, а тогда возможно дополнительное решение $inline$omega = T / 2,; ilde{a}(k, t) = hat{a}(k, T / 2) (-1)^t/ T$inline$ (в сумме выживает только слагаемое, в котором вещественная $inline$ omega $inline$, его мы и записали). В этом случае

$$display$$a(x, t) = frac{1}{N} a(n / 2, t) = frac{1}{NT} (-1)^x (-1)^t hat{a}(n / 2, T / 2).$$display$$

Аналогично остаётся всего одно слагаемое, его и пишем. Теперь про решение нам почти всё известно. Это некая вот такая конструкция, которая меняет знак как при шаге по времени, так и при шаге по пространству. Заметьте, что если бы здесь $inline$n$inline$ не было чётным, это бы нарушило цикличность по окружности. Осталось только найти значение коэффициента.

Взглянем на обратное преобразование Фурье:

$$display$$hat{a}(n / 2, T / 2) (-1)^t / T= ilde{a}(n / 2, t) = sumlimits_{x = 0}^{n - 1} a(x, t) e^{-2 pi i (n / 2) x / n}.$$display$$

При $inline$t = 0$inline$ слева стоит $inline$hat{a}(k, omega) / T$inline$, а справа стоит просто $inline$sumlimits_{x = 0}^{n - 1} a(x, 0) (-1)^x$inline$, то есть альтернированная сумма богатств в исходный момент времени. Таким образом, мы получаем

$$display$$ a(x, t) o frac{(-1)^x (-1)^t}{N}sumlimits_{b = 0}^{n - 1} a(b, 0) (-1)^b + frac{1}{N} sumlimits_{b = 0}^{n - 1} a(b, 0).$$display$$

Послесловие

За контрольную дали семь очков из восьми. Я не написал про трюк с $inline$lambda$inline$ в задаче про матрицы, а просто раскладывал — этого не заметили. Затем было собеседование. Меня ничего не спросили про экзамен, просто поговорили за жизнь, зачем я хочу поступать в ШАД (подготовьте ответ на этот вопрос!). Ребят, у кого было поменьше задач, просили решать что-то на месте, так тчо лучше придти в боевом расположени духа. Также будет возможность отапеллировать недоставленных за контрольную очков.

Обучение в ШАД мне сильно-сильно понравилось. Здесь всё время толкают какую-то теорию, читают по самым свежим статьям, а не по 50-летним книгам, и, самое главное, теория всегда подкреплена очень подходящей и логичной практикой.

Плюсы:

  1. Очень крутые курсы, разбегаются глаза: есть на любой вкус, от очень практических до очень теоретических, почти все современные отрасли компьютерных наук по свежим статьям.
  2. Преподаватели в основной массе огонь, не лень было после лабы вечером ехать на другой конец Москвы послушать.
  3. Классная подача материала, всё записывается на видео, можно не ходить. Сдавать можно удалённо, но ходить всё равно хочется.
  4. Здоровские однокурсники!

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

Поступайте в ШАД! И, да, забыл, разберитесь обязательно с формулой полного разложения определителя

$$display$$ mbox{det} A = epsilon^{i_1 i_2 i_3ldots i_N} a_{1 i_1} a_{2 i_2} ldots a_{N i_N}.$$display$$


Источник: habrahabr.ru

Комментарии: