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

算法设计与分析课程教学大纲【课程编码】JSZX0490【适用专业】运算机科学与技术【课时】理论课时：54，实验课时：16【学分】3【课程性质、目标和要求】《算法设计与分析》是运算机科学与技术专业的专业课。无论是计算科学仍是计算实践，算法都在其中扮演着重要角色。本课程的教学目的是教学在运算机应用中常常碰到的实际问题的解法，教学设计和分析各类算法的大体原理、方式和技术，培育学生对算法复杂性进行正确分析的能力。课程大体要求是⑴掌握算法分析的大体概念和理论。⑵掌握算法设计技术和分析算法和算法复杂性。【教学时刻安排】本课程计3学分，理论课时54+实验课时16,学时分派如下：序号课程内容/实验名称实验类型课时备注1算法引论理论课时4

2递归与分治策略/分治法实验设计理论课时6+实验课时83动态规划/动态规划实验设计理论课时8+实验课时8

4贪心算法理论课时65回溯法理论课时66分支限界法理论课时67概率算法理论课时68NP完全性理论理论课时49近似算法理论课时410算法优化策略理论课时4

合计理论课时54+实验课时16【教学内容要点】第一章算法引论一、学习目的要求1．了解算法的计算复杂性分析方式2．理解算法分析的大体理论3．掌握算法分析的大体概念二、主要教学内容1.算法的大体概念2.表达算法的抽象机制3.采用Java语言与自然语言相结合的方式描述算法的方式4.算法的计算复杂性分析方式第二章递归与分治策略一、学习目的要求1．理解典型范例中递归与分治策略应用技能2．掌握递归与分治策略3．掌握数学归纳法证明算法正确性方式二、主要教学内容1.递归的概念2.分治法的大体思想3.二分搜索技术4.大整数的乘法5.Strassen阵乘法6.棋盘覆盖7.归并排序8.快速排序9.线性时刻选择10.最接近点对问题11.循环赛日程表第三章动态计划一、学习目的要求1．理解典型范例中动态计划算法的设计思想2．掌握动态计划算法的大体要求和算法的设计要点二、主要教学内容1.矩阵连乘问题2.动态计划算法的大体要素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.单源最短路径第五章回溯法一、学习目的要求1．理解回溯法的效率分析方式2．掌握回溯法的算法框架和应用技能二、主要教学内容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.最大团问题7.旅行售货员问题8.电路板排列问题9.批处置作业调度三、课堂讨论选题1.0-1背包问题2.批处置作业调度第七章概率算法一、学习目的要求1．理解概率算法的大体思想2．掌握典型范例中概率算法的应用技能二、主要教学内容1.随机数2.数值概率算法3.舍伍德算法4.拉斯维加斯算法5.蒙特卡罗算法第八章NP完全性理论一、学习目的要求1．了解P类与NP类问题2．了解典型的NP完全问题二、主要教学内容1.计算模型2.P类与NP类问题3.NP完全问题4.一些典型的NP完全问题第九章近似算法一、学习目的要求1．掌握近似算法的大体思想2．掌握常常利用近似算法的应用二、主要教学内容1.近似算法的性能2.极点覆盖问题的近似算法3.旅行售货员问题近似算法4.集合覆盖问题的近似算法5.子集和问题的近似算法第十章算法优化策略一、学习目的要求1．掌握算法优化策略2．掌握算法优化的大体方式二、主要教学内容1.算法优化策略的比较与选择2.动态计划加速原理3.问题的算法特征4.优化数据结构5.优化搜索策略【教学（实验）内容要点】算法设计与分析实验是算法设计与分析课的一个实践性教学环节。通过实验使学生加深对大体算法设计方式的理解，增强学生对解决问题的不同算法运行时刻不同的感性熟悉，使学生在算法设计方式和编程技术等方面取得系统的训练，使学生养成设计良好算法的适应，为此后从事软件开发和软件理论研究打下良好的实验基础。一、（实验1）分治法实验1.实验目的要求应用分治法算法解决实际问题，并编程实现。2.实验主要内容(1)写出并调试二分检索的递归程序并调试通过。(2)写出并调试"由底向上"的归并分类程序，从而取消对栈空间的需求。3、实验仪器设备PC兼容机二、（实验2）动态计划实验1.实验目的要求把动态计划算法应用到求货郎担问题和矩阵乘法问题，并编程实现。2.实验主要内容（1）写出并调试用动态计划方式求货郎担问题的程序。（2）写出并调试用动态计划方式求矩阵乘法的程序。3.实验仪器设备PC兼容机。【成绩考核方式】1.成绩评定总则全面考核学生在课程学习各个环节的理解、掌握和参与情形2.平时成绩评定平时成绩＝考勤成绩＋作业成绩+课堂讨论成绩3.期末考核评定课程成绩＝平时成绩(10%)+实验成绩(20%)+期末成绩(70%)【教材与参考书目】指定教材：《算法设计与分析》王晓东编著2003年1月第1版清华大学出版社参考书目：1.《算法设计与分析》周培德编著1991年1月第1版机械工业出版社2.《算法设计与分析》曹新谱编著1984年11月第1