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

Устройство в крупную IT компанию — непростой и порой длительный процесс. Работода‑ тели в ходе многочисленных собеседований проверяют кандидата со всех сторон. В частности, оценивают его способности решать задач и технические навыки. В статье мы расскажем о том, как готовиться к прохождению технических собеседований по математике и алгоритмам в IT компании, как в целом проходит процесс устройства на работу. (1)

При устройстве в иностранный хедж‑фонд XQuant на среднюю позицию у вас будет два тестирования по математике и программированию, одно hr собеседование, шесть технических собеседований, три интервью с биг боссами, одно интервью на сошиал фит, часть интервью на английском языке. При устройстве аналитиком в российские IT‑компании (Яндекс, Авито, Тинькофф,...) количество технических собеседований может варьироваться (по нашим оценкам от 2 до 7), но минимум два по алгоритмам и математике пройти придётся.

Для оценки IQ кандидата (2) или того, насколько быстро, оригинально и глубоко он может мыслить, ему предлагают решить задачи по математике, алгоритмам, а также брейнтизеры — головоломки на общую сообразительность. Некоторые задачи стандартные, из школьных и вузов‑ ских учебников, но часто на собеседованиях предлагают нестандартные задачи. Такие, которые не встречались ни в школе, ни в вузе (и даже ни в баре и ни на дискотеке). Например, такого характера (3):

Мы разберём несколько красивых комбинаторных задач, которые решаются элементарно – стоит перевести их условие на матричный язык. А как решать без матриц – непонятно. Вообще, теория матриц имеет огромную сферу применения в том числе в комбинаторике, теории графов.

Задача 1 (ШАД). В ШАД поступили всего студентов. Кураторы решили ограничить число доступных курсов и придумали набор простых правил:

Авторы делятся своими воспоминаниями о поступлении и учебе на механико ‑математическом факультете МГУ. На всякий случай: Ильичев Виталий — окончил кафедру «Математической логики и теории алгоритмов», доктор технических наук, Южный Научный Центр РАН; Маринин Андрей — окончил кафедру «Дифференциальных уравнений», преподаватель Нижегородского госуниверситета.

Эти реальные события произошли много лет тому назад, кажется, в 1967 году. В этот раз на первом экзамене — по письменной математике — предлагались четыре задачи. С точки зрения психологии не совсем ясно какой стратегии на данном экзамене лучше придерживаться. Так, первая «параллельная» стратегия заключается в беглом просмотре всех задач, чтобы примерно оценить их трудность, а затем уже приступить к аккуратному изложению решений. Хорошо, если быстро удается убедиться, что все задачи «вполне решаемы». Это вдохновляет, и позволяет быстро оформить работу. Разумеется, это рискованная стратегия, поскольку можно потратить много времени на поиске решения одной из трудных задач. И тогда не хватит времени на аккуратное оформление остальных. Вторая стратегия — последовательное решении предлагаемых задач. Если решить какую‑то задачу сразу не получается, то переходим к следующей.

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

Определяющими факторами для любого человека являются:

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

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

Одна из увлекательных тем кружковой и олимпиадной математики - "переаттестация мудрецов". Эта серия головоломок, которые начинаются примерно с таких слов:

В некотором царстве король устроил своим придворным мудрецам переаттестацию. Он объявил им правила испытания и дал сутки на обдумывание решения. Сегодня вы - мудрецы. Докажите королю свою профпригодность!

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

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

Задача 0. На каждого из двух мудрецов надевают колпак одного из двух цветов: белый или чёрный (возможны 4 варианта). Каждый мудрец видит колпак товарища, но не видит свой. Король спрашивает любого мудреца, какой на нём колпак, и тот выкрикивает один из цветов: белый или чёрный (второй мудрец это слышит). Затем король обращается с тем же вопросом к другому мудрецу, и тот пытается отгадать свой цвет. Испытание пройдено, если максимум один мудрец ошибся. Как мудрецам заранее, до испытания, договориться, чтобы гарантированно один из них угадал свой цвет?

О функциях

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

Рассмотрим на этом интервале степенные функции , где . Каждая из этих функций возрастает, её график соединяет точки и . На интервале выполняется неравенство , каждый следующий график лежит ниже предыдущего (рис.1).

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

Таким образом можно разложить любое натуральное число. Однако встаёт вопрос о единственности. Что, если раскладывать на множители по-другому? Например,

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

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

Большинство нижних оценок имеют вид , где традиционно длина входа. Увы, наука чаще всего умеет доказывать только простые вещи в духе «для решения задачи необходимо считать весь вход». Даже для сортировок не ограниченных только доступом к сравнениям нижняя оценка остаётся открытым вопросом (при дополнительных ограничениях на вход за линейное время работает, например, Counting Sort). Чаще всего во вводных курсах по алгоритмам и книжках можно встретить нижние оценки для задач на взвешивание: поиск максимума за сравнение, одновременный поиск максимума и минимума за сравнений, и ещё несколько подобных задач. За исключением нескольких простых хорошо известных примеров, задачи на нижние оценки часто оказываются либо сложными, либо требуют знакомство со специальной (математической) техникой, нужной для их решения. Какого же было моё удивление, когда я встретил среди задач, используемых на вступительных испытаниях в Школу анализа данных Яндекса задачу на нижние оценки, которую можно решить достаточно простым способом!

Посмотрите на серию фигур из точек:

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

Вопрос: сколько всего точек на первых n гексах?

Сосчитаем ответ при малых : на первых двух гексах точек, на третьем -, поэтому на первых трёх - . Заметим, что и . Хм... Просто совпадение? Посмотрим, сколько точек на 4-м гексе. На его внешнем слое будет точек. Плюс внутри него расположен третий гекс из 19 точек. Итого, точек. Значит, всего на первых четырёх гексах точки. А - закономерность подтверждается. Правда ли, что на первых гексах всегда точек? Выведем это несколькими методами.

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

Для большинства наук и приложений, в машинном обучении, computer science прежде всего нужна, конечно, линейная алгебра. Для её успешного освоения нужно уверенно владеть элементарной алгеброй. На школьном уровне она (не)проста и скучна. Но при переходе в университет алгебра резко становится абстрактной и потому для многих сложной и непонятной: больно много аксиоматических определений — примеры еле поспевают. Как исторически произошёл этот скачок? Что нужно/полезно всем, изучающим математику, из высшей алгебры? Как лучше освоить азы линейной алгебры с прицелом на приложения, machine learning, не упустив что-то важное, но и не перетрудившись зря? Эти вопросы мы обсудим в статье.

Как найти площадь произвольного многоугольника с вершинами в узлах клетчатой бумаги?

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

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

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

Факториал натурального числа определяется так: . Например,- число со 157 цифрами. Формула, о которой пойдёт речь далее, используется для оценки факториала при больших .

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