课程简介
“算法设计与分析”是计算机科学与技术专业的一门核心课程。通过学习算法不但对学习其他专业课程奠定了扎实的基础，也对培养学生的计算思维和求解问题的能力起到重要的作用。算法与计算复杂性理论一直是计算机科学研究的热点领域。面对各个应用领域的大量实际问题，最重要的是根据问题的性质选择正确的求解思路，即找到一个好的算法。特别在复杂的、海量信息的处理中，一个好的算法往往起到决定性的作用。 算法设计与分析涉及内容较多，根据MOOC课程的教学特点和需求，我们将它分成两个部分。其中“算法设计与分析(1)”主要讲授有关算法的基础知识和通用设计技术，包括算法的基本概念和数学基础、分治策略、动态规划、贪心法、回溯和分支限界等。“算法设计与分析(2)”是在上述基础上介绍两类重要问题的建模和算法设计，并进一步讨论问题难度的界定和困难问题的应对策略。这次开课的是第二部分“算法设计与分析(2)”。选修本课程的学生应该预先修过“算法设计与分析(1)”或者具有相关的基础。“算法设计与分析(1)”已经在华文慕课平台上线，网址是：http://www.chinesemooc.org/mooc/4748/，需要了解相关教学内容的同学可以访问。
课程大纲
第一周：线性规划
介绍线性规划的例子、二维线性规划的图解法和线性规划的标准形，讨论线性规划可行解的性质，给出求解线性规划的单纯形法与单纯形表。
第二周：线性规划的对偶与应用
介绍对偶线性规划、对偶单纯形法、整数线性规划的分支限界算法，讨论线性规划的应用。
第三周：最大流问题
介绍网络流及其性质、最大流与最小割的概念，讲授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，有兴趣的同学可以阅读。
拓展阅读
其他
主讲教师
汪小林
暂无简介
课程助教
jingpinmooc
相关课程推荐
正在进行
京公网安备 11040202430145号
