算法设计与分析
分享
课程详情
课程评价
spContent=算法设计与分析是北京大学信息科学技术学院屈婉玲教授为主讲授的算法设计与分析系列MOOC课程之基础篇。中国计算机学会(CCF)授予她2017“CCF夏培肃奖”,表彰她在算法等课程的建设与教学中所作出的杰出贡献,本课程由北大算法设计与分析教学团队的汪小林、蒋婷婷、罗国杰等教师辅助屈婉玲教授开设。
—— 课程团队
课程概述

算法设计与分析是计算机专业的核心课程。学习该课程对学习其他专业课奠定了扎实的基础,也对培养计算思维和求解问题的能力起到重要作用。面对各个应用领域的大量实际问题,最重要的是分析问题的性质并选择正确的求解思路,即找到一个好的算法。特别是在当今复杂、海量信息的大数据处理中,一个好的算法往往起到决定性的作用。
    本课程注重针对实际问题需求,进行数学建模并选择高效求解算法的训练,为提高学生的素质和创新能力打下必要的基础。课程主要内容涉及:面对实际问题建立数学模型、设计正确的求解算法、算法的效率估计、改进算法的途径、问题计算复杂度的估计、难解问题的确定和应对策略等等。本课程是算法课程的基础部分,主要涉及算法的设计、分析与改进途径,其他有关计算复杂性的内容将在后续课程"算法设计与分析(高级)"中加以介绍。

    课程的内容分成两大部分:算法的基础知识和通用算法设计技术与分析方法。

    算法基础知识部分主要介绍算法相关的基本概念和数学基础。比如,什么是算法的伪码描述?什么是算法最坏情况下和平均情况下的时间复杂度?算法时间复杂度函数的主要性质,算法复杂度估计中常用的数学方法,如序列求和及递推方程求解。

    通用算法设计技术与分析方法部分主要介绍分治策略、动态规划、贪心法、回溯与分支限界等算法设计技术。重点介绍这些设计技术的使用条件、分析方法、改进途径,并给出一些重要的应用。

授课目标

本课程从算法复杂性分析的基本方法和原理入手,以讲授算法设计的基本方法和原理、算法优化的基本方法和技巧为主,通过典型的问题及其相应的求解算法,以及算法复杂性的分析,达到完善学生的知识体系、培养学生的分析能力、拓展学生的思维方法,并鼓励学生把理论与实践相结合。

课程大纲

第一周 基础知识(1):算法的基本概念及伪码描述,函数的渐近的界 (2课时)

  1.1 本周教学内容简介

  1.2 算法设计的两个例子

  1.3 问题的计算复杂度:排序问题

  1.4 货郎问题与计算复杂性

  1.5 算法及其时间复杂度

  1.6 算法的伪码表示

  1.7 函数的渐近的界

  1.8 有关函数渐近的界的定理

  1.9 几类重要函数

第二周 基础知识(2):序列求和方法,递推方程求解 (2课时)

  2.1 本周教学内容简介

  2.2 序列求和的方法

  2.3 递推方程与算法分析

  2.4 迭代法求解递推方程

  2.5 差消法化简递推方程

  2.6 递归树

  2.7 主定理及其证明

  2.8 主定理的应用

第三周 分治策略(1)(2课时)

  3.1 本周教学内容简介

  3.2 分治策略的设计思想

  3.3 分治策略的一般描述和分析方法

  3.4 芯片测试

  3.5 快速排序

  3.6 幂乘算法及应用

  3.7 改进分治算法的途径1:减少子问题数

  3.8 改进分治算法的途径2:增加预处理

第四周 分治策略(2)(2课时)

  4.1 本周内容简介

  4.2 选最大与最小

  4.3 选第二大

  4.4 一般选择问题的算法设计

  4.5.选择问题的算法分析

  4.6 卷积及应用

  4.7 卷积计算

  4.8 快速傅立叶变换FFT算法

  4.9 平面点集的凸包

......

预备知识

程序设计基础、数据结构与算法、高等数学、高等代数

证书要求

60分以上颁发合格证书

85分以上颁发优秀证书

参考资料

《算法设计与分析(第2版)》  屈婉玲、刘田、张立昂、王捍贫编著 清华大学出版社