Занятия проходили онлайн, обычно по понедельникам с 18.00 до 20.00. Форма занятий: решение задач, их обсуждение.
|
1 |
Жадный и естественный алгоритм |
6 октября 2014 г. |
Когда цель – максимум какой-то величины, ее часто достигают с помощью жадного алгоритма, то есть, добиваясь максимально возможного приращения на каждом шаге. |
||
|
2 |
Конечное и бесконечное |
13 октября |
Складывая само с собой любое положительное число (даже очень малое), можно превзойти любое число (даже очень большое). Следует различать «сколь угодно большое» и «бесконечное». Если бесконечную кучу разделить на конечное число частей, хотя бы одна из частей должна быть бесконечной. Если покрыто целое, то должна быть покрыта его любая часть. |
||
|
3 |
Изоморфизм |
20 октября |
|
Задача, переведенная на другой язык, может оказаться гораздо легче. Не забудьте только перевести решение обратно! Переводят обычно на знакомый язык, где начинает работать интуиция. |
|
|
4a |
Счастливые билеты |
27 октября |
|
Подсчет числа счастливых билетов хорошо демонстрирует многообразие приемов комбинаторики |
|
|
4b |
Соответствие. Включение-исключение. |
27 октября |
|
Сколько элементов во множестве можно найти, установив его соответствие с другим множеством, которое пересчитать легче. Если для каждого набора свойств известно число объектов с таким набором, то по формуле включения можно найти, сколько объектов удовлетворяют хотя бы одному из свойств. |
|
|
5 |
Бесконечные алгоритмы |
11 ноября |
|
Последовательная проверка пронумерованных гипотез, "подача под удобную руку", диагональный метод Кантора. |
|
|
6 |
Делимость и остатки |
17 ноября |
|
Подсчет разных остатков и разных пар остатков. Теоремы Ферма, Вильсона, китайская об остатках. |
|
|
7 |
Функция Эйлера и показатели |
24 ноября |
|
Остатки, взаимно простые с n, можно умножать, возводить в степень и делить. В некоторой степени каждый из них сравним с 1. Это дает делимость показателей степени. |
|
|
8 |
Остатки и коэффициенты |
1 декабря |
|
Остатки по простому модулю можно делить друг на друга. Многочлены с коэффициентами из таких остатков похожи на обычные, и помогают разбираться с делимостью биномиальных коэффициентов, сумм и произведений. |
|
|
9 |
Многочлены: целые значения и коэффициенты |
15 декабря |
|
Делимость разности значений на разность аргументов. Целые и рациональные корни. Критерий Эйзенштейна. |
|
|
10 |
Комплексные числа и корни |
25 декабря |
|
Комплесные числа, корни из единицы. Основная теорема алгебры. Разложение на множители многочленов с действительными коэффициентами. |
|
|
11 |
Многочлены деления круга |
29 декабря |
|
Комплексные корни из 1 являются корнями многочлена xn–1 и помогают разложить его на множители с целыми коэффициентами. Они часто возникают в связи с делимостью (функция Эйлера) и векторами в правильном многоугольнике. |
|
|
12 |
Единственность разложения многочленов |
19 января |
|
Единственность разложения многочленов с комплексными, действительными и рациональными коэффициентами. Доказательство Гаусса о связи разложения многочленов с целыми и рациональными коэффициентами. |
|
|
13 |
Числа и поля |
27 января |
|
Доказываем, что иррациональности некоторого вида замкнуты относительно четырех арифметических действий и однозначно представляются в указанном виде. С помощью линейного представления НОД многочленов избавляемся от иррациональностей в знаменателе. |
|
|
14 |
Теорема Виета |
5 февраля |
|
Теорема Виета вводит в представление симметрических выражений от двух переменных через сумму и произведение этих переменных. Это позволяет использовать симметрию выражений при решении уравнений и систем, а также использовать вместе с иирациональностью сопряженную иррациональность. |
|
|
15 |
Симметрические многочлены |
9 февраля |
|
Обобщенная терема Виета показывает, что коэффициенты многочлена любой степени симметрически зависят от корней этого многочлена. Это - элементарные симметрические многочлены, а любой другой симметрический многочлен через них выражается. Это позволяет получить массу нетривиальных следствий. |
|
|
16 |
Посредники в неравенствах |
16 февраля |
|
Неравенство A>B иногда можно разбить на два более легких для доказательства: A>P и P>B. Искусство состоит в выборе правильного посредника P. С помощью посредника доказывается транснеравенство, неравенство Мюрхеда, работает метод Штурма. |
|
|
17 |
Точки и сыр |
23 февраля |
|
В некоторых задачах возникают комбинации из конечного числа объектов, но сами объекты выбираются из бесконечного набора, заданного непрерывным параметром или параметрами. Назовем это непрерывной комбинаторикой. Хорошей моделью в таких задачах служат наборы точек на прямой и окружности. |
|
|
18 |
Непрерывная комбинаторика: комбинации и оценки |
2 марта |
|
В непрерывной комбинаторике помогает упорядочение объектов и рассмотрение крайних случаев. |
|
|
19 |
Первообразные корни и квадратичные вычеты |
9 марта |
|
Все ненулевые остатки по простому модулю можно представить как степени одного остатка. Нечетные делители сумм квадратов сравнимы с 1 по по модулю 4. |
|
|
20 |
Группа подстановок |
16 марта |
|
Разложение подстановок в циклы, в композицию транспозиций, чётность перестановок и подстановок. |
|
|
21 |
Группы преобразований |
23 марта |
|
Идея обратимости реализуется через группы: множества преобразований, замкнутых относительно композиций и взятия обратного. Это объединяет подстановки, движения плоскости и теорию чисел. Порядок конечной группы делится на длину орбиты, порядок подгруппы и порядок элемента. |
|
|
22 |
Свяжитесь с графом |
4 апреля |
|
Граф – не только точки, связанные отрезками: он есть везде, где выделены пары объектов, в частности, где есть позиции и ходы. Есть различные равенства и неравенства для числа вершин, рёбер и компонент связности. Это может дать неожиданные оценки. |
|
|
23 |
Линейные системы. Рациональный трюк. |
20 апреля |
|
Про линейную систему можно много узнать, не решая её (например, число решений). Итог взвешиваний тоже можно выразить, как линейную систему. Решение системы с целыми коэффициентами можно подменить рациональным решением. |
|
|
24 |
Комбинатороная геометрия: Покрытия |
14 мая |
|
Кроме геометрических теорем, в комбигеометрии работает принцип узких мест и соответствие. В задачах на покрытие широко применяются оценки; часто работает идея посредника. |