下载文档原格式
《算法设计与分析》教学大纲适用于四年制本科计算机应用技术、信息与计算科学专业（参考学时数：64 学时）一、课程代码7100450，7100451二、课程的性质、任务算法设计与分析是计算机科学的核心问题之一，这门课是计算机专业以及相关专业的一门重要的课程。
本课程的教学目的是：在学生学习掌握了编程的基本技术，掌握了数据结构的基本知识、理论的基础上，比较系统的学习算法理论中的基础部分内容。
在这一课程教学中，培养学生掌握算法设计的方法论，掌握常用的算法设计的方法；掌握算法分析的基本工具、方法、技巧，在解决实际问题时，对于较复杂的问题能抽象出问题的数学模型，设计出有效的算法。
在此基础上学习本课程的中级篇：结构上的算法设计（分类、图的高级部分、流），学生通过这部分的学习，了解算法优化的实现途径，很好的解决数据结构中未能解决的问题、最后是本课程的高级篇：NP完全理论、现代优化计算方法简介。
学生通过这部分的学习初步了解计算复杂性理论的基本内容、现代算法的几个主要发展分支，为今后实际应用或者搞理论研究打下一些必备的理论基础。
三、课程基本要求学生必备的先行课是：高等数学、离散数学、程序设计、数据结构。
本课程不能求快，应循序渐进，培养学生浓厚的学习热情和求知欲。
教学中注重和前期课程数据结构的衔接，使学生明白这门课不同于数据结构的是：数据结构是讨论三种基本数据结构上的基本操作的实现，它是完成“如何做”，算法设计与分析这门课强调的是：怎么巧做，做的更好。
在本课程的后期教学中，特别提倡学生广泛阅读参考书、独立思考、结合实际问题展开讨论的教学方式，并以此达到教师精讲、学生宽学的目的。
课程的基本要求是：1．掌握7种常用的算法设计方法，并能综合、灵活的使用这些基本方法，同时用所学到的知识解决一些实际问题；2．掌握算法分析的基本工具、基本技巧、基本方法；3．掌握数据结构中未能详细、深入了解的部分内容（内存分类，图的高级部分、流上的算法）；4．了解计算复杂性理论中的基本内容，包括：机器模型，NP完全、NP难题，近似计算；5．了解现代的计算算法和算法理论的发展趋势走向。
算法设计与分析课程教学大纲【适用专业】计算机科学与技术【课时】理论课时：32【学分】 2【课程性质、目标和要求】《算法设计与分析》是计算机科学与技术专业的专业课。
无论是计算科学还是计算实践，算法都在其中扮演着重要角色。
本课程的教学目的是讲授在计算机应用中常常遇到的实际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术，培养学生对算法复杂性进行正确分析的能力。
课程基本要求是⑴掌握算法分析的基本概念和理论。
⑵掌握算法设计技术和分析算法以及算法复杂性。
【教学时间安排】本课程计 2 学分，理论课时32, 学时分配如下：【教学内容要点】第一章算法引论一、学习目的要求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 课程背景算法设计与分析是计算机科学的一门重要课程，其主要目的是教授学生算法设计的基本原理、常用算法的实现技巧以及算法性能的分析方法。
本课程旨在培养学生的算法设计能力和问题解决能力，为其今后从事计算机领域的研究和开发工作打下坚实的基础。
1.2 课程目标本课程的目标是使学生：- 掌握算法设计的基本思想和方法；- 熟悉常见的算法设计和实现技巧；- 理解算法的正确性和效率分析方法；- 能够运用所学算法解决实际问题。
二、教学内容2.1 算法基础- 算法的定义与特性；- 算法的表示方法；- 算法设计的基本思想；- 算法分析的基本概念。
2.2 常见算法设计技巧- 递归与分治法；- 贪心法；- 动态规划；- 回溯法。
2.3 数组与矩阵算法- 线性查找；- 二分查找；- 排序算法（如冒泡排序、快速排序等）；- 矩阵运算与应用。
2.4 图算法- 图的基本概念与表示方法；- 图的遍历算法（如深度优先搜索、广度优先搜索等）；- 最短路径算法（如Dijkstra算法、Floyd算法等）；- 最小生成树算法（如Prim算法、Kruskal算法等）。
2.5 字符串算法- 字符串匹配算法（如朴素匹配算法、KMP算法等）；- 字符串编辑距离算法；- 字符串压缩与编码算法。
三、教学方法3.1 理论讲授通过课堂讲授，介绍算法设计与分析的基本概念、原理和方法，并结合具体案例进行讲解，帮助学生深刻理解算法的设计思想和实现技巧。
3.2 课堂练习在理论讲授的基础上，组织学生进行算法设计的实践与练习，通过编写代码解决问题，培养学生的分析和解决问题的能力。
3.3 实验教学设置相关实验项目，让学生通过实验操作来巩固和应用所学算法知识，培养学生独立分析和解决实际问题的能力。
3.4 作业与考核布置实践作业，要求学生独立完成算法设计与实现，以检验学生对所学知识的掌握程度。
通过考核测试学生对算法设计和分析的理解与应用能力。
算法设计与分析课程教学大纲(DesignandAna1ysisofA1gorithms)48实验学时：0课外学时：03计算机科学与技术一、课程的性质、目的和任务《算法分析与设计》课程是计算机专业的一门限选专业课程，是计算机科学与技术应用的核心。
设立本课程的目的是适应21世纪我国计算机科学技术及软件工程人才培养的需要,培养学生设计和分析算法的能力。
通过学习本课程，学生应该掌握计算机软件常用的几种算法,并可以对算法的复杂性进行分析,从而能够在实际工作中根据具体问题设计和优化算法。
二、课程教学的基本要求通过本课程的学习，学生应比较系统地掌握算法设计的基本方法，加深对计算机领域中常用的非数值算法的理解和应用。
这对于培养学生在计算机科学与技术领域的兴趣、提高他们动手进行程序设计的能力以及解决实际问题的技能技巧无疑有着深远的意义。
学生在学习本课程时，要善于把算法设计的基本理论与解决实际问题现实结合起来。
通过学习和研究经典的数学、计算机问题，如何使用具体的算法进行求解。
为了较好地理解和掌握不同的算法,要勤于思考、联系实际，能够对比较经典问题使用不同的算法进行求解，从中得到启迪和借鉴，提高算法的设计和分析能力。
必要的时候要强化一些算法设计的模式和框架，以求达到对相关算法分析与设计的融会贯通。
三、课程的教学内容、重点和难点本课程的重点：贪心算法，动态规划，基本检索与周游方法，回溯法。
本课程的难点：回溯法，分枝-限界法。
第1章算法概述（2学时）教学内容：1.算法与程序2 .表达算法的抽象机制3 .描述算法4 .算法复杂性分析。
基本要求：理解算法的概念；理解什么是程序，程序与算法的区别和内在联系；掌握求解问题的基本步骤；掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念；掌握算法复杂性的渐近性态的数学表述；掌握用C++语言描述算法的方法。
学时数: 其中: 学分数:适用专业:第2章递归与分治策略（10学时）教学内容：1.递归的概念2 .分治法的基本思想3 .二分搜索技术4 .棋盘覆盖5 .合并排序6 .快速排序7 .线性时间选择8 .最接近点对问题9 .循环赛日程表基本要求：理解递归的概念；掌握设计有效算法的分治策略；通过二分搜索技术、Strassen 矩阵乘法、合并排序和快速排序、线性时间选择等范例的学习掌握分治策略设计技巧。
算法分析与设计教学大纲一、课程概述二、预修条件1.数据结构基础知识。
2.编程语言基础。
三、授课目标1.掌握算法分析的基本方法和工具。
2.理解常见算法的设计思想和实现技巧。
3.能够独立设计、实现和优化算法解决实际问题。
四、教学内容1.算法基础知识（1）算法的概念和分类（2）算法分析的基本概念和方法（3）复杂度分析（4）递归与递归算法（5）分治法与减治法2.基本算法设计（1）贪心算法（2）动态规划算法（3）回溯算法3.高级算法设计（1）图算法：最短路径、最小生成树等（2）网络流算法：最大流、最小割等（4）近似算法：近似算法的基本思想与应用4.数据结构与算法分析（1）线性表和链表（2）栈和队列（3）树和二叉树（4）图和图的遍历算法五、教学方法1.理论课讲授：通过教师讲解、演示和示范等方式，让学生掌握算法基本知识和分析方法。
2.实践教学：通过课程设计和编程实践，让学生动手实践算法设计与实现，并对其进行分析和优化。
3.讨论与交流：组织学生进行小组讨论和互动交流，培养学生的合作学习能力和问题解决能力。
六、教学评估1.平时成绩：考察学生的课堂参与、作业完成情况和实验报告质量。
2.期中考试：考察学生对课程内容的掌握和理解。
3.期末考试：考察学生对课程内容的整体把握和综合应用能力。
七、参考教材1. 算法导论（第3版）- Thomas H. Cormen等2. 算法设计与分析基础（第4版）- Levitin A. V.八、教学资源1.电子课件和习题集。
2.在线编程平台和算法分析工具。
九、教学进度安排1.第1-2周：算法基础知识2.第3-5周：基本算法设计3.第6-8周：高级算法设计4.第9-11周：数据结构与算法分析5.第12-14周：综合应用与实践6.第15周：复习与总结备注：以上为算法分析与设计教学大纲的基本框架和内容，具体教学安排和进度可根据实际情况进行调整补充。
算法设计与分析教学大纲算法设计与分析教学大纲引言：算法设计与分析是计算机科学领域中的重要课程之一。
它涉及到计算机程序的设计、性能分析和优化，对于培养学生的计算思维和解决问题的能力至关重要。
本文将探讨算法设计与分析教学的目标、内容和方法。
一、教学目标1. 培养学生的算法设计能力：通过学习不同的算法设计方法，使学生能够运用适当的算法解决实际问题。
2. 提高学生的算法分析能力：学生应该能够分析算法的时间复杂度和空间复杂度，以便评估算法的效率。
3. 培养学生的团队合作和沟通能力：通过小组项目和讨论，学生将学会与他人合作解决问题，并能够清晰地表达他们的思想。
二、教学内容1. 算法基础知识：介绍算法的基本概念和术语，如输入、输出、控制结构、迭代和递归等。
2. 基本算法设计方法：介绍常见的算法设计方法，如贪心算法、分治算法、动态规划和回溯算法等。
3. 常见算法的实现与分析：通过实例讲解常见的排序算法、查找算法和图算法，并对它们的时间复杂度和空间复杂度进行分析。
4. 高级算法设计方法：介绍一些高级的算法设计方法，如分支限界法、随机化算法和近似算法等。
5. 算法的应用：通过实际案例，讨论算法在不同领域的应用，如网络优化、图像处理和人工智能等。
三、教学方法1. 理论讲解：通过课堂讲解，向学生介绍算法的基本概念和设计方法，并解释其原理和应用。
2. 编程实践：通过编写程序，学生将实际运用所学算法解决问题，并通过实验验证算法的正确性和效率。
3. 小组项目：学生将组成小组，共同解决一个复杂的问题，通过合作和讨论，培养团队合作和沟通能力。
4. 论文阅读与讨论：学生将阅读并讨论与算法设计与分析相关的研究论文，以拓宽他们的视野和思维。
结语：通过算法设计与分析的教学，学生将培养解决问题的能力和计算思维，为他们未来的学习和工作打下坚实的基础。
同时，通过小组项目和讨论，学生将学会与他人合作解决问题，并能够清晰地表达他们的思想。
希望学生们能够在这门课程中获得知识的同时，也能够培养出批判性思维和创新能力，为未来的发展做好准备。
算法设计与分析课程教学大纲【课程编码】JSZX0490【适用专业】计算机科学与技术【课时】理论课时：54，实验课时：16【学分】 3【课程性质、目标和要求】《算法设计与分析》是计算机科学与技术专业的专业课。
无论是计算科学还是计算实践，算法都在其中扮演着重要角色。
本课程的教学目的是讲授在计算机应用中常常遇到的实际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术，培养学生对算法复杂性进行正确分析的能力。
课程基本要求是⑴掌握算法分析的基本概念和理论。
⑵掌握算法设计技术和分析算法以及算法复杂性。
【教学时间安排】本课程计 3 学分，理论课时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. 优化搜索策略【教学（实验）内容要点】算法设计与分析实验是算法设计与分析课的一个实践性教学环节。
算法设计与分析一、说明（一）课程性质计算机科学是一种创造性思维活动，其教育必须面向设计。
计算机算法设计与分析正是一门面向设计，且处于计算机学科核心地位的教育课程。
设计一个高效的程序不仅需要编程小技巧，更需要合理的数据组织和清晰高效的算法，这正是计算机科学领域里数据结构与算法设计所研究的主要内容。
（二）教学目的通过对本课程的学习与研究,使学生掌握算法设计的主要方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法复杂性分析奠定坚实的理论基础，对学生将来从事计算机系统结构、系统软件和应用软件的研究与开发提供一个广泛扎实的计算机算法知识基础。
（三）教学内容算法及算法复杂性基本概念,算法描述,有效算法最常用的设计策略——递归和分治法,动态规划法的设计要点与适用性，贪心算法，回溯法和分支限界法，许多难解问题的高效算法——概率算法，以及NP完全理论和NP难问题的近似解法.传统算法实例分析，算法领域研究热点介绍。
（四）教学时数课堂教学36学时，实验部分36学时，总计36+36/2=54学时（五）教学方式讲授+上机实验+课题设计对每一教学内容，首先介绍一种算法设计策略的基本思想，然后从解决计算机科学和应用中的实际问题入手，由简到繁地描述几个经典的精巧算法。
同时对每个算法所需的时间和空间进行分析,使学生既能学到一些常用的精巧算法，又能通过对算法设计策略的反复应用，牢固掌握这些算法设计的基本策略，以期收到融会贯通之效。
在为各种算法设计策略选择用于展示其设计思想与技巧的具体应用问题时,有意义重复选择某些经典问题，使学生能深刻地体会到一个问题可以用多种设计策略求解.同时通过对解同一问题的不同算法的比较，使学生更容易体会到每一种具体算法的设计要点。
随着内容的逐步展开，学生也将进一步感受到综合应用多种设计策略可以更有效地解决问题。
二、本文（一）课堂教学部分第一章算法概述教学要点：算法的基本概念,算法的计算复杂性教学时数：建议2学时7p29188 7204 爄］27848 6CC8 泈20258 4F22 伢教学内容：第一节算法与程序（0。
《算法分析与设计》课程教学大纲【课程编号】：14314025【英文译名】：Analysis and Design of Computer Algorithms【适用专业】：软件工程、计算机科学与技术、信息安全【学分数】：3【总学时】：48学时【实践学时】：0一、本课程教学目的和课程性质本课程是软件工程、计算机科学与技术、信息安全等专业的选修课程，也可作为其它计算机相关专业的选修课程。
课程属于专业教育课。
课程主要介绍计算机算法分析、算法设计及复杂性理论的基本概念、基本的算法分析方法和常用的算法设计方法。
通过本课程的教学，强化学生算法分析与设计的基础理论知识，使学生掌握计算机算法分析的基本方法及常见的算法设计方法（如：分治法、回溯法、贪心法、动态规划法、分枝限界法等）。
通过学习，学生能够用利用常见的算法设计方法来解决软件开发中的实际问题。
培养扎实的专业知识和基本技能和从事应用软件开发和测试的能力。
二、本课程的基本要求本课程的基本要求是让学生理解计算机算法效率分析与设计所涉及的基本概念和基础知识，掌握基本的算法分析方法和常见的算法设计方法，能熟练应用课程介绍的算法设计方法来解决软件开发中的实际问题。
通过对算法实例的分析，进一步加深学生对算法设计方法的认识和理解。
1、理解算法的基本概念和算法的效率分析方法。
2、理解分治策略的原理、效率分析，掌握分支策略在常见问题（如：二分检索、归并分类、快速排序、选择问题等）问题中的应用。
了解分治策略的变形（减治策略、变治策略）的思想和简单应用。
3、理解动态规划的原理、适用条件，了解算法的效率，掌握该算法在常见问题（如：多段图、最优二分检索树、0/1背包问题、货郎担问题、可靠性设计等）问题中的应用。
4、理解贪心方法的原理、效率分析方法，掌握在常见问题（如：背包问题、带有期限的作业排序、最小生成树、单源点最短路径等）问题中的应用。
5、理解回溯法的原理，掌握在常见问题（如：8-皇后、子集和数、图的着色、哈密顿环等）问题中的简单应用。
6、了解分支-限界方法的基本思想和简单应用。
7、了解基本的检索和周游方法的基本思想。
8、了解NP-难度和NP-完全问题基本思想和简单应用。
9、了解概率算法的基本思想及简单应用。
三、本课程与其他课程的关系该课程主要涉及算法的分析与设计，要求学生具备较好的程序设计能力，具有一定的数据结构、离散数学和数学分析基础。
前修课程：离散数学、数据结构四、课程内容（一）算法的概念与效率分析基础1、算法分析基础：算法的定义和特征，算法的时间复杂性、空间复杂性，算法运行时间估计，最优算法，递归算法的效率分析；2、算法的表示：伪代码的使用。
重点：算法的定义和特征，算法效率分析的基本方法和表示方法、递归算法的效率分析。
难点：算法时间复杂性的估计与表示、递归算法的效率分析。
（二）分治策略1、分治策略率的基本原理和效率分析；2、分治策略的典型问题应用及算法的效率分析（如：二分检索、找最大和最小元素、归并分类、快速分类、选择问题、斯特拉森矩阵乘法）；3、分治策略的变形（减治策略、变治策略）及简单应用。
重点：分治策略的基本思想及其应用。
难点：二分检索、归并分类、快速分类等问题中的算法时间复杂性的分析。
（三）贪心方法1、贪心方法的基本思想、适用条件和效率分析；2、贪心方法的典型问题的应用及算法效率分析（背包问题、带有限期的作业排序、最优归并模式、最小生成树、单源点最短路径）。
重点：贪心策略的基本思想及其适用条件。
难点：背包问题、最小生成树问题、最短路径问题的解决方法及时间复杂性的分析。
（四）动态规划1、动态规划的基本思想和适用条件，最优性原理；2、动态规划典型问题的应用及算法效率分析（如：多段图、每对结点之间的最短路径、最优二分检索树、0/1背包问题、可靠性设计、货郎担问题、流水线调度问题等）。
重点：动态规划的基本思想、适用条件及其应用。
难点：多段图、最短路径、0/1背包、可靠性设计、货郎担问题的解决方法及时间复杂性的分析。
（五）基本检索及周游方法1、图的基本检索与遍历方法简介；2、深度优先搜索及其应用；3、广度优先搜索及其应用。
重点：图的遍历的基本思想及其应用。
难点：图遍历算法的时间复杂性的分析。
（六）回溯法与分支限界法1、回溯法的基本思想及效率估计，限界函数；2、回溯法在典型问题（8-皇后问题、子集和树的问题、图的着色、哈密顿环、背包问题等）中的简单应用及算法；3、分支限界法的基本思想及简单应用。
重点：回溯法的基本思想、适用条件及其简单应用。
难点：限界函数的确定，8-皇后问题、子集和数问题、图的着色问题的解决方法及时间复杂性的分析。
*（七）概率算法1、概率算法的概念；2、随机数；3、数值概率算法。
重点、难点概率算法的概念、随机数的概念、数值概率算法。
*（八）NP-完全问题1、计算模型；2、P类与NP类；3、NP完全问题；4、NP完全问题的近似算法。
重点：NP完全问题的基本概念和计算模型。
难点：NP完全问题的近似算法。
*（九）计算复杂性引论1、计算模型：图灵机；2、k带图灵机和时间复杂性；3、离线图灵机和空间复杂性；4、带压缩和线性增速复杂性；5、类之间的关系归约；6、完全性；重点：计算模型—图灵机。
难点：各类图灵机的时空复杂性分析。
注：打“*”为选将内容。
五、教学方法建议本课程涉及了常见算法分析方法和算法设计技术，比较抽象且难懂。
建议采用案例教学并结合演示让学生理解和掌握各种算法设计方法，通过课堂讨论、课后作业和实验训练，加强学生对各种算法设计方法的掌握。
六、考核方式考核可采用开卷笔试，主要考察学生应用算法设计方法来解决具体问题的能力，再结合平时作业及课堂讨论的表现来考核，平时成绩占总成绩的30%~40%。
七、选用教材及主要参考书1、教材[1] (美) Anany Levtin著. 算法分析与设计基础，潘彦译，清华大学出版社，2004年6月2、参考资料[1] 余祥宣,崔国华，邹海明.计算机算法基础（第二版）.武汉：华中科技大学出版社 . 2000[2] [沙特] M.H. Alsuwaiyel 著，吴伟昶等译.算法设计技巧与分析 .电子工业出版社,2004算法设计与分析英文名称：The Design and Analysis of Computer Algorithms课程编号：COMP4024总学时：32（授课32）学分：2适用对象：计算机专业三年级以上学生先修课程：程序设计语言、离散数学、数据结构使用教材及参考书：[1] 王晓东,《算法设计与分析,清华大学出版社》,2003[2] 刘晓东,《计算机算法设计与分析》,西安交大讲义,1990[3] 朱洪等,《算法设计与分析》,上海科技文献出版社,1989[4] [美]萨拉.巴斯,《计算机算法：设计与分析引论》,上海科技文献出版社, 1989[5] H.Ellis,S.Sartaj,R.Sanguthevar著,冯博琴,叶茂等译,《计算机算法,机械工业出版社》,2006[6] B.Gilles,B.Paul著,邱仲潘等译,《算法基础》,清华大学出版社,2005[7] M.H.Alsuwaiyel著,《算法设计技巧与分析》,电子工业出版社,2003一、课程性质、目的和任务性质：选修课目的：计算机算法设计与分析是继数据结构之后的一门计算机专业基础课程，目的在于加强和培养学生的专业技术理论的抽象和应用能力，掌握好的算法设计和分析方法对学生提高计算机科学理论和素质的作用日显重要。
任务：本课程对计算机科学中总结抽象出的最常用的算法设计策略（分治、贪心、动态规划、回溯、分枝界限法等）、算法分析技术（算法复杂度、T（n）、S（n）等）以及算法理论进行了介绍，期望学生理解和掌握算法设计策略的思想和技巧；本课程对计算机算法的分析评价有一个较为系统规范的方法和科学评价指标，为学生分析评价选择算法奠定基础。
在今后的算法设计工作中能够灵活地运用有关知识，以人为本、物尽所能地设计出恰当合理正确高效的算法在计算机上运行。
二、课程内容简介“计算机科学的核心是算法”。
计算机算法设计与分析是一门专业基础课程，计算机算法设计与分析是继数据结构之后的一门计算机专业基础课程，目的在于加强和培养学生的专业技术理论的抽象和应用能力，掌握好的算法设计和分析方法对学生提高计算机科学理论和素质的作用日显重要。
本课程对计算机科学中总结抽象出的最常用的算法设计策略（分治、贪心、动态规划、回溯、分枝界限法等）、算法分析技术（算法复杂度、T（n）、S（n）等）以及算法理论进行了介绍，期望学生理解和掌握算法设计策略的思想和技巧；本课程对计算机算法的分析评价有一个较为系统规范的方法和科学评价指标，为学生分析评价选择算法奠定基础。
在今后的算法设计工作中能够灵活地运用有关知识，以人为本、物尽所能地设计出恰当合理正确高效的算法在计算机上运行。
实验内容:本实验是“计算机算法设计与分析”课程教学的必要环节。
本实验的目的是配合课程，通过对具体问题按照不同设计策略设计算法、编写程序上机实践、对运行结果进行分析评价，培养学生应用已学算法知识解决问题的能力。
要求学生掌握每种策略的基本设计思想和基本设计方法，对具体问题能采用适宜的策略设计出相应的算法、分析出所设计算法的性态，如能再做出一定的算法改进更好。
本实验要求用计算机高级语言编程，上机实现，最后提交实验报告。
实验基本内容和模式：对教授的分治法、贪心法、动态规划法、回溯法、分枝限界法等一些常用的典型的算法设计策略掌握其思想和具体实现方法。
对给定的问题确定适当的解题策略，编程实现解题算法，分析时间和空间复杂度，按照或改进复杂度评价自己的算法。
三、教学基本要求1．通过对经典算法设计策略的分析，让学生理解并掌握算法设计的基本策略和技术；2．通过对算法复杂度的介绍，使学生掌握算法分析评价选择的指标；3．通过对算法设计和分析的实践，锻炼培养学生运用算法理论和技术解决实际问题的能力，不仅掌握怎样做的技巧，还要明白为什么这样做的道理。
四、教学内容及要求Ⅰ算法分析部分一、概述1 算法的基本特性2 算法分析的目的3 算法的描述4 算法效率的度量要求：理解各名词、术语的含义，掌握算法相关的基本概念；了解理解算法编写的基本规范和描述方法。
二、算法复杂度的测度1 几个术语2 复杂性的渐进性态及其阶要求：理解算法复杂度的表示符号的含义，掌握算法性能的分析方法。
三、算法效率的度量１各个句子的统计２加法规则３乘法规则要求：掌握算法性能的分析统计方法，会表示和统计算法复杂度。
四、递归方程的解法１递归、递归程序2 递归方程的解要求：掌握递归算法的分析统计方法，会解递归方程。
五、存储空间复杂度的测度要求：能比照算法时间复杂度的分析统计方法处理空间复杂度。
