up
  • Russian

    course language

  • 13 weeks

    course duration

  • 3 credit points

    for credit at your university

 

Курс входит в пакет курсов (возможность приобрести доступ к нескольким курсам по сниженной стоимости):

Дискретная математика ч.1 (комбинаторика и теория вероятностей)

 

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

About

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

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

Format

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

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

Requirements

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

Course program

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

Education results

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

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

Умения:

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

Отзывы о курсе

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

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