наверх

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

видеоролик о курсе

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

О курсе

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

Формат

Курс состоит из 10 недель лекций и 1 недели экзамена. Каждую неделю слушатель выполняет задания, составляющие 10% от всего курса (5% тест и 5% задачи с ответом). Экзамен также состоит из теста и задач с ответом, каждая часть оценивается в 15% от общей суммы. Для успешного прохождения курса необходимо в каждом задании набрать не менее 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 Технологии легкой промышленности
  • 10 недель

    длительность курса

  • 3 зачётных единицы

    для зачета в своем вузе

Райгородский Андрей Михайлович

Доктор физико-математических наук
Должность: Заведующий кафедрой Дискретной математики ФИВТ, научный руководитель бакалавриата кафедры «Анализ данных», руководитель отдела теоретических и прикладных исследований Яндекса, главный редактор журнала Moscow Journal of Combinatorics and Number Theory

сертификат об окончании курса

Сертификат

Сертификат участника обычно выдается при достижении 60% от общего рейтинга при условии сдачи работ до жесткого дедлайна. Сертификат с отличием, как правило, выдается при достижении 90% от общего рейтинга при условии сдачи работ до мягкого дедлайна.

Похожие курсы