解析组合数学

Analytic Combinatorics

这门课将教会大家精确定量预测大型组合结构的性质,介绍符号法,用以推导普通、指数和多元生成函数之间的函数关系;还将介绍复分析中的方法,用于从GF方程推导准确渐近性。

普林斯顿大学

Coursera

数学与统计

普通(中级)

20 小时

  • 英语
  • 1459

课程概况

解析组合学这门课将教会大家精确定量预测大型组合结构的性质。这门课将介绍符号法,用以推导普通、指数和多元生成函数之间的函数关系;这门课还将介绍复分析中的方法,用于从GF方程推导准确渐近性。

解析组合学基于推导生成函数关系的形式方法和将这些函数处理为复平面内函数的渐进分析。这门课涵盖了立刻从组合结构中定义生成函数符号法,然后发展出方法,直接从这些生成函数中推导渐近结果,过程中会用到复渐近、奇异分析、鞍点渐近、和极限定律。课程将教你如下概念:“只要你能具体说明它,你就能够分析它。”

Analytic Combinatorics teaches a calculus that enables precise quantitative predictions of large combinatorial structures. This course introduces the symbolic method to derive functional relations among ordinary, exponential, and multivariate generating functions, and methods in complex analysis for deriving accurate asymptotics from the GF equations.

All the features of this course are available for free. It does not offer a certificate upon completion.

课程大纲

第一讲:组合结构和OGF
Our first lecture is about the symbolic method, where we define combinatorial constructions that we can use to define classes of combinatorial objects. The constructions are integrated with transfer theorems that lead to equations that define generating functions whose coefficients enumerate the classes. We consider numerous examples from classical combinatorics.

第二讲:带标号结构和EGF
This lecture introduces labelled objects, where the atoms that we use to build objects are distinguishable. We use exponential generating functions EGFs to study combinatorial classes built from labelled objects. As in Lecture 1, we define combinatorial constructions that lead to EGF equations, and consider numerous examples from classical combinatorics.

第三讲:组合参数和MGF
This lecture describes the process of adding variables to mark parameters and then using the constructions form Lectures 1 and 2 and natural extensions of the transfer theorems to define multivariate GFs that contain information about parameters. We concentrate on bivariate generating functions (BGFs), where one variable marks the size of an object and the other marks the value of a parameter. After studying ways of computing the mean, standard deviation and other moments from BGFs, we consider several examples in some detail.

第四讲:复分析、有理和亚纯渐近
This week we introduce the idea of viewing generating functions as analytic objects, which leads us to asymptotic estimates of coefficients. The approach is most fruitful when we consider GFs as complex functions, so we introduce and apply basic concepts in complex analysis. We start from basic principles, so prior knowledge of complex analysis is not required.

第五讲:有理和亚纯渐近应用
We consider applications of the general transfer theorem of the previous lecture to many of the classic combinatorial classes that we encountered in Lectures 1 and 2. Then we consider a universal law that gives asymptotics for a broad swath of combinatorial classes built with the sequence construction.

第六讲:生成函数的奇异分析
This lecture addresses the basic Flajolet-Odlyzko theorem, where we find the domain of analyticity of the function near its dominant singularity,
approximate using functions from standard scale, and then transfer to coefficient asymptotics term-by-term.

第七讲:奇异分析的应用
We see how the Flajolet-Odlyzko approach leads to universal laws covering combinatorial classes built with the set, multiset, and recursive
sequence constructions. Then we consider applications to many of the classic combinatorial classes that we encountered in Lectures 1 and 2.

第八讲:鞍点渐近
We consider the saddle point method, a general technique for contour integration that also provides an effective path to the development of coefficient asymptotics for GFs with no singularities. As usual, we consider the application of this method to several of the classic problems introduced in Lectures 1 and 2.

预备知识

熟悉算法分析中讲授的递归、生成函数、渐近和基本组合学内容。熟悉Java这类现代编程语言。 算法,第一部分所讲授的基本算法和数据结构知识对这门课会有帮助,但不是必需的。视频从算法分析到解析组合学:菲利普·弗拉乔利特带你领略是选看内容,该视频概述了一些历史,回答了“解析组合学是什么”这一问题。

参考资料

这门课基于教材《解析组合学》,塞奇威克和弗拉乔利特著。教材和课程相关免费网络内容可以访问http://ac.cs.princeton.edu/home/

声明: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
  • 以及更多...

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