Основы комбинаторики

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

Для бесплатного просмотра доступны только видеолекции и тренировочные задания. Тесты на проверку откроются после оплаты сертификации. Стоимость сертификации составляет 2800 рублей.

Экзамус.

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

Ближайшие даты экзамена с 22 по 31 мая 2023 года.

 

Курс состоит из 11 недель лекций и 1 недели экзамена. Каждую неделю слушатель выполняет задания (тесты и задачи с ответом). Экзамен также состоит из теста и задач с ответом. Для успешного прохождения курса необходимо в каждом задании набрать не менее 50% от общего числа баллов.

1. Н.Я. Виленкин. Комбинаторика. – М.: Наука, 1969.
2. Н.Б. Алфутова, А.В. Устинов. Алгебра и теория чисел (сборник задач). – М.: МЦНМО, 2002.
3. М. Холл. Комбинаторика. – М.: Мир, 1970.
4. М.Айгнер Комбинаторная теория. - М.: Мир, 1982
5. А.М. Райгородский Комбинаторика и теория вероятностей. - МФТИ, 2012 - 109 c.
6. Г. Эндрюс Теория разбиений, М.: Наука, 1982
7. Д. Кнут, Р. Грэхем, О. Паташник. Конкретная математика. Математические основы информатики. М.: Мир, 1998

Для участия в курсе слушателю необходимо иметь базовые представления о теории множеств и началах анализа. Все остальные понятия будут введены в ходе курса.

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

Базовые знания:

1. основные правила и принципы комбинаторики,
2. основные комбинаторные величины и тождества с ними,
3. основы теории обращения Мёбиуса,
4. основы теории разбиений,
5. основы метода производящих функций, линейных рекуррентных соотношений и их решений.

Умения:

1. решать простейшие комбинаторные задачи,
2. доказывать тождества,
3. упрощать выражения, содержащие биномиальные коэффициенты,
4. вычислять количества упорядоченных и неупорядоченных разбиений,
5. находить формулы для линейных рекуррентных соотношений,
6. вычислять производящие функции

05.00.00 Науки о земле
07.00.00 Архитектура
08.00.00 Техника и технологии строительства
09.00.00 Информатика и вычислительная техника
10.00.00 Информационная безопасность
11.00.00 Электроника, радиотехника и системы связи
12.00.00 Фотоника, приборостроение, оптические и биотехнические системы и технологии
13.00.00 Электро- и теплоэнергетика
14.00.00 Ядерная энергетика и технологии
15.00.00 Машиностроение
16.00.00 Физико-технические науки и технологии
17.00.00 Оружие и системы вооружения
18.00.00 Химические технологии
19.00.00 Промышленная экология и биотехнологии
20.00.00 Техносферная безопасность и природообустройство
21.00.00 Прикладная геология, горное дело, нефтегазовое дело и геодезия
22.00.00 Технологии материалов
23.00.00 Техника и технологии наземного транспорта
24.00.00 Авиационная и ракетно-космическая техника
25.00.00 Аэронавигация и эксплуатация авиационной и ракетно-космической техники
26.00.00 Техника и технологии кораблестроения и водного транспорта
27.00.00 Управление в технических системах
28.00.00 Нанотехнологии и наноматериалы
29.00.00 Технологии легкой промышленности