《算法设计与分析教学》课程教学大纲.docx

《《算法设计与分析教学》课程教学大纲.docx》由会员分享，可在线阅读，更多相关《《算法设计与分析教学》课程教学大纲.docx（4页珍藏版）》请在第一文库网上搜索。

1、算法设计与分析课程教学大纲(DesignandAna1ysisofA1gorithms)学时数:其中:学分数:适用专业:48实验学时：0课外学时：03计算机科学与技术一、课程的性质、目的和任务算法分析与设计课程是计算机专业的一门限选专业课程，是计算机科学与技术应用的核心。设立本课程的目的是适应21世纪我国计算机科学技术及软件工程人才培养的需要,培养学生设计和分析算法的能力。通过学习本课程，学生应该掌握计算机软件常用的几种算法,并可以对算法的复杂性进行分析,从而能够在实际工作中根据具体问题设计和优化算法。二、课程教学的基本要求通过本课程的学习，学生应比较系统地掌握算法设计的基本方法，加深对计算机

2、领域中常用的非数值算法的理解和应用。这对于培养学生在计算机科学与技术领域的兴趣、提高他们动手进行程序设计的能力以及解决实际问题的技能技巧无疑有着深远的意义。学生在学习本课程时，要善于把算法设计的基本理论与解决实际问题现实结合起来。通过学习和研究经典的数学、计算机问题，如何使用具体的算法进行求解。为了较好地理解和掌握不同的算法,要勤于思考、联系实际，能够对比较经典问题使用不同的算法进行求解，从中得到启迪和借鉴，提高算法的设计和分析能力。必要的时候要强化一些算法设计的模式和框架，以求达到对相关算法分析与设计的融会贯通。三、课程的教学内容、重点和难点本课程的重点：贪心算法，动态规划，基本检索与周游方

3、法，回溯法。本课程的难点：回溯法，分枝-限界法。第1章算法概述（2学时）教学内容：1.算法与程序2 .表达算法的抽象机制3 .描述算法4 .算法复杂性分析。基本要求：理解算法的概念；理解什么是程序，程序与算法的区别和内在联系；掌握求解问题的基本步骤；掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念；掌握算法复杂性的渐近性态的数学表述；掌握用C+语言描述算法的方法。重点：算法的基本概念和算法的时间复:杂性与空间复杂性。难点：算法的时间复杂性与空间匏杂性分析。第2章递归与分治策略（10学时）教学内容：1.递归的概念2 .分治法的基本思想3 .二分搜索技术4 .棋盘覆盖5 .合并排序6 .快

4、速排序7 .线性时间选择8 .最接近点对问题9 .循环赛日程表基本要求：理解递归的概念；掌握设计有效算法的分治策略；通过二分搜索技术、Strassen矩阵乘法、合并排序和快速排序、线性时间选择等范例的学习掌握分治策略设计技巧。重点：分治算法的设计模式、分治法的效率分析，运用递归与分治策略解决实际问题。难点：运用递归与分治策略解决实际问题。第3章动态规划（10学时）教学内容：1.矩阵连乘问题10 动态规划算法的基本要素11 最长公共子序列12 凸多边形最优三角剖分13 多边形游戏14 图像压缩15 电路布线16 流水作业调度17 背包问题18 .最优二叉搜索树。基本要求：理解动态规划算法的基本概

5、念；掌握设计动态规划算法的步骤；通过矩阵连乘问题、流水作业调度、0-1背包问题和最优二叉搜索树等应用范例掌握动态规划算法的设计策略。重点：动态规划算法的基本要素和设计方法和运用动态规划算法解决实际的问题。难点：运用动态规划算法解决实际的问题。第4章贪心算法（10学时）教学内容：123456活动安排问题贪心算法的基本要素最优装载哈夫曼编码单源最短路径最小生成树多机调度问题19 贪心算法的理论基础基本要求：理解贪心算法的基本概念；掌握贪心算法的基本要素；理解贪心算法与动态规划算法的差异；理解贪心算法的一般理论；通过活动安排问题、哈夫曼编码、单源最短路径和最小生成树等应用范例掌握贪心算法的设计策略。

6、重点：贪心算法的理论基础和设计方法以及运用贪心算法解决具体问题。难点：运用贪心算法解决具体问题。第5章回溯法（8学时）教学内容：12345678回溯法的算法框架装载问题批处理作业调度符号三角形问题n后问题0|1背包问题旅行售货员问题回溯法的效率分析。基本要求：理解回溯法的深度优先搜索策略；掌握用回溯法解题的算法框架；通过装载问题、批处理作业调度、n后问题和旅行售货员问题等应用范例掌握回溯法的设计策略；理解回溯法的效率。重点：回溯算法的基本框架和基本要素以及运用回溯算法解决具体问题。难点：运用回溯算法解决具体问题。第6章分支限界法（8学时）教学内容：I.分支限界法的基本思想20 单源最短路径问题

7、21 装载问题22 布线问题23 电路板排列问题24 批处理作业调度25 0-1背包问题26 旅行售货员问题。基本要求：最优装载问题、单源最短路径问题、布线问题、0-1背包问题、旅行售货员问题和批处理作业调度问题。重点：分支限界算法的设计方法和效率分析。难点：运用分支眼界算法解决具体问题。四、课程各教学环节要求（-）作业要求.,-r早T题量要求12掌握算法的时间复杂性问题23掌握设计有效算法的分治策略32掌握动态规划算法的设计策略-42运用贪心算法分析和解决具体问题53运用回溯算法分析和解决具体问题62运用分支限界算法解决具体问题（二）考试环节1）本课程的命题考试将根据本大纲所规定的考试内容和

8、考试目标来确定考试范围和考核要求。考试命题会覆盖各章，并适当突出重点章节，体现本课程的内容重点。2）本课程在试题中对不同能力层次要求的分数比例一般为：了解占20%,理解占30%,简单应用占30%,综合运用占20%。3）试题合理安排难易度结构。试题难易度可分为3个等级。不同难度试题的分数比例为：30%,50%,20%O4）本课程采取期末考试与平时作业考查相结合的方法，期末考试成绩占70%,平时作业成绩（含实验）占30%。期末考试闭卷笔试，根据教学大纲命题，考试时间为120分钟,卷面分值100分。五、学时分配总学时48时，教学各环节具体分配如下:章节主要内容各教学环节学时分配业量作题备注讲授实验讨

9、论习题课外其它小计算法概述2222递归与分治策略101033动态规划101024贪心算法101025回溯法8836分支限界法6282fr4624814六、本课程与其它课程的联系本课程主要介绍算法设计的基本方法，其先修课为高等数学、高等代数、程序设计、数据结构。通过本课程的学习，能够在掌握算法设计基本方法的基础上，加深对计算机领域中常用的非数值算法的理解和应用。七、教材与教学参考书（一）教材：王晓东.计算机算法分析与设计.北京：电子工业出版社，2001年。（二）参考书：I宋文，吴坦.算法分析与设计.重庆：重庆大学出版社，2001年。2宋晏.计算机算法基础.北京：中国电力出版社，2003年.3刘璟.计算机算法引论-设计与分析技术.北京：科学出版社，2003年。