现代组合学

Современная комбинаторика (Modern combinatorics)

427 次查看
莫斯科物理科学与技术学院
Coursera
  • 完成时间大约为 44 个小时
  • 混合难度
  • 俄语
注:本课程由Coursera和Linkshare共同提供,因开课平台的各种因素变化,以上开课日期仅供参考

课程概况

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

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

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

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

Данный курс рекомендуется к прохождению перед курсом Теория вероятностей.

课程大纲

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

Основные принципы комбинаторики. Правило сложения. Правило умножения. Принцип Дирихле. Пример применения принципа Дирихле. Теорема о раскраске множества в два цвета. Мощности множества попарно неортогональных {-1,0,1}-векторов : верхняя и нижняя оценки. Числа сочетаний, размещений и перестановок.

Комбинаторные тождества

Бином Ньютона. Полиномиальная формула. Формула включений и исключений. Простейшие тождества. Треугольник Паскаля. Сумма биномиальных и полиномиальных коэффициентов. Сумма квадратов биномиальных коффициентов. Формулы для суммы степеней натуральных чисел. Знакопеременное тождество.

Формула обращения Мёбиуса

Формула для количества ‘слов’. Определение циклической последовательности. Формулировка проблемы. Простое число. Бесконечность простых. Основная теорема арифметики. Функция Мебиуса. Суммы по делителям. Формула обращения Мебиуса.

Циклические последовательности

Вывод формулы для количества циклических последовательностей. Частично упорядоченное множество. Обобщенная функция Мебиуса. Связь с обычной функцией Мебиуса. Теорема об формуле обращения Мебиуса на ч.у.м. Передоказательство формулы включений и исключений (часть 1) (*).

Разбиения

Разбиения чисел на слагемые. Упорядоченные и неупорядоченные разбиения. Формула для числа упорядоченных разбиений. Рекуррентное соотношение для числа неупорядоченных разбиений. Формула Харди-Рамануджана. Диаграмма Юнга. Теоремы Эйлера о равенстве количеств неупорядоченных разбиений. Передоказательство формулы включений и исключений (часть 2) (*).

Линейные рекуррентные соотношения. Формальные степенные ряды.

Линейные рекуррентные соотношения. Числа Фибоначчи. Теорема о решении линейного рекуррентного соотношения второго порядка. Формальные степенные ряды. Операции над рядами. Пример “деления в столбик”.

Производящие функции

Производящие функции. Теорема о сходимости степенных рядов (б/д). Примеры, иллюстрирующие теоремы. Сходимость на границе интервала. Числа Фибоначчи и их производящая функция. Суммы чисел Фибоначчи, чисел сочетания и пр. Числа Каталана. Извлечение корней из степенных рядов. Формула для числа Каталана: д-во через производящие функции.

Экзамен

Экзамен.

千万首歌曲。全无广告干扰。
此外,您还能在所有设备上欣赏您的整个音乐资料库。免费畅听 3 个月,之后每月只需 ¥10.00。
Apple 广告
声明:MOOC中国十分重视知识产权问题,我们发布之课程均源自下列机构,版权均归其所有,本站仅作报道收录并尊重其著作权益。感谢他们对MOOC事业做出的贡献!
  • Coursera
  • edX
  • OpenLearning
  • FutureLearn
  • iversity
  • Udacity
  • NovoEd
  • Canvas
  • Open2Study
  • Google
  • ewant
  • FUN
  • IOC-Athlete-MOOC
  • World-Science-U
  • Codecademy
  • CourseSites
  • opencourseworld
  • ShareCourse
  • gacco
  • MiriadaX
  • JANUX
  • openhpi
  • Stanford-Open-Edx
  • 网易云课堂
  • 中国大学MOOC
  • 学堂在线
  • 顶你学堂
  • 华文慕课
  • 好大学在线CnMooc
  • (部分课程由Coursera、Udemy、Linkshare共同提供)

© 2008-2020 MOOC.CN 慕课改变你,你改变世界