1. Логика и софизмы.

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

2. Оценка плюс пример.

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

3. Геометрия и алгебра помогают друг другу.

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

4. Кратчайший путь.

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

5. Математическая индукция.

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

6. Комбинаторика и вероятность.

Как избегать ошибок при подсчётах в комбинаторных и вероятностных задачах: не считать объекты несколько раз, отличать упорядоченные выборки от неупорядоченных. Как устанавливать взаимно-однозначные соответствия и видеть аналогии, облегчающие подсчёт. Обсудим также интересные вероятностные парадоксы, связанные с выбором вероятностного пространства.

7. Графы.

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

8. Переаттестация мудрецов.

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

9. Игры и стратегии.

В математической игре, как правило, конечное число исходов, что по идее должно снимать интригу „Кто победит?“ У одного из игроков обычно имеется выигрышная стратегия. В простых задачах она несложная и основана на симметричных (в каком либо смысле) ответных действиях. Но более трудные игры нужно анализировать с конца, приходя в конце к алгоритму для одного из соперников.

10. Раскраски помогают.

Ряд трудных задач сразу решаются с помощью удачно подобранной раскраски клетчатой доски (например, шахматной или куда более хитрой) или расстановки чисел. Но как до них догадаться? И что общего у таких приёмов с переходом к остаткам при работе с целыми числами? Что обо всём этом думает высшая математика? Мы покажем вам „магию раскрасок“ и пригласим „за кулисы“.

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

1. Жадные алгоритмы (задачи на поддержание инварианта) как задачи на индукцию

2. Комбинаторные игры и динамическое программирование

3. Сортировки и нижние оценки (задачи на взвешивания и их приложения к алгоритмам)

4. Некоторые алгоритмические задачи на графы