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

1、算法分析与设计课程大纲一、课程概况所属专业:物联网工程专业开课单位：数学与计算机科学学院课程类型:专业选修课程课程代码:07495550开课学期:4学分：2学时：32核心课程:否拟使用教材：国内(外)现有教材：算法与数据结构傅清祥等编 2001年1月第1版电子工业出版社计算机算法设计与分析王晓东编著 2012年第4版:电子工业出版社二、课程描述算法分析与设计是一门面向设计，且处于计算机学科核心地位的教育课程。设计一个高效的程序不仅需要编程技巧，更需要合理的数据组织和清晰高效的算法，这正是计算机科学领域里算法分析与设计所研究的主要内容。三、课程目标本课程的教学目的是讲授在计算机应用中常常遇到的实

2、际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术，培养学生对算法复杂性进行正确分析的能力。四、教学要求依据课程的性质、目的及任务，教学基本要求是紧扣多媒体教学、课后答疑等几个主要环节，要求学生系统地了解、熟悉和掌握算法分析与设计基本知识。授课教师将按照学校本科教学工作有关要求做好教学各项工作，严格要求自己做到不迟到、不早退。将根据本大纲要求，认真备课完成教案与讲稿编写等各项课前准备工作；授课过程力求内容充实、概念准确、思路清晰、详略得当、逻辑性强、重难点突出；同时重视对学生的学习方法指导和课堂教学效果信息的反馈，实现教与学的双向互动；将结合课程目标要求，做好考核内容设计，并严格按照本

3、大纲要求做好出勤率统计、作业评价等各项工作。通过本课程教学，使学生不仅能够学习到算法分析与设计的相关理论知识与设计分析方法，还能提高实践操作与应用的专业技能，以及分析问题与解决问题的全面综合素质。学生应根据课程大纲要求制定本门课程学习计划，加强学业管理，严格自我要求，提升自主学习能力，主动适应课程学习要求。参与课堂教学活动不迟到、不早退，无正当理由不请假，上课认真听讲，不做任何与课堂教学无关事宜，积极与授课教师进行教学互动，同时利用课余时间做好预习、复习、课外书籍阅读等工作，主动与同学开展合作学习，认真完成任课教师布置的各项作业。五、考核方式及要求教学过程是知识消化、理解和升华的过程，各个教学

4、环节之间是相互影响、相互依存的，各个环节的统一协调，齐抓并重是提高教学质量的根本保证，也是培养学生自主学习能力的必要措施。因此，在教学过程中对学生的学习过程实施全程考核。课程将考勤、上机作业、答疑质疑、综合实验情况量化成分值作为本课程的平时成绩。课程总成绩 = 平时分（60）+期末考试（40）课程期末考试形式：闭卷笔试六、课程内容第一章算法引论（授课时间：第四学期第12周）教学目标：了解算法的计算复杂性分析方法，理解算法分析的基本理论教学重点：掌握算法分析的基本概念教学难点：计算复杂性分析方法学时：4学时教学方法：讲授法、演示法主要内容：（1）算法的基本概念；（2）表达算法的抽象机制；（3）描

5、述算法的方法；（4）算法的计算复杂性分析方法。学习方法：认真听讲、积极思考，小组讨论课后作业：算法性能分析第二章分治算法（授课时间：第四学期第34周）教学目标：理解典型范例中递归与分治策略应用技巧，掌握递归与分治策教学重点：分治法的基本思想教学难点：递归与分治策略应用技巧学时：4学时教学方法：讲授法、演示法主要内容：（1）递归的概念；（2）分治法的基本思想；（3）二分搜索技术；（4）Strassen阵乘法。学习方法：认真听讲、积极思考，小组讨论课后作业：最接近点对问题，循环赛日程表第三章贪心算法（授课时间：第四学期第56周）教学目标：了解贪心算法的理论基础及基本要素，理解典型范例中贪心算法的设

6、计思想教学重点：贪心算法的理论基础教学难点：贪心算法的设计要点学时：4学时教学方法：讲授法、演示法主要内容：（1）贪心算法的基本要素；（2）哈夫曼编码；（3）最小生成树；（4）多机调度问题。学习方法：认真听讲、积极思考，小组讨论课后作业：最优装载，活动安排第四章动态规划（授课时间：第四学期第79周）教学目标：理解典型范例中动态规划算法的设计思想教学重点：掌握动态规划算法的基本要求以及算法的设计要点教学难点：动态规划算法的基本要素学时：6学时教学方法：讲授法、演示法主要内容：（1）最长公共子序列；（2）凸多边形最优三角剖分；（3）流水作业调度；（4）图像压缩；（5）动态规划加速原理。学习方法：认

7、真听讲、积极思考，小组讨论课后作业：最长公共子序列，0l背包问题第五章回溯法（授课时间：第四学期第1012周）教学目标：掌握回溯法的算法框架和应用技巧教学重点：回溯法的算法框架教学难点：理解回溯法的效率分析方法学时：6学时教学方法：讲授法、演示法主要内容：（1）装载问题；（2）图的m着色问题；（3）旅行售货员问题；（4）连续邮资问题；（5）回溯法的效率分析。学习方法：认真听讲、积极思考，小组讨论课后作业：n后问题，旅行售货员问题第六章分支限界法（授课时间：第四学期第1315周）教学目标：理解分支限界法的基本思想及应用教学重点：分支限界法的算法框架教学难点：掌握典型范例中分支限界法的应用技巧学时：6学时教学方法：教学法、演示法主要内容：（1）单源最短路径问题；（2）电路板排列问题；（3）布线问题；（4）批处理作业调度。学习方法：认真听讲、积极思考，小组讨论课后作业：0-1背包问题，批处理作业调度第七章NP完全性理论（授课时间：第四学期第1617周）教学目标：理解P类与NP类问题及应用教学重点：P类与NP类问题相关模型教学难点：理