教学目的要求.docx
《教学目的要求.docx》由会员分享，可在线阅读，更多相关《教学目的要求.docx（18页珍藏版）》请在冰点文库上搜索。
教学目的要求
教案
2006-2007学年第一学期
课程名称：
计算机算法设计与分析
课程简介
课程编号：
4111309-1,4111309-2,2111309-0
课程名称：
算法设计与分析
英文名称：
TheDesignandAnalysisofAlgorithms
课程类别：
专业课
先修课程：
《C程序设计》、《离散数学》、《计算方法》、《数据结构》
周学时数：
3
总学时数：
54学时（理论54学时，实验0学时）
课程简介：
本课程主要介绍许多经典的非数值算法设计的常用方法，如贪婪法、递归、回溯法、动态规划法、分治法、探索法、分枝限界法等，分析这些算法的时间和空间复杂性。
通过学习算法分析，掌握估计算法的时空复杂度的方法，从而能够正确地评价一个算法，设计出真正好的、有效的算法。
教材名称：
计算机算法设计与分析
教材主编：
王晓东
出版日期：
2004年7月
出版社：
电子工业出版社
参考书目：
1.王若东.算法设计与分析.北京：
清华大学出版社.2007
2.T.H.Cormen.算法导论.北京：
高等教育出版社.2001
3.苏德富、钟诚.计算机算法设计与分析.北京：
电子工业出版社,2001,1
教学大纲
课程名称：
算法设计与分析
英文名称：
DesignandAnalysisofAlgorithms
课程编号：
4111309/2111309
课程类别：
专业选修课
学时数：
54学时（理论54学时，实验0学时）
先修课程：
离散数学、程序设计语言、数据结构
适用年级：
四年级（专升本二年级）
适用专业：
计算机科学与技术
一、内容简介
本课程首先介绍计算复杂性的定义和算法分析的基本方法，结合计算机科学及应用领域中常见的有代表性的非数值算法，介绍了几种重要的算法设计的方法：
分治法、动态规划、贪心法、回朔法、分支限界法，使学生在掌握各种算法的同时，掌握算法分析的基本方法和技巧。
二、本课程的性质、目的和任务
算法设计和分析是计算机软、硬件专业的选修课之一。
算法的研究是计算机科学的核心问题之一，具有极大的应用价值和理论价值，因为它所涉及的范围十分广泛，不论是从事计算机硬件设计，还是从事计算机软件设计，都需要认真研究算法。
本课程特别提倡学生广泛阅读参考书、独立思考、结合实际问题展开讨论的教学方式，并以此达到教师精讲、学生宽学的目的。
三、本课程与其它课程的关系
本课程的前导课程主要包括离散数学、程序设计语言、数据结构等。
其中，离散数学课程为算法设计和分析的学习和理解打下数学方面的基础；学习者需要依靠某种程序设计语言完成算法的计算机实现；算法设计，特别是对大型问题的算法设计，经常要用到表、堆栈、队列、树和图等，没有相应的数据结构方面的知识对算法设计和分析的学习是很困难的。
四、本课程的基本要求
通过本课程中许多常见且有代表性算法的学习，使学生理解和掌握算法设计的主要方法，同时掌握算法分析的基本方法和技巧，培养对算法时间、空间复杂性进行正确分析能力，为独立的设计算法和给定算法进行复杂性分析打下良好的基础。
五、课程内容与学时分配
⏹理论教学内容
第1章概论（4学时）
1、课程内容：
♦算法的概念、算法的特征
♦算法设计和分析的步骤
♦算法的复杂性
2、学习目的与要求
♦掌握基本知识：
如算法的概念、特征；算法设计和分析的步骤
♦掌握算法计算复杂性的几个评价标准：
时间复杂性、空间复杂性；平均复杂性、最坏情况下的复杂性；均匀耗费标准的复杂性分析、对数耗费标准的复杂性分析
本章重点：
算法的计算复杂性分析
本章难点：
对数耗费标准的复杂性分析
3、考核的知识点与考核要求
♦会复述算法的概念、特征；算法设计和分析的步骤
♦会对给出的算法从不同标准进行计算复杂性的分析
第2章递归与分治策略（8学时）
1、课程内容：
♦递归的概念
♦分治法的基本思想
♦分治法：
二分搜索技术、大整数的乘法、Strassen矩阵、棋盘覆盖、合并排序、快速排序、线性时间选择、最接近点对问题、循环赛日程表
2、学习目的与要求
♦掌握用递归技术解决实际问题，会用递归函数过程完成递归算法的实现；会求解递归方程
♦掌握整数乘法等问题的分治算法及该算法的计算复杂性分析
本章重点：
排序算法、整数相乘和矩阵相乘、最接近点对问题
本章难点：
算法的平均时间复杂性下界的证明
3、考核的知识点与考核要求
♦对一些具体实际问题，会书写递归算法；会求解递归方程
♦会给出Strassen矩阵乘法等问题的算法，能对具体实例给出算法的工作过程，并能对该算法进行分析
♦能用分治平衡法对具体问题进行算法实现
第3章动态规划（8学时）
1、课程内容：
♦矩阵连乘问题
♦动态规划算法的基本要素
♦最长公共子序列、最大子段和、凸多边形的最优三角剖分、多边形游戏、图像压缩、电路布线、流水作业调度、0-1背包问题、最优二叉搜索树
♦动态规划加速原理
2、学习目的与要求
♦理解动态规划算法的基本步骤和复杂性分析
♦掌握矩阵连乘等具体问题的动态规划算法的基本思想和设计方法
本章重点：
矩阵连乘问题、最长公共子序列、最大子段和、凸多边形的最优三角剖分、多边形游戏、图像压缩、电路布线、流水作业调度、0-1背包问题、最优二叉搜索树
本章难点：
最优子结构性质、动态规划计算最优值的递归式的构造
3、考核的知识点与考核要求
♦对具体问题，会给出最优值递归式的构造过程
♦能对具体动态规划问题给出解决方法，并给出相应的复杂性分析
第4章贪心法（8学时）
1、课程内容：
♦活动安排问题
♦贪心算法的基本要素
♦最有装载、哈夫曼编码、单源最短路径、最小生成树、多机调度问题
2、学习目的与要求
♦掌握贪心算法的设计思想
♦掌握贪心算法的正确性证明
本章重点：
贪心算法的设计思想
本章难点：
贪心算法的正确性证明
3、考核的知识点与考核要求
♦对具体问题能给出适当的贪心选择策略
♦对给出贪心算法能给出正确性证明
第5章回朔法（8学时）
1、课程内容：
♦回溯法的算法框架
♦装载问题、批处理作业调度、符号三角形问题、n后问题、0-1背包问题、图的m着色问题、旅行售货员问题、圆排列问题、电路板排列问题、连续邮资问题
2、学习目的与要求
♦掌握具体问题的回溯算法
♦掌握回溯法的效率分析
本章重点：
回溯算法的设计
本章难点：
回溯算法的解空间结构与效率分析
3、考核的知识点与考核要求
♦会对具体问题给出约束条件及状态空间树，并给出算法
♦对具体的实际问题会用回溯法找到一个解或所有的解
第6章分支限界法（8学时）
1、课程内容：
♦分支限界法的基本思想
♦单源最短路径问题、装载问题、布线问题、0-1背包问题、最大团问题、旅行售货员问题、电路板排列问题、批处理作业调度
2、学习目的与要求
♦掌握分支限界方法解决具体问题的实现过程和算法
♦掌握分支限界法的算法复杂性分析
本章重点：
单源最短路径问题、装载问题、布线问题、0-1背包问题、最大团问题、旅行售货员问题、电路板排列问题、批处理作业调度
本章难点：
分枝限界法的优先队列、剪枝策略
3、考核的知识点与考核要求
♦会给出队列式、优先队列式分支限界法的实现算法
♦会用分枝限界法解决具体问题的算法实现，并会分析实现过程
第7章概率算法（2学时）
随机数
数值概率算法
舍伍德算法
拉斯维加斯算法
蒙特卡罗算法
第8章线性规划与网络流（4学时）
线性规划问题和单纯性算法
最大网络流问题
最小费用流问题
第9章NP完全性理论与近似算法（4学时）
计算模型
P类与NP类问题
NP完全问题
NP完全问题的近似算法
六、教材与参考书
♦教材
王晓东.算法设计与分析.电子工业出版社,2004.7
♦参考书
1.SaraBaase,AllenVanGelder.计算机算法-设计与分析导论（第三版）影印版.高等教育出版社,2001
2.余祥宣,崔国化,邹海明.计算机算法基础（第二版）.华中科技大学出版社,1998
3.T.H.Cormen.算法导论.高等教育出版社,2001
4.E.Horowitz,S.Sahni.FundamentalsofComputerAlgorithms.NewYork:
ComputerSciencePress,1978
七、本课程的教学方式
本课程的特点是理论性强，思想性强，与相关基础课及专业课联系较多，教学中应注重启发引导学生掌握重要概念的背景思想，理解重要概念的思想本质，避免学生死记硬背。
注重各教学环节（理论教学、习题课、作业、辅导参考）的有机联系，特别是强化习题与辅导环节，使学生加深对课堂教学内容的理解，提高分析解决问题的能力和运算能力。
教学中有计划有目的地向学生介绍各专业课之间的关系，学习算法是获取进一步学习机会的关键学科。
由于学科特点，本课程教学应突出教师的中心地位，通过教师的努力，充分调动学生的学习兴趣。
八、执行大纲时应注意的问题
本大纲是根据教育部颁布的本科基础课教学基本要求，结合我校教学计划制定的。
本大纲对课程内容划定了“理解”、“掌握”、“了解”、“会”等四方面内容，执行时应注意。
课内外学时比为1:
2。
习题课是完成教学基本要求的一个重要的教学环节，习题课学时不应少于总学时的1/6。
在教学过程中，教师应根据学生的情况，按大纲要求，在每部分都要在复习制导书中为学生指明不同档次的课外自学内容。
授课时间2006年9月11—20日第1次课
授课章节
第一章算法概述
任课教师
及职称
徐连诚讲师
教学方法
与手段
多媒体教学与课堂讲授教学相结合
课时安排
4
使用教材和
主要参考书
教材：
王晓东.算法设计与分析.电子工业出版社,2004.7
参考书：
T.H.Cormen.算法导论.高等教育出版社,2001
教学目的与要求：
掌握基本知识：
如算法的概念、特征；算法设计和分析的步骤
掌握算法计算复杂性的几个评价标准：
时间复杂性、空间复杂性；平均复杂性、最坏情况下的复杂性；均匀耗费标准的复杂性分析、对数耗费标准的复杂性分析
教学重点，难点：
本章重点：
算法的计算复杂性分析
本章难点：
对数耗费标准的复杂性分析
教学内容：
算法的概念、算法的特征
算法设计和分析的步骤
算法的复杂性
复习思考题、作业题：
习题1-4、1-5、1-8、1-10
下次课预习要点
第二章递归与分治策略
实施情况及教学效果分析
课堂教学完成、学生作业完成
效果良好
学院审核意见
学院负责人签字
年月日
授课时间2006年9月21日—10月15日第2次课
授课章节
第二章递归与分治策略
任课教师
及职称
徐连诚讲师
教学方法
与手段
多媒体教学与课堂讲授教学相结合
课时安排
8
使用教材和
主要参考书
教材：
王晓东.算法设计与分析.电子工业出版社,2004.7
参考书：
T.H.Cormen.算法导论.高等教育出版社,2001
教学目的与要求：
掌握用递归技术解决实际问题，会用递归函数过程完成递归算法的实现；会求解递归方程
掌握整数乘法等问题的分治算法及该算法的计算复杂性分析
教学重点，难点：
本章重点：
排序算法、整数相乘和矩阵相乘、最接近点对问题
本章难点：
算法的平均时间复杂性下界的证明
教学内容：
递归的概念
分治法的基本思想
分治法：
二分搜索技术、大整数的乘法、Strassen矩阵、棋盘覆盖、合并排序、快速排序、线性时间选择、最接近点对问题、循环赛日程表
复习思考题、作业题：
习题2-2、2-30、2-34、2-35
下次课预习要点
第三章动态规划
实施情况及教学效果分析
课堂教学完成、学生作业完成
效果良好
学院审核意见
学院负责人签字
年月日
授课时间2006年10月16—25日第3次课
授课章节
第三章动态规划
任课教师
及职称
徐连诚讲师
教学方法
与手段
多媒体教学与课堂讲授教学相结合
课时安排
8
使用教材和
主要参考书
教材：
王晓东.算法设计与分析.电子工业出版社,2004.7
参考书：
T.H.Cormen.算法导论.高等教育出版社,2001
教学目的与要求：
理解动态规划算法的基本步骤和复杂性分析
掌握矩阵连乘等具体问题的动态规划算法的基本思想和设计方法
教学重点，难点：
本章重点：
矩阵连乘问题、最长公共子序列、最大子段和、凸多边形的最优三角剖分、多边形游戏、图像压缩、电路布线、流水作业调度、0-1背包问题、最优二叉搜索树
本章难点：
最优子结构性质、动态规划计算最优值的递归式的构造
教学内容：
矩阵连乘问题
动态规划算法的基本要素
最长公共子序列、最大子段和、凸多边形的最优三角剖分、多边形游戏、图像压缩、电路布线、流水作业调度、0-1背包问题、最优二叉搜索树
复习思考题、作业题：
习题3-3、3-4、3-5、3-7、3-12、3-22、3-23
下次课预习要点
第四章贪心法
实施情况及教学效果分析
课堂教学完成、学生作业完成
效果良好
学院审核意见
学院负责人签字
年月日
授课时间2006年10月26月—11月19日第4次课
授课章节
第四章贪心算法
任课教师
及职称
徐连诚讲师
教学方法
与手段
多媒体教学与课堂讲授教学相结合
课时安排
8
使用教材和
主要参考书
教材：
王晓东.算法设计与分析.电子工业出版社,2004.7
参考书：
T.H.Cormen.算法导论.高等教育出版社,2001
教学目的与要求：
掌握贪心算法的设计思想
掌握贪心算法的正确性证明
教学重点，难点：
本章重点：
贪心算法的设计思想
本章难点：
贪心算法的正确性证明
教学内容：
活动安排问题
贪心算法的基本要素
最有装载、哈夫曼编码、单源最短路径、最小生成树、多机调度问题
复习思考题、作业题：
习题4-2、4-3、4-4、4-5、4-6、4-24
下次课预习要点
第五章回溯法
实施情况及教学效果分析
课堂教学完成、学生作业完成
效果良好
学院审核意见
学院负责人签字
年月日
授课时间2006年11月20月—12月10日第5次课
授课章节
第五章回溯法
任课教师
及职称
徐连诚讲师
教学方法
与手段
多媒体教学与课堂讲授教学相结合
课时安排
8
使用教材和
主要参考书
教材：
王晓东.算法设计与分析.电子工业出版社,2004.7
参考书：
T.H.Cormen.算法导论.高等教育出版社,2001
教学目的与要求：
掌握具体问题的回溯算法
掌握回溯法的效率分析
教学重点，难点：
本章重点：
回溯算法的设计
本章难点：
回溯算法的解空间结构与效率分析
教学内容：
回溯法的算法框架
装载问题、批处理作业调度、符号三角形问题、n后问题、0-1背包问题、图的m着色问题、旅行售货员问题、圆排列问题、电路板排列问题、连续邮资问题
复习思考题、作业题：
习题5-14、5-16、5-18、5-27、5-29
下次课预习要点
第六章分支限界法
实施情况及教学效果分析
课堂教学完成、学生作业完成
效果良好
学院审核意见
学院负责人签字
年月日
授课时间2006年12月11—31日第6次课
授课章节
第六章分支限界法
任课教师
及职称
徐连诚讲师
教学方法
与手段
多媒体教学与课堂讲授教学相结合
课时安排
8
使用教材和
主要参考书
教材：
王晓东.算法设计与分析.电子工业出版社,2004.7
参考书：
T.H.Cormen.算法导论.高等教育出版社,2001
教学目的与要求：
掌握分支限界方法解决具体问题的实现过程和算法
掌握分支限界法的算法复杂性分析
教学重点，难点：
本章重点：
单源最短路径问题、装载问题、布线问题、0-1背包问题、最大团问题、旅行售货员问题、电路板排列问题、批处理作业调度
本章难点：
分枝限界法的优先队列、剪枝策略
教学内容：
分支限界法的基本思想
单源最短路径问题、装载问题、布线问题、0-1背包问题、最大团问题、旅行售货员问题、电路板排列问题、批处理作业调度
复习思考题、作业题：
习题6-1、6-2、6-3、6-4、6-5、6-6、6-10
下次课预习要点
第七章概率算法
第八章线性规划与网络流
第九章NP完全性理论与近似算法
实施情况及教学效果分析
课堂教学完成、学生作业完成
效果良好
学院审核意见
学院负责人签字
年月日
授课时间2007年1月2—17日第7次课
授课章节
第七章概率算法；第八章线性规划与网络流；第九章NP完全性理论与近似算法
任课教师
及职称
徐连诚讲师
教学方法
与手段
多媒体教学与课堂讲授教学相结合
课时安排
10（选讲）
使用教材和
主要参考书
教材：
王晓东.算法设计与分析.电子工业出版社,2004.7
参考书：
T.H.Cormen.算法导论.高等教育出版社,2001
教学目的与要求：
了解概率算法的概念和应用实例
了解线性规划与网络流的概念和主要方法
了解NP完全性理论与相关的近似算法
教学重点，难点：
教学重点：
概率算法的概念、线性规划与网络流的概念、NP完全性理论及其近似算法
教学难点：
网络流问题、NP完全性理论
教学内容：
概率算法：
随机数、数值概率算法、舍伍德算法、拉斯维加斯算法、蒙特卡罗算法
线性规划和网络流：
线性规划问题和单纯性算法、最大网络流问题、最小费用流问题
NP完全性理论与近似算法：
计算模型、P类与NP类问题、NP完全问题、NP完全问题的近似算法
复习思考题、作业题：
习题7-1、8-6、9-2
下次课预习要点
实施情况及教学效果分析
课堂教学完成、学生作业完成
效果良好
学院审核意见
学院负责人签字
年月日
升级会员 