算法分析

课程概况

本课程是普林斯顿大学的慕课，目标是精确定量预测大型组合结构的性质。此外，这门课还在算法分析应用和基本结构（例如排列、树、字符串、字、映射）的语境下，涵盖了生成函数、实渐近、符号法等内容。

算法分析课程的目标是精确定量预测大型组合结构的性质。相关理论在最近数十年间变得至关重要，无论是对计算机科学中的科学算法分析，还是对其它学科中科学模型的研究，包括概率论、统计物理、计算生物学和信息理论等学科。这门课在算法分析应用的语境中，涵盖了递归关系、生成函数、渐近和基本结构（例如排列、树、字符串、字、映射）。

This course teaches a calculus that enables precise quantitative predictions of large combinatorial structures. In addition, this course covers generating functions and real asymptotics and then introduces the symbolic method in the context of applications in the analysis of algorithms and basic structures such as permutations, trees, strings, words, and mappings.

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

课程大纲

第一讲：算法分析
We begin by considering historical context and motivation for the scientific study of algorithm performance. Then we consider a classic example that illustrates the key ingredients of the process: the analysis of Quicksort. The lecture concludes with a discussion of some resources that you might find useful during this course.

第二讲：递归
We begin this lecture with an overview of recurrence relations, which provides us with a direct mathematical model for the analysis of algorithms. We finish by examining the fascinating oscillatory behavior of the divide-and-conquer recurrence corresponding to the mergesort algorithm and the general "master theorem" for related recurrences.

第三讲：使用GF求解递归
Since the 17th century, scientists have been using generating functions to solve recurrences, so we continue with an overview of generating functions, emphasizing their utility in solving problems like counting the number of binary trees with N nodes.

第四讲：渐近
Exact answers are often cumbersome, so we next consider a scientific approach to developing approximate answers that, again, mathematicians and scientists have used for centuries.

第五讲：符号法
Analytic Combinatorics. With a basic knowledge of recurrences, generating functions, and asymptotics, you are ready to learn and appreciate the basic features of analytic combinatorics, a systematic approach that avoids much of the detail of the classical methods that we have been considering. We introduce unlabeled and labelled combinatorial classes and motivate our basic approach to studying them, with numerous examples.

第六讲：树
The quintessential recursive structure, trees of various sorts are ubiquitous in scientific enquiry, and they arise explicitly in countless computing applications. You can find broad coverage in the textbook, but the lecture focuses on the use of analytic combinatorics to enumerate various types of trees and study parameters.

第七讲：排列
The study of sorting algorithms is the study of properties of permutations. We introduce analytic-combinatoric approaches to studying permutations in the context of this relationship.

第八讲：字符串和trie树
From DNA sequences to web indices, strings (sequences of characters) are ubiquitous in modern computing applications, so we use analytic combinatorics to study their basic properties and then introduce the trie, an essential and fundamental structure not found in classical combinatorics.

第九讲：字和映射
We view strings as sets of characters or as functions from [1..N] to [1..M] to study classical occupancy problems and their application to fundamental hashing algorithms. Functions from [1..N] to [1..N] are mappings, which have an interesting and intricate structure that we can study with analytic combinatorics.

预备知识

这门课要求知道微积分的数学知识和对Java这类现代编程语言的熟悉。算法第一部分所讲授的基本算法和数据结构知识对这门课会有帮助，但不是必需的。视频从算法分析到解析组合学：菲利普·弗拉乔利特带你领略是选看内容（因为它包含一些进阶内容，超出了本课程的范围），该视频概述了一些历史，对这门课和解析组合学进行了介绍。