spContent=“有两种思想，就像摆放在天鹅绒上的宝石那样熠熠生辉，一个是微积分，另一个就是算法。微积分以及在微积分基础上建立起来的数学分析体系造就了现代科学，而算法则造就了现代世界”
——大卫.伯林斯基
“有两种思想，就像摆放在天鹅绒上的宝石那样熠熠生辉，一个是微积分，另一个就是算法。微积分以及在微积分基础上建立起来的数学分析体系造就了现代科学，而算法则造就了现代世界”
——大卫.伯林斯基
—— 课程团队
课程概述
算法是计算机科学的核心，绝大多数科学、商业和技术都与其密切相关。课程将从算法表示、分析、设计策略三个方面开展线上线下混合教学，以实际工程应用问题为导向，开展探究式实践教学，使学生能从数学上分析算法的时间、空间复杂度，针对特定的问题，能形式化描述问题，并选择合适的算法设计策略开展算法设计、分析、证明等，并能对问题的复杂性进行讨论。
教学团队长期从事该课程的教学，多年指导程序设计类学科竞赛，同时具有丰富的工程经验，能将算法设计策略与工程实际问题进行有效结合，有效训练学生的计算思维及解决实际问题的能力。
授课目标
目标1：能够对复杂软件中设计的递归算法、非递归算法的时间复杂度进行数学描述及分析，并能选择合适的渐进符号进行表达。
目标2：理解精确算法、近似算法、算法正确性证明、算法时间复杂性、空间复杂性、算法时间渐进表示等算法时间复杂的分析的概念和符号，能使用标准伪代码对软件工程中的算法进行表达。
目标3：理解分治法、变治法、减治法、时空权衡、动态规划、贪婪策略、迭代改进、分支限界、回溯法等算法设计策略的基本原理及特点，对软件开发中的特定问题，能形式化描述问题，并能选择合适的设计策略进行算法设计与实现，说明算法的正确性，计算算法的时间复杂度，并进行复杂性讨论。
课程大纲
引言
课时目标：了解算法的基本概念及特点；能使用为代码描述正确算法；能复述算法求解问题的过程，以及每一步骤的注意事项。
算法效率分析技术
课时目标：掌握算法效率分析的方法。能重述算法效率分析的框架、算法时间渐进表示的符号及其含义；能对非递归算法的时间效率进行数学分析；能对递归算法的时间效率进行数学分析。
2.1 算法效率分析框架；
2.2 时间渐进表示；
2.3 非递归算法的效率分析；
2.4 递归算法的效率分析。
蛮力法
课时目标：了解蛮力法的基本思想及常见问题的时间效率。能重述蛮力法的基本思想，以及在排序、查找、穷举问题中的时间效率。
3.1 蛮力法的基本思想
3.2 最近对和凸包问题的蛮力法；
3.3 穷举问题的蛮力法。
减治法
课时目标：能重述减治法的基本思想及表现形式；能实现减治法的排序算法，并能分析效率；能实现生成组合对象的算法（排列），并能分析效率；能复述减常数因子和减可变规模的算法的思想及常见问题的时间效率。
4.1 减治法与排序
4.2 生成组合对象的算法
4.3 减常因子算法
4.4 减可变规模算法
分治法
课时目标：掌握分治法的基本思想，能实现合并排序、快速排序、凸包、最近对问题的分治算法，并能分析他们的效率。
5.1 分治法与排序
5.2 快速排序
5.3 最近对问题
5.4 凸包问题
变治法
课时目标：掌握变治法的基本思想及其类别，能实现高斯消元、堆排序的变治算法，并能分析效率。
6.1 变治法与预排序
6.2 高斯消元法
6.3 堆和堆排序
时空权衡
课时目标：掌握时空给权衡的基本思想，能实现计数排序、horspool、boormore及散列表，并能分析其效率。
7.1 时空权衡与技术排序
7.2 字符串匹配中的输入增强技术-hoorspool
7.3 字符串匹配中的输入增强技术-boormore
7.4 散列法
动态规划
课时目标：掌握动态规划基本思想和最优化原理，能用程序设计语言实现背包问题、最优二叉查找树、完全最短路径问题的动态规划算法，并能进行效率分析。
8.1 动态规划基本原理
8.2 背包问题
8.3 最优二叉查找树
8.4 Warshall算法
贪心策略
课时目标：掌握贪心策略的基本原理，能用程序设计语言实现最小生成树、单源点最短路径问题的贪心算法，并能分析效率。
9.1 贪心策略原理
9.2 Prim算法
9.3 Kruskal算法
9.4 Dijkstra算法
迭代改进
课时目标：掌握迭代改进的基本原理，能复述线性规划、网络流问题的迭代改进算法。
回溯与分支限界
课时目标：掌握穷举问题的回溯与分支限界算法，能分析其效率。
展开全部
预备知识
先修知识点：集合、排列、矩阵、高级程序设计语言、图、树、递归等。
先修能力和素质基础：能使用高级程序设计语言完成代码编写、运行与调试的能力，具备一定分析问题和解决问题的能力。
先修主要课程：离散数学、程序设计（C语言）、数据结构。
参考资料
1.(美) Anany Levtin著. 算法分析与设计基础（第三版），潘彦译，清华大学出版社，2015年2月
2．Thomas H.Cormen等著，殷建平,徐云,王刚等译.算法导论（第三版）.机械工业出版社.2013年1月
3.课程实验地址：https://acm.swust.edu.cn
