算法设计与分析   Design and Analysis of Algorithms

算法设计与分析 Design and Analysis of Algorithms

课程
zh
中文
44 时
此内容评级为 0/5
来源
  • 来自www.coursera.org
状况
  • 自定进度
  • 免费获取
  • 收费证书
更多信息
  • 11 序列
  • 等级 中级

Their employees are learning daily with Edflex

  • Safran
  • Air France
  • TotalEnergies
  • Generali
Learn more

课程详情

教学大纲

  • Week 1 - 算法基础
    先通过几个典型的例子阐述算法设计与分析课程的学习内容及重要意义,接着介绍与算法有关的基本概念,如算法的伪码描述、时间复杂度函数的表示方法和一些常用的时间复杂度函数。
  • Week 2 - 序列求和与递推方程
    介绍在算法分析中所需要的一些数学基础知识,如与程序迭代有关的序列求和公式,在估计递归计算工作量时常用的递推方程及其求解方法等。
  • Week 3 - 分治算法的设计与分析
    分而治之是一种常用的算法设计技术。主要思想是将原始问题分解成若干个规模较小的独立的子问题,接着分别求解每个子问题,最后再将子问题的解综合以得到原始问题的解。通过本周的学习,你将了解分治算法的使用条件、主要的设计步骤、递归的实现技术、时间复杂度的分析方法、提高算法效率的途径等重要问题。
  • Week 4 - 分治算法的典型应用
    在对分治算法有了基本的认识以后,进一步介绍一些典型的分治算法的成功案例,包括各种选择算法、涉及信号降噪处理的卷积计算与快速傅立叶变换、涉及图形学的平面点集凸包的计算等。
  • Week 5 - 动态规划算法
    动态规划是另一种常用的算法设计技术。首先通过矩阵相乘的例子介绍动态规划算法的设计思想、主要步骤、分析方法、迭代实现与存储表示等。然后通过投资、背包、最长公共子序列等典型问题展现不同的动态规划算法在子问题划分与迭代计算时的特点和提高算法效率的技巧。
  • Week 6 - 动态规划算法的典型应用
    在对动态规划算法有了基本认识之后,进一步介绍运用动态规划算法的一些成功案例,如用于黑白图片存储的变位压缩算法、最大子段和的计算、最优二分检索树的构造以及生物信息学中的RNA二级结构预测和序列比对算法等。
  • Week 7 - 贪心法的设计
    贪心法是处理组合优化问题的常用算法。通过几个典型例子说明了贪心法的设计思想,同时重点阐述了贪心策略正确性的证明方法。针对某些不能保证对所有的输入都得到最优解的贪心策略讨论了其适用范围。
  • Week 8 - 贪心算法的典型应用
    给出了贪心法应用的一些成功案例,如与最优前缀码设计有关的哈夫曼算法、应用广泛的最小生成树Prim算法和Kruskal算法、在网络路由中寻找单源最短路径的Dijkstra算法等。
  • Week 9 - 回溯算法的设计思想
    回溯算法是一种基本的搜索技术,通过n后放置、0-1背包、货郎旅行、图的着色等问题介绍了回溯算法的设计思想、适用条件和实现方法,并给出了估计算法运行时间的一种抽样方法。
  • Week 10 - 回溯算法的典型应用
    介绍提升回溯算法搜索效率的分支限界技术,给出求解最大团、货郎、圆排列、邮票设计等回溯算法的典型应用实例。
  • Week 11 - 期末考试
     

先决条件

没有。

讲师

Wanling Qu
Professor
School of EECS, Peking University

编辑

北京大学致力于向中国和世界各地的学生开放教育。北京大学拥有 3000 多名教职员工,教学质量卓越。北京大学成立于 1898 年,是中国第一所国立综合性大学。

115 年来,北京大学拥有数十万杰出校友,在人文和科学领域为促进中国的繁荣与进步做出了突出贡献。

平台

Coursera是一家数字公司,提供由位于加利福尼亚州山景城的计算机教师Andrew Ng和达芙妮科勒斯坦福大学创建的大型开放式在线课程。

Coursera与顶尖大学和组织合作,在线提供一些课程,并提供许多科目的课程,包括:物理,工程,人文,医学,生物学,社会科学,数学,商业,计算机科学,数字营销,数据科学 和其他科目。

此内容评级为 4.5/5
(没有评论)

您覺得這門課如何?

完成这个资源,写一篇评论