|
一、课程基本信息
1. 课程层次：专升本
2. 课程性质：专业特色课
3. 学时/学分：80学时/4学分
4. 适用专业：计算机科学与技术
二、课程教学目标及学生应达到的能力
《算法设计与分析》课程是为计算机科学与技术专业学生开设的一门专业特色课。“算法是软件的灵魂”，本课程是计算机学科的重要理论基础，也是软件设计的重要技术基础。本课程在计算机类专业人才培养中长期以来一直占据重要的位置，它将为后续诸多专业课程（比如操作系统、数据库系统原理等）奠定理论和实践基础，在学生专业素质和能力培养体系中发挥重要的作用。
课程目标及能力要求具体如下：
课程目标1：熟练运用递归、分治、归约等数学思想与算法设计与实现；
课程目标2：掌握面向实际问题的数学建模和算法设计方法，理解算法复杂度的表示方法；
课程目标3：掌握面向实际问题的建模、分析、设计和测试等方面的计算思维与创新思维；
课程目标4：掌握针对实际问题运用算法模型和程序设计方法建立解决方案的能力；
课程目标5：在学习过程中培养自主学习习惯和终身学习意识。
三、课时分配
| 序号 |
内容 |
总课时 |
课件教学时数 |
实践教学时数 |
自学及作业时数 |
|
1
|
绪论
|
3
|
2
|
0
|
1
|
|
2
|
算法分析
|
5
|
4
|
0
|
1
|
|
3
|
蛮力法与问题易解性
|
3
|
2
|
0
|
1
|
|
4
|
图搜索算法
|
13
|
4
|
8
|
1
|
|
5
|
分治策略
|
14
|
5
|
8
|
1
|
|
6
|
贪婪策略
|
14
|
5
|
8
|
1
|
|
7
|
动态规划
|
15
|
6
|
8
|
1
|
|
8
|
回溯与分支限界
|
13
|
4
|
8
|
1
|
|
9
|
合计
|
80
|
32
|
40
|
8
|
（注：课堂教学时数为面授教学或课件视频教学课时）
四、课程教学内容与要求
| 序号 |
模块内容 |
教学内容 |
要求 |
课时数 |
|
1
|
绪论
|
有关算法的基本概念
|
理解
|
课件课时：2
自学课时：1
|
|
算法的伪代码描述
|
掌握
|
|
算法设计与问题求解的框架
|
理解
|
|
数据结构简单回顾
|
理解
|
|
2
|
算法分析
|
算法分析框架
|
理解
|
课件课时：4
自学课时：1
|
|
渐近分析基础
|
掌握
|
|
3
|
蛮力法与问题易解性
|
蛮力法
|
理解
|
课件课时：2
自学课时：1
|
|
多项式时间算法
|
理解
|
|
4
|
图搜索算法
|
广度优先搜索及其应用
|
掌握
|
课件课时：4
实践课时：8
自学课时：1
|
|
深度优先搜索及其应用
|
掌握
|
|
图搜索算法在谜题求解中的应用
|
掌握
|
|
5
|
分治策略
|
递归与迭代
|
理解
|
课件课时：5
实践课时：8
自学课时：1
|
|
分治策略的基本思想
|
理解
|
|
分治算法的基本框架
|
掌握
|
|
主定理
|
掌握
|
|
典型的分治算法
|
掌握
|
|
6
|
贪婪策略
|
贪婪策略的基本思想
|
了解
|
课件课时：5
实践课时：8
自学课时：1
|
|
贪婪算法的基本框架
|
掌握
|
|
贪婪算法最优性的分析与证明
|
理解
|
|
典型的贪婪算法
|
掌握
|
|
7
|
动态规划
|
动态规划的基本思想
|
掌握
|
课件课时：6
实践课时：8
自学课时：1
|
|
动态规划的基本框架
|
理解
|
|
动态规划的实现方法
|
掌握
|
|
典型的动态规划算法
|
掌握
|
|
8
|
回溯与分支限界
|
回溯法的基本思想
|
了解
|
课件课时：4
实践课时：8
自学课时：1
|
|
回溯法的基本框架
|
掌握
|
|
“剪枝”的概念
|
理解
|
|
典型的回溯算法，包括但不限于子集和问题、n皇后问题、图的点着色问题等
|
掌握
|
|
基于深度优先的分支限界算法的基本思想
|
了解
|
|
基于深度优先的分支限界算法的基本模式
|
掌握
|
|
典型的分支限界算法，包括但不限于最大团问题、TSP问题、0-1背包问题等
|
掌握
|
|
对“界”的正确估算
|
掌握
|
|
9
|
合计
|
|
|
80
|
五、教学安排建议
学生应结合各章节重难点知识，通过观看网络视频进行网上学习，并完成相应的作业、测试。
六、课程考核建议
| 考核方式 |
权重 |
|
形成性考核
|
活动
|
40%
|
|
作业
|
20%
|
|
终结性考核
|
期末考试（开卷）
|
40%
|
（注：“活动”包括出勤、课堂表现和网上学习等；“实践”包括仿真实验、调研报告、技能考核等）
七、本课程与其它课程的联系与分工
先修课程：程序设计基础，离散数学，数据结构。
后续课程：人工智能基础，大数据概论等。
本课程在教学内容上为后续课程提供必要的理论基础和技能储备。而且，通过本课程的学习，可以培养、训练并提高学生的问题抽象能力、逻辑推理能力、分析问题解决问题的能力和自主性学习能力，使学生学会系统的研究方法。
八、建议教学参考书
教材：
屈婉玲，刘田，张立昂，王捍贫. 算法设计与分析（第2版）. 清华大学出版社. 2016.2.
参考资料：
(美)莱维丁. 算法设计与分析基础（第3版 影印版）. 清华大学出版社. 2015.1.
|