课程简介

“算法设计与分析”是计算机科学与技术专业的一门核心课程。通过学习算法不但对学习其他专业课程奠定了扎实的基础,也对培养学生的计算思维和求解问题的能力起到重要的作用。算法与计算复杂性理论一直是计算机科学研究的热点领域。面对各个应用领域的大量实际问题,最重要的是根据问题的性质选择正确的求解思路,即找到一个好的算法。特别在复杂的、海量信息的处理中,一个好的算法往往起到决定性的作用。 算法设计与分析涉及内容较多,根据MOOC课程的教学特点和需求,我们将它分成两个部分。其中“算法设计与分析(1)”主要讲授有关算法的基础知识和通用设计技术,包括算法的基本概念和数学基础、分治策略、动态规划、贪心法、回溯和分支限界等。“算法设计与分析(2)”是在上述基础上介绍两类重要问题的建模和算法设计,并进一步讨论问题难度的界定和困难问题的应对策略。这次开课的是第二部分“算法设计与分析(2)”。选修本课程的学生应该预先修过“算法设计与分析(1)”或者具有相关的基础。“算法设计与分析(1)”已经在华文慕课平台上线,网址是:http://www.chinesemooc.org/mooc/4748/,需要了解相关教学内容的同学可以访问。

课程大纲

国家精品在线开放课程认定评审专家请关注:

由于国外平台访问课程视频有困难,评审专家可在华文慕课平台查看视频等静态内容,在Coursera和edX查看互动情况,Coursera课程链接:https://www.coursera.org/learn/algorithms,edX课程链接:https://www.edx.org/course/suan-fa-she-ji-yu-fen-xi-gao-ji-advanced-pekingx-04833050x


第一周:线性规划
介绍线性规划的例子、二维线性规划的图解法和线性规划的标准形,讨论线性规划可行解的性质,给出求解线性规划的单纯形法与单纯形表。

第二周:线性规划的对偶与应用
介绍对偶线性规划、对偶单纯形法、整数线性规划的分支限界算法,讨论线性规划的应用。

第三周:最大流问题
介绍网络流及其性质、最大流与最小割的概念,讲授Ford-Fulkeson算法和Dinic算法。

第四周:最小费用流与网络流应用
介绍最小费用流与Floyd算法、最小费用流的负回路算法与最短路径算法,讨论网络流算法的应用。

第五周:问题的计算复杂度分析
介绍有关问题计算复杂度分析的基本概念,给出决策树定义并作出检索问题的时间复杂度分析、介绍冒泡排序与堆排序。

第六周:排序及选择问题的复杂度分析
介绍堆排序算法、定义排序算法的决策树,对排序问题及选最小问题进行复杂度分析、介绍通过归约估计问题难度的下界的方法。

第七周:NP完全性理论
介绍NP完全理论的基本概念:难解问题与易解问题、判定问题、NP类与P类、多项式时间变换等,Cook-Levin定理。

第八周:几个NP完全问题
介绍可满足性问题、顶点覆盖、哈密顿回路与货郎问题、恰好覆盖、子集和、0-1背包、整数线性规划等。

第九周:近似算法
介绍近似算法的设计思想及分析方法,针对多机调度、货郎问题、0-1背包等问题讨论了近似算法的设计思想与分析方法。

第十周:随机算法
介绍随机算法的设计思想和分析方法,讨论了随机快速排序与选择算法以及n后问题、主元素测试、素数测试等随机算法。

课程说明

每周教学有6-7个视频,开始的1个短视频是本周课程内容的介绍,大约1-2分钟;剩下的5-8个视频是课程讲授,每讲涉及一个知识点,一般10-15分钟(个别知识点可能稍长一点)。每个视频都配有相应的讲义(pdf文件)以便大家阅读和复习。每周配有小测验,作为练习和检查。

参考资料

算法设计与分析(1)和(2)的教学参考书是:算法设计与分析(第2版),屈婉玲、刘田、张立昂、王捍贫,清华大学出版社,2016,有兴趣的同学可以阅读。

拓展阅读

其他

主讲教师

屈婉玲   

多年主讲北京大学信息科学技术学院本科生离散数学课程(代数结构与组合数学),系国家级精品课离散数学课程主持人。多年主讲算法分析与复杂性理论、算法分析与设计等研究生必修课。主持过多项教改课题,出版过20多本教材,其中含4本国家级规划教材。承担过多项国家科研项目,主要研究方向是算法设计与分析、软件形式化方法,发表学术论文30多篇。

课程助教

  • jingpinmooc

相关课程推荐

  • 正在进行
    翻译与本地化工程
    本课程将讲授现代语言服务行业中相关的翻译与本地化工程知识,选修本课程的同学,需要具备一定的计算机基础知识,并在修课之前完成预修任务。
  • 正在进行
    需求分析
    需求开发与管理是项目的基础,本课程将对需求定义、需求捕获、需求分析与建模、需求规格化、需求管理提供一套可以实践的解决方案,通过讲解和案例分析指导学员完成一系列练习,使学员对需求分析与需求管理的方法和过程建立较深刻的认识和实际操作的能力。
  • 正在进行
    解密教育的技术变革史
    互联网并非人类历史上第一次“信息技术”革命。人类历史上一共出现过5种媒介技术:口头语言、手工抄写/羊皮书、印刷技术、广播电视和互联网。 媒介技术提供的记录和传承功能,对人类的群体社会认知,带来了革命性的影响。西方历史上曾经发生的两次文明的大发展,都正好处于媒介技术变革前后。希腊文明处于希腊从口传到手工抄写的媒介技术变革中;近代科学史上的哥白尼革命,又正好处于欧洲从手工抄写到机器印刷的技术转型中;今天,轮到了信息技术…… 吟唱、诗歌、戏曲、绘画、文字书写等,都曾经是一种表达“技术”;《荷马史诗》、《圣经》都曾经充当过识字课本;口头语言、羊皮纸卷、印刷书、广播电视,都是曾经的“教育技术”。 这门课程从重新定义教育和人这两个核心概念开始,带着你从媒介史、知识产业分工配套体系、教学模式和教育组织方式等不同的视角,游历人类一路走来传播生态环境、知识产业、教育教学的发展过程,从中寻找媒介技术影响教育变革的规律,指导学习者迎接未来教育变革的挑战,寻找创新和发展方向!

恭喜,报名成功

进入学习中心

恭喜,报名成功

确定

请进入开课界面预览

确定

X

请去您的邮箱验证

还没收到验证邮件?

1. 试试去广告邮件、垃圾邮件目录看看

2. 再次发送验证邮件

对不起,班次容量已满

请报名下一班次

知道了~!

对不起,您没有操作权限

知道了~!