算法设计与分析是计算机科学的核心课程之一。在了解了分治策略、动态规划、贪心法、回溯和分支限界等基本的算法设计技术的基础上,通过线性规划和网络流算法的学习,可以进一步掌握两类重要问题的建模和算法设计方法。此外,面对实际问题,只有对问题的性质有着清晰的分析,才能提出有效的解决方案。需要进一步考虑的是:怎么估计这个问题的难度?最好的算法的效率有多高?这些都涉及到问题复杂度的分析与计算复杂性理论。通过本课程的学习,可以了解有关计算复杂性理论的基础知识、方法和应用,学习近似算法、随机算法等更多的算法设计技术和分析方法,进一步提高处理复杂问题的能力。
算法设计与分析(高级) | Advanced Design and Analysis of Algorithms
Project detail
Overview
Syllabus
教学大纲:
第一周:线性规划
介绍线性规划的例子、二维线性规划的图解法和线性规划的标准形,讨论线性规划可行解的性质,给出求解线性规划的单纯形法与单纯形表。
第二周:线性规划的对偶与应用
介绍对偶线性规划、对偶单纯形法、整数线性规划的分支限界算法,讨论线性规划的应用。
第三周:最大流问题
介绍网络流及其性质、最大流与最小割的概念,讲授Ford-Fulkeson算法和Dinic算法。
第四周:最小费用流与网络流应用
介绍最小费用流与Floyd算法、最小费用流的负回路算法与最短路径算法,讨论网络流算法的应用。
第五周:问题的计算复杂度分析
介绍有关问题计算复杂度分析的基本概念,给出决策树定义并作出检索问题的时间复杂度分析、介绍冒泡排序与堆排序。
第六周:排序及选择问题的复杂度分析
介绍堆排序算法、定义排序算法的决策树,对排序问题及选最小问题进行复杂度分析、介绍通过归约估计问题难度的下界的方法。
第七周:NP完全性理论
介绍NP完全理论的基本概念:难解问题与易解问题、判定问题、NP类与P类、多项式时间变换等,Cook-Levin定理。
第八周:几个NP完全问题
介绍可满足性问题、顶点覆盖、哈密顿回路与货郎问题、恰好覆盖、子集和、0-1背包、整数线性规划等。
第九周:近似算法
介绍近似算法的设计思想及分析方法,针对多机调度、货郎问题、0-1背包等问题讨论了近似算法的设计思想与分析方法。
第十周:随机算法
介绍随机算法的设计思想和分析方法,讨论了随机快速排序与选择算法以及n后问题、主元素测试、素数测试等随机算法。
Industry Categories
Languages required
Related Courses
- Data Structures and Algorithms using C++ : Zero To Mastery
- Data Structures and Algorithms in Python
- An introduction to algorithms in Python
- Programming for Everybody: Python Data Structures
- Programming 102: Think Like a Computer Scientist
- AI and Machine Learning Algorithms Using Python
- Ultimate JavaScript Interview Course
- The Road To Dynamic Programming: Java, JavaScript, & Python
- Searching and Sorting Algorithms
- Recursion and Backtracking (Memoization, D&C, Combinations)