|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/analysis-of-algorithms
课程评论：没有评论
课程名称：算法分析 概述：本课程教授一种能够精确预测大规模组合结构的计算方法。此外，课程还涉及生成函数和实际渐近分析，并在算法分析及基本结构（如排列、树、字符串、单词和映射）的应用背景下引入符号方法。本课程的所有内容均可免费获取，完成后不提供证书。 课程大纲： 1. **算法分析的历史背景与动机**：从经典的快速排序算法分析入手，探讨算法性能的科学研究，最后讨论一些有用的资源。 2. **递归关系**：概述递归关系，为算法分析提供直接的数学模型，最后探讨归并排序算法的分治递归及相关的“主定理”。 3. **生成函数**：自17世纪以来，科学家们使用生成函数解决递归问题，本节将强调其在计数二叉树等问题中的实用性。 4. **渐近分析**：讨论科学方法以开发近似解的思路，解决详细计算常常繁琐的问题。 5. **分析组合学**：在掌握递归、生成函数与渐近分析的基础知识后，介绍分析组合学，避免经典方法的复杂细节，并通过多个实例激励对基本方法的理解。 6. **树**：作为经典的递归结构，树在科学研究中普遍存在，侧重于如何利用分析组合学对各种类型的树进行计数及研究其参数。 7. **排列**：排序算法的研究与排列特性密切相关，介绍分析组合学方法以研究排列的性质。 8. **字符串与字典树**：字符串（字符序列）在现代计算应用中的普遍性，通过分析组合学研究其基本属性，并引入字典树这一在经典组合学中未涉及的重要结构。 9. **单词与映射**：将字符串视为字符集合或从[1..N]到[1..M]的函数，以此研究经典的占用问题及其在基本哈希算法中的应用。对映射（从[1..N]到[1..N]的函数）进行深入的分析组合学研究。 本课程旨在为学习者提供算法分析领域的系统知识，帮助他们掌握相关的基本概念和技术。
Name:Analysis of Algorithms
Description: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.
Name:Recurrences
Description: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.
Name:Generating Functions
Description: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.
Name:Asymptotics
Description: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.
Name:Analytic Combinatorics
Description: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.
Name:Trees
Description: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.
Name:Permutations
Description: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.
Name:Strings and Tries
Description: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.
Name:Words and Mappings
Description: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.
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.
