《理论课程(含实验内容)教学大纲格式 - 延安大学》由会员分享，可在线阅读，更多相关《理论课程(含实验内容)教学大纲格式 - 延安大学（10页珍藏版）》请在金锄头文库上搜索。
1、理论课程理论课程( (含实验内容含实验内容) )教学大纲格式教学大纲格式 - - 延安大学延安大学算法设计与分析课程教学大纲【课程编码】 JSZX0490【适用专业】 计算机科学与技术【课 时】 理论课时：54，实验课时：16【学 分】 3【课程性质、目标和要求】算法设计与分析是计算机科学与技术专业的专业课。无论是计算科学还是计算实践，算法都在其中扮演着重要角色。本课程的教学目的是讲授在计算机应用中常常遇到的实际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术，培养学生对算法复杂性进行正确分析的能力。课程基本要求是掌握算法分析的基本概念和理论。掌握算法设计技术和分析算法以及算法复杂性。
2、【教学时间安排】本课程计 3 学分，理论课时 54+实验课时 16, 学时分配如下：序号课程内容/实验名称实验类型课时备注1算法引论理论课时 42递归与分治策略/分治法实验设计理论课时 6+实验课时 83动态规划/动态规划实验设计理论课时 8+实验课时 84贪心算法理论课时 65回溯法理论课时 66分支限界法理论课时 67概率算法理论课时 68NP 完全性理论理论课时 49近似算法理论课时 410算法优化策略理论课时 4合 计理论课时 54+实验课时 16【教学内容要点】第一章 算法引论一、学习目的要求1了解算法的计算复杂性分析方法2理解算法分析的基本理论3掌握算法分析的基本概念二、主要教学内
3、容1. 算法的基本概念2. 表达算法的抽象机制3. 采用 Java 语言与自然语言相结合的方式描述算法的方法4. 算法的计算复杂性分析方法第二章 递归与分治策略一、学习目的要求1理解典型范例中递归与分治策略应用技巧2掌握递归与分治策略3掌握数学归纳法证明算法正确性方法二、主要教学内容1. 递归的概念2. 分治法的基本思想3. 二分搜索技术4. 大整数的乘法5. Strassen 阵乘法6. 棋盘覆盖7. 合并排序8. 快速排序9. 线性时间选择10. 最接近点对问题11. 循环赛日程表第三章 动态规划一、学习目的要求1理解典型范例中动态规划算法的设计思想2掌握动态规划算法的基本要求以及算法的设
4、计要点二、主要教学内容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. 贪
5、心算法的理论基础三、课堂讨论选题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
6、. 分支限界法的基本思想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.
7、 一些典型的 NP 完全问题第九章 近似算法一、学习目的要求1掌握近似算法的基本思想2掌握常用近似算法的应用二、主要教学内容1. 近似算法的性能2. 顶点覆盖问题的近似算法3. 旅行售货员问题近似算法4. 集合覆盖问题的近似算法5. 子集和问题的近似算法第十章 算法优化策略一、学习目的要求1掌握算法优化策略2掌握算法优化的基本方法二、主要教学内容1. 算法优化策略的比较与选择2. 动态规划加速原理3. 问题的算法特征4. 优化数据结构5. 优化搜索策略【教学（实验）内容要点】算法设计与分析实验是算法设计与分析课的一个实践性教学环节。通过实验使学生加深对基本算法设计方法的理解，增强学生对解决问题
8、的不同算法运行时间不同的感性认识，使学生在算法设计方法和编程技能等方面得到系统的训练，使学生养成设计良好算法的习惯，为今后从事软件开发和软件理论研究打下良好的实验基础。一、 （实验 1）分治法实验1. 实验目的要求应用分治法算法解决实际问题，并编程实现。2. 实验主要内容(1)写出并调试二分检索的递归程序并调试通过。(2)写出并调试“由底向上“的归并分类程序，从而取消对栈空间的需求。3、实验仪器设备PC 兼容机二、 （实验 2）动态规划实验1. 实验目的要求把动态规划算法应用到求货郎担问题和矩阵乘法问题，并编程实现。2. 实验主要内容（1）写出并调试用动态规划方法求货郎担问题的程序。（2）写出
9、并调试用动态规划方法求矩阵乘法的程序。3. 实验仪器设备PC 兼容机。【成绩考核方式】1. 成绩评定总则全面考核学生在课程学习各个环节的理解、掌握和参与情况2. 平时成绩评定平时成绩考勤成绩作业成绩+课堂讨论成绩3. 期末考核评定课程成绩平时成绩(10%)+实验成绩(20%)+期末成绩(70%)【教材与参考书目】指定教材：算法设计与分析王晓东编著 2003 年 1 月第 1 版 清华大学出版社参考书目：1.算法设计与分析周培德编著 1991 年 1 月第 1 版 机械工业出版社2.算法设计与分析曹新谱编著 1984 年 11 月第 1 版 湖南科技出版社3.算法与数据结构傅清祥等编 2001 年 1 月第 1 版 电子工业出版社4.并行算法引论陈景良编著 1992 年 4 月第 1 版 石油工业出版社【有关说明（教学建议） 】1. 讲解与讨论相结合2. 用通俗易懂的例子描述抽象的概念（ 编制：张根耀 / 审核：郝继升 ）?11
