挑战性实验课程实施方案
--高级算法与程序设计实验
|
课程名称
|
高级算法与程序设计实验
|
授课专业
|
全校各专业
|
年级
|
二年级
|
|
课程编号
|
|
修课人数
|
200
|
|
课程类型
|
必修
|
公共基础课( )；学科基础课( )；专业核心课()
|
|
选修
|
专业选修()；任选课（ ）；公选课(√ )；
|
|
|
理论课( )；实践课( √ )
|
|
授课方式
|
课堂讲授为主（ ）；实验为主（ √ ）；
自学为主（ ）；专题讨论为主（ ）；
其他：
|
是否采用
多媒体授课
|
是
|
|
考核方式及成绩构成
|
考 试(√ )考 查( )
成绩构成及比例：平时20%,上机80%,
|
是否采用
双语教学
|
否
|
|
学时分配
|
讲授40 学时；实验 学时；上机16 学时；习题 学时；课程设计 学时
|
|
教材
|
名称
|
作者
|
出版社及出版时间
|
|
|
算法设计与分析（第3版）
|
吕国英主编
|
清华大学出版社, 2015.06.01
|
|
参考书目
|
1.算法导论. 高等教育出版社,
2. 算法分析与设计
|
T.H.Cormen,等
Michael T等
|
高等教育出版社. 2004.
人民邮电出版社.2006.
|
|
授课时间
|
第 9 周——第 18 周
|
|
第1章高级数据结构
授课时数：共8学时，2次上课完成本章教学内容
一、 教学内容及要求
1.教学内容：
¨ 数据结构的概念、算法的特征
¨ 高级数据结构算法设计和分析的步骤
¨ 算法的复杂性
2. 教学要求
¨ 掌握高级数据结构知识：如优先队列、线段树、树状数组、并查集等
¨ 掌握算法计算复杂性的几个评价标准：时间复杂性、空间复杂性；平均复杂性、最坏情况下的复杂性；均匀耗费标准的复杂性分析、对数耗费标准的复杂性分析
二、教学重点与难点
1. 重点：算法的计算复杂性分析
2. 难点：对数耗费标准的复杂性分析
三、教学设计
（1）理解算法分析的基本思想和概念对后面各个章节的学习具有重要的意义；
（2）了解设计与分析的步骤对掌握各种具体类型的算法设计思想具有重要的意义。
四、作业
http://acm.uestc.edu.cn/#/contest/show/95 ；
五、本章参考资料
1.算法导论.T.H.Cormen等，高等教育出版社. 2004.
2. 算法分析与设计. Michael T等,人民邮电出版社.2006.
第2章图论
授课时数：共8学时，2次上课完成本章教学内容
一、教学内容及要求
1.教学内容：
¨ 图的各类基本概念
¨ 涉及图的各类算法介绍
¨ 图算法介绍：各类图论问题的编程实例，包括单源最短路径、最小生成树、SPFA、Floyd算法、有向无环图、拓扑排序等经典图论问题
2. 教学要求
¨ 掌握用图的各类算法，熟练掌握图方面算法的代码实现
¨ 具体解决图的相关问题
二、教学重点与难点
1. 重点： dijkstra算法，prim算法，kruskal算法，SPFA，FLOYD等算法
2. 难点：网络流问题一直是较难掌握的算法
三、教学设计
理解递归的基本原理与方法对后续的回溯算法以及相关遍历的设计具有重要的意义；
教学中要注意前后知识点的相互联系与照应，视学生情况作适当复习。
四、作业
http://acm.uestc.edu.cn/#/contest/show/113
五、本章参考资料
1.算法导论.T.H.Cormen等，高等教育出版社. 2004.
2. 算法分析与设计. Michael T等,人民邮电出版社.2006.
第3章动态规划
授课时数：共8学时，2次上课完成本章教学内容
一、教学内容及要求
1.教学内容：
¨ 矩阵连乘问题
¨ 动态规划算法的基本要素
¨ 最长公共子序列、最大子段和、凸多边形的最优三角剖分、多边形游戏、图像压缩、电路布线、流水作业调度、0-1背包问题、最优二叉搜索树
¨ 动态规划加速原理
2. 教学要求
¨ 理解动态规划算法的基本步骤和复杂性分析
¨ 掌握矩阵连乘等具体问题的动态规划算法的基本思想和设计方法
二、教学重点与难点
1. 重点：矩阵连乘问题、最长公共子序列、最大子段和、凸多边形的最优三角剖分、多边形游戏、图像压缩、电路布线、流水作业调度、0-1背包问题、最优二叉搜索树
2. 难点：最优子结构性质、动态规划计算最优值的递归式的构造
三、教学设计
理解和掌握动态适宜于解最优化化方面的问题，因此加深对这种理论方法的理解将大大降低后面各个章节的学习难度。
教学中要注意前后知识点的相互联系与照应，视学生情况作适当复习。
四、作业
http://acm.uestc.edu.cn/#/contest/show/96
五、本章参考资料
1.算法导论.T.H.Cormen等，高等教育出版社. 2004.
2. 算法分析与设计. Michael T等,人民邮电出版社.2006.
第4章搜索算法与字符串应用
授课时数：共8学时，2次上课完成本章教学内容
一、教学内容及要求
1.教学内容：
¨ 深度优先搜索、广度优先搜索，剪枝优化，KMP，AC自动机算法
¨ 搜索算法的优化技巧
¨ 字符串应用实现技巧
2. 教学要求
¨ 掌握搜索算法的设计思想
¨ 掌握字符串算法的设计思想
二、教学重点与难点
1. 重点：DFS、BFS、KMP等算法
2. 难点：KMP算法的掌握，剪枝优化策略
三、教学设计
由于搜索算法适用面较广，题型较多,优化的方式技巧也各不尽相同，因此对搜索问题需具体问题具体分析；
教学中要注意前后知识点的相互联系与照应，视学生情况作适当复习。
四、作业
http://acm.uestc.edu.cn/#/contest/show/99
五、本章参考资料
1.算法导论.T.H.Cormen等，高等教育出版社. 2004.
2. 算法分析与设计. Michael T等,人民邮电出版社.2006.
第5章计算几何与数学
授课时数：共8学时，2次上课完成本章教学内容
一、教学内容及要求
1.教学内容：
¨ 叉积的定义及应用，各类凸包算法，半平面交的定义及应用
¨ 中国剩余定理、欧拉定理、费马小定理等方法
¨ 抽屉原理、容斥原理解决存在性问题
2. 教学要求
¨ 掌握计算几何中的各类基本概念和公式
¨ 掌握数论与组合数学中的各类定理和方法
二、教学重点与难点
1. 重点：各类凸包算法，半平面交的定义及应用，数论中中国剩余定理、欧拉定理、费马小定理等方法在算法编程中的应用
2. 难点：如何使用Polya定理对一个问题的各种不同组合状态计数
三、教学设计
理解各类数学公式定理的应用场合和程序实现方法，对这类数学问题的理解学习具有重要的意义；
教学中要注意前后知识点的相互联系与照应，视学生情况作适当复习。
四、作业
http://acm.uestc.edu.cn/#/contest/show/107
五、本章参考资料
1.算法导论.T.H.Cormen等，高等教育出版社. 2004.
2. 算法分析与设计. Michael T等,人民邮电出版社.2006.
