算法设计与分析教学大纲

《算法设计与分析教学大纲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析课程教学大纲【课程编码】JSZX0490【适用专业】计算机科学与技术【课时】理论课时：54，实验课时：16【学分】3【课程性质、目标和要求】《算法设计与分析》是计算机科学与技术专业的专业课。无论是计算科学还是计算实践，算法都在其中扮演着重要角色。本课程的教学目的是讲授在计算机应用中常常遇到的实际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术，培养学生对算法复杂性进行正确分析的能力。课程基本要求是⑴掌握算法分析的基本概念和理论。⑵掌握算法设计技术和分析算法以及算法复杂性。【教学时间安排】　　本课程计3学分，理论课时54+实验课时16,学时分配如下：

2、序号课程内容/实验名称实验类型课时备注1算法引论理论课时4 2递归与分治策略/分治法实验设计理论课时6+实验课时83动态规划/动态规划实验设计理论课时8+实验课时8 4贪心算法理论课时65回溯法理论课时66分支限界法理论课时67概率算法理论课时68NP完全性理论理论课时49近似算法理论课时4710算法优化策略理论课时4 合计理论课时54+实验课时16【教学内容要点】第一章算法引论一、学习目的要求1．了解算法的计算复杂性分析方法2．理解算法分析的基本理论3．掌握算法分析的基本概念二、主要教学内容1.算法的基本概念　　2.表达算法的抽象机制　　3.采用Java语言与自然语言

3、相结合的方式描述算法的方法4.算法的计算复杂性分析方法第二章递归与分治策略一、学习目的要求1．理解典型范例中递归与分治策略应用技巧2．掌握递归与分治策略3．掌握数学归纳法证明算法正确性方法二、主要教学内容1.递归的概念　　2.分治法的基本思想　　3.二分搜索技术4.大整数的乘法5.Strassen阵乘法6.棋盘覆盖7.合并排序8.快速排序9.线性时间选择10.最接近点对问题11.循环赛日程表第三章动态规划一、学习目的要求1．理解典型范例中动态规划算法的设计思想2．掌握动态规划算法的基本要求以及算法的设计要点7二、主要教学内容1.矩阵连乘问题　　2.动态规划算法的基本要素

4、　　3.最长公共子序列4.最大子段和5.凸多边形最优三角剖分6.多边形游戏7.图像压缩8.电路布线9.流水作业调度10.0—l背包问题11.最优二叉搜索树12.动态规划加速原理三、课堂讨论选题1.最长公共子序列2.0—l背包问题第四章贪心算法一、学习目的要求1．了解贪心算法的理论基础及基本要素2.理解典型范例中贪心算法的设计思想3.掌握贪心算法的设计要点二、主要教学内容1.活动安排问题　　2.贪心算法的基本要素　　3.最优装载4.哈夫曼编码5.单源最短路径6.最小生成树7.多机调度问题8.贪心算法的理论基础三、课堂讨论选题1.最优装载2.单源最短路径第五章回溯法一、学习

5、目的要求1．理解回溯法的效率分析方法2．掌握回溯法的算法框架和应用技巧7二、主要教学内容1.回溯法的算法框架　　2.装载问题　　3.批处理作业调度4.符号三角形问题5.n后问题6.0—l背包问题7.最大团问题8.图的m着色问题9.旅行售货员问题10.圆排列问题11.电路板排列问题12.连续邮资问题13.回溯法的效率分三、课堂讨论选题1.0—l背包问题2.图的m着色问题第六章分支限界法一、学习目的要求1．理解分支限界法的基本思想2．掌握典型范例中分支限界法的应用技巧二、主要教学内容1.分支限界法的基本思想　　2.单源最短路径问题　　3.装载问题4.布线问题5.0-1背包问

6、题6.最大团问题7.旅行售货员问题8.电路板排列问题9.批处理作业调度三、课堂讨论选题1.0-1背包问题2.批处理作业调度第七章概率算法一、学习目的要求71．理解概率算法的基本思想2．掌握典型范例中概率算法的应用技巧二、主要教学内容1.随机数　　2.数值概率算法　　3.舍伍德算法4.拉斯维加斯算法5.蒙特卡罗算法第八章NP完全性理论一、学习目的要求1．了解P类与NP类问题2．了解典型的NP完全问题二、主要教学内容1.计算模型　　2.P类与NP类问题　　3.NP完全问题4.一些典型的NP完全问题第九章近似算法一、学习目的要求1．掌握近似算法的基本思想2．掌握常用近似算法的

7、应用二、主要教学内容1.近似算法的性能　　2.顶点覆盖问题的近似算法　　3.旅行售货员问题近似算法4.集合覆盖问题的近似算法5.子集和问题的近似算法第十章算法优化策略一、学习目的要求1．掌握算法优化策略2．掌握算法优化的基本方法二、主要教学内容1.算法优化策略的比较与选择　　2.动态规划加速原理　　3.问题的算法特征4.优化数据结构75.优化搜索策略【教学（实验）内容要点】算法设计与分析实验是算法设计与分析课的一个实践性教学环节。通过实验使学生加深对基本算法设计方法的理解，增强学生对解决问题的不同算法运行时间不同的感性认识，使学生在算法设