Корнеев Сергей Александрович
«Комбинаторика и смежные вопросы сложности вычислений»
Описание курса:
Комбинаторные задачи естественным образом возникают в различных областях математики, например, когда необходимо подсчитать количество каких-либо объектов. Однако комбинаторике не всегда уделяется достаточно внимания. Даже задачи типа «В магазине продаётся 4 типа шоколадок. Сколько различных наборов из 8 шоколадок можно купить?» могут вызывать у студентов трудности. В спецкурсе рассказывается о методах решения различных комбинаторных задач. Основные темы: бином Ньютона и полиномиальная формула, треугольник Паскаля, рекуррентные уравнения, числа Фибоначчи и числа Каталана, основы теории графов. В заключительной части спецкурса планируется рассказать об оценках сложности вычисления биномиальных коэффициентов, которые являются одним из основных объектов комбинаторики. На данный момент комбинаторика является чрезвычайно содержательной и быстроразвивающейся областью математики. Стоит отметить, что в этой области есть много интересных открытых задач - например, гипотеза Сингмастера, гипотеза Адамара, задачи о количестве графов разных типов, задачи о числах Рамсея.
План курса:
Лекция 1
Биномиальные коэффициенты. Бином Ньютона. Формулы с биномиальными коэффициентами.
Лекция 2
Треугольник Паскаля и его свойства.
Лекция 3
Полиномиальные коэффициенты. Полиномиальная формула.
Лекция 4
Различные типы комбинаторных задач и методы их решения.
Лекция 5
Однородные рекуррентные уравнения.
Лекция 6
Неоднородные рекуррентные уравнения.
Лекция 7
Примеры задач, решаемых с помощью рекуррентных уравнений. Числа Фибоначчи.
Лекция 8
Числа Каталана. Примеры задач, в которых они возникают.
Лекция 9
Основные понятия теории графов. Маршруты, цепи, циклы. Связность. Ориентированные и неориентированные графы.
Лекция 10
Способы задания графов: матрица смежности, матрица инцидентности, список смежности, список рёбер.
Лекция 11
Деревья. Характеристические свойства деревьев. Остовные деревья. Код Прюфера. Теорема Кэли.
Лекция 12
Сложность арифметических вычислений. Свойства делимости биномиальных коэффициентов.
Лекция 13
Формула Лежандра. Теорема Куммера. Верхняя оценка суммы логарифмов биномиальных коэффициентов.
Лекция 14
Оценки сложности вычисления биномиальных коэффициентов.
