Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Peking University

算法设计与分析(高级) | Advanced Design and Analysis of Algorithms

Peking University via edX

Overview

算法设计与分析是计算机科学的核心课程之一。在了解了分治策略、动态规划、贪心法、回溯和分支限界等基本的算法设计技术的基础上,通过线性规划和网络流算法的学习,可以进一步掌握两类重要问题的建模和算法设计方法。此外,面对实际问题,只有对问题的性质有着清晰的分析,才能提出有效的解决方案。需要进一步考虑的是:怎么估计这个问题的难度?最好的算法的效率有多高?这些都涉及到问题复杂度的分析与计算复杂性理论。通过本课程的学习,可以了解有关计算复杂性理论的基础知识、方法和应用,学习近似算法、随机算法等更多的算法设计技术和分析方法,进一步提高处理复杂问题的能力。

Syllabus

教学大纲:

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

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

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

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

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

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

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

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

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

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

Taught by

Qu Wan Ling, Jiang Ting Ting and Wang Xiao Lin

Tags

Reviews

Start your review of 算法设计与分析(高级) | Advanced Design and Analysis of Algorithms

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.