|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/analytic-combinatorics
课程评论：没有评论
课程名称：解析组合学 概述：解析组合学教授一种能够精确定量预测大型组合结构的数学工具。该课程介绍了符号方法，以推导普通、指数和多元生成函数之间的功能关系，以及利用复分析方法从生成函数方程中得出准确的渐近结果。 课程特点：此课程的所有内容均可免费获取，但完成后不提供证书。 课程大纲： 1. **组合结构与普通生成函数**：讲解符号方法，定义组合对象类的组合构造，结合传递定理推导生成函数定义的方程，并探讨经典组合学的多个例子。 2. **带标签的结构与指数生成函数**：介绍带标签的对象，使用可区分的原子构建组合对象，通过指数生成函数研究由带标签对象构建的组合类，并定义与之相关的EGF方程。 3. **组合参数与多元生成函数**：讲述添加变量标记参数的过程，并利用前两讲中的构造和传递定理的自然扩展定义含参数信息的多元生成函数，重点研究双变量生成函数。 4. **复分析、理性与亚解析渐近**：将生成函数视为分析对象，引入系数的渐近估计，探索复分析的基本概念，适合没有复分析基础的学生。 5. **理性与亚解析渐近的应用**：应用前一讲的传递定理，研究我们在前两讲中遇到的经典组合类的应用，探讨适用于广泛组合类的普遍法则。 6. **奇点分析**：讲解Flajolet-Odlyzko定理，找出函数在主导奇点附近的解析领域，并通过标准尺度函数进行近似，逐项转移到系数渐近。 7. **奇点分析的应用**：展示Flajolet-Odlyzko方法如何应用于由集合、多重集和递归序列构造的组合类，并探讨经典组合类的应用。 8. **鞍点渐近**：研究鞍点法，这是一种轮廓积分的通用技术，为无奇点生成函数的系数渐近提供有效途径，并应用于经典问题。
Name:Combinatorial Structures and OGFs
Description: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.
Name:Labelled Structures and EGFs
Description: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.
Name:Combinatorial Parameters and MGFs
Description: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.
Name:Complex Analysis, Rational and Meromorphic Asymptotics
Description: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.
Name:Applications of Rational and Meromorphic Asymptotics
Description: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.
Name:Singularity Analysis
Description: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.
Name:Applications of Singularity Analysis
Description: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.
Name:Saddle Point Asymptotics
Description: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.
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.
