下载文档原格式
《算法设计与分析》教学大纲适用于四年制本科计算机应用技术、信息与计算科学专业（参考学时数：64 学时）一、课程代码7100450，7100451二、课程的性质、任务算法设计与分析是计算机科学的核心问题之一，这门课是计算机专业以及相关专业的一门重要的课程。
本课程的教学目的是：在学生学习掌握了编程的基本技术，掌握了数据结构的基本知识、理论的基础上，比较系统的学习算法理论中的基础部分内容。
在这一课程教学中，培养学生掌握算法设计的方法论，掌握常用的算法设计的方法；掌握算法分析的基本工具、方法、技巧，在解决实际问题时，对于较复杂的问题能抽象出问题的数学模型，设计出有效的算法。
在此基础上学习本课程的中级篇：结构上的算法设计（分类、图的高级部分、流），学生通过这部分的学习，了解算法优化的实现途径，很好的解决数据结构中未能解决的问题、最后是本课程的高级篇：NP完全理论、现代优化计算方法简介。
学生通过这部分的学习初步了解计算复杂性理论的基本内容、现代算法的几个主要发展分支，为今后实际应用或者搞理论研究打下一些必备的理论基础。
三、课程基本要求学生必备的先行课是：高等数学、离散数学、程序设计、数据结构。
本课程不能求快，应循序渐进，培养学生浓厚的学习热情和求知欲。
教学中注重和前期课程数据结构的衔接，使学生明白这门课不同于数据结构的是：数据结构是讨论三种基本数据结构上的基本操作的实现，它是完成“如何做”，算法设计与分析这门课强调的是：怎么巧做，做的更好。
在本课程的后期教学中，特别提倡学生广泛阅读参考书、独立思考、结合实际问题展开讨论的教学方式，并以此达到教师精讲、学生宽学的目的。
课程的基本要求是：1．掌握7种常用的算法设计方法，并能综合、灵活的使用这些基本方法，同时用所学到的知识解决一些实际问题；2．掌握算法分析的基本工具、基本技巧、基本方法；3．掌握数据结构中未能详细、深入了解的部分内容（内存分类，图的高级部分、流上的算法）；4．了解计算复杂性理论中的基本内容，包括：机器模型，NP完全、NP难题，近似计算；5．了解现代的计算算法和算法理论的发展趋势走向。
算法复杂度分析算法是计算机科学中解决问题的基本方法，而算法复杂度分析是在评估算法好坏的过程中至关重要的一环。
通过对算法的复杂度进行分析，我们可以了解算法在处理大规模问题时的效率，进而选择最合适的算法来解决我们所面临的具体问题。
一、什么是算法复杂度算法复杂度是指在算法执行过程中所需要的资源（如时间、空间）的度量。
通常我们将算法的复杂度分为时间复杂度和空间复杂度两个方面来进行分析。
1. 时间复杂度时间复杂度描述的是算法在运行过程中所需要的时间资源。
我们可以通过估算算法中基本操作的执行次数来确定其时间复杂度。
在分析时间复杂度时，我们一般关注最坏情况下的执行时间。
常见的时间复杂度有：- 常数时间复杂度：O(1)- 线性时间复杂度：O(n)- 对数时间复杂度：O(log n)- 线性对数时间复杂度：O(n log n)- 平方时间复杂度：O(n^2)- 立方时间复杂度：O(n^3)- 指数时间复杂度：O(2^n)通过对算法中各部分代码运行次数的计算，我们可以得出一个算法的时间复杂度，从而衡量算法的耗时情况。
在实际应用中，我们通常会选择时间复杂度低、效率高的算法来解决问题。
2. 空间复杂度空间复杂度描述的是算法在运行过程中所需要的内存资源。
与时间复杂度类似，我们可以通过估算算法所需的额外空间来确定其空间复杂度。
常见的空间复杂度有：- 常数空间复杂度：O(1)- 线性空间复杂度：O(n)- 平方空间复杂度：O(n^2)- 对数空间复杂度：O(log n)在实际应用中，我们需要尽量节约内存资源，选择空间复杂度较低的算法来提高程序的性能。
二、如何进行算法复杂度分析在进行算法复杂度分析时，我们可以使用以下几种常用的方法：1. 估算法中基本操作的执行次数通过观察算法的代码，我们可以大致估算出每种基本操作的执行次数，进而得出时间复杂度和空间复杂度。
2. 使用大O表示法大O表示法是用来表示算法的上界的一种方法。
在分析时间复杂度时，我们通常只关注算法在处理大规模问题时的表现情况，因此使用大O表示法更为直观和简洁。
算法设计与分析课程教学大纲【适用专业】计算机科学与技术【课时】理论课时：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. 优化搜索策略【教学（实验）内容要点】算法设计与分析实验是算法设计与分析课的一个实践性教学环节。
算法设计与分析——算法复杂性分析这篇博客的内容摘⾃课本，针对课本中缺少的5道证明题，作为练习，给出证明。
算法运⾏时所需要的计算机时间资源的量称为时间复杂性。
这个量应该集中反应算法的效率，并从运⾏该算法的实际计算机中抽象出来。
换句话说，这个量应该是只依赖于要解的问题的规模、算法的输⼊和算法本⾝的函数。
如果分别⽤ N,I和A 表⽰算法要解的问题的规模、算法的输⼊和算法本⾝，⽽且⽤ T 表⽰时间复杂性，那么，应该有 T=T(N,I,A)。
通常 A 隐含在复杂性函数名中，因⽽将 T 简写为 T(N,I) 。
现在，时间复杂性分析的主要问题是如何将复杂性函数具体化，即对于给定的 N,I和A ，如何导出 T(N,I) 的数学表达式，来给出计算T(N,I) 的法则。
根据 T(N,I) 的概念，它应该是算法在⼀台抽象的计算机上运⾏所需要的时间。
设此抽象的计算机所提供的原运算有 k 种，它们分别记为O1,O2,...,Ok 。
⼜设每执⾏⼀次这些元运算所需要的时间分别为 t1,t2,...,tk 。
对于给定的算法 A ，设经统计，⽤到元运算 Oi 的次数为 ei,i=1,2,...,k 。
很清楚，对于每⼀个 i,1≤i≤k,ei 是 N和I 的函数，即 ei=ei(N,I)。
因此有 式中， ti（i=1,2,...,k )，是与 N和I ⽆关的常数。
显然，不可能对规模为 N 的每⼀种合法的输⼊都去统计 ei(N,I),i=1,2,...,k 。
因此 T(N,I) 的表达式还要进⼀步简化，或者说，只能在规模为 N 的某些或某类有代表性的合法输⼊中统计相应的 ei,i=1,2,...,k ，评价其时间复杂性。
通常只考虑三种情况下的时间复杂性，即最坏情况、最好情况和平均情况下的时间复杂性，并分别记为 Tmax(N)、Tmin(N)和Tavg(N) 。
在数学上有 式中， DN 是规模为 N 的合法输⼊的集合； I∗是 DN 中使 T(N,I∗) 达到 Tmax(N) 的合法输⼊；I∼是 DN 中使 T(N,I∼)达到 Tmin(N) 的合法输⼊；⽽ P(I) 是在算法的应⽤中出现输⼊ I 的概率。
第一章算法概述1、算法的五个性质：有穷性、确定性、能行性、输入、输出。
2、算法的复杂性取决于：(1)求解问题的规模(N) , (2)具体的输入数据(I),( 3)算法本身的设计(A)，C=F(N,I,A。
3、算法的时间复杂度的上界，下界，同阶，低阶的表示。
4、常用算法的设计技术：分治法、动态规划法、贪心法、回溯法和分支界限法。
5、常用的几种数据结构：线性表、树、图。
第二章递归与分治1、递归算法的思想：将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。
递归的时间复杂性可归结为递归方程：1 11= 1T(n) <aT(n—b) + D(n) n> 1其中，a是子问题的个数，b是递减的步长，~表示递减方式，D(n)是合成子问题的开销。
递归元的递减方式~有两种：1、减法，即n -b，的形式。
2、除法，即n / b，的形式。
2、D(n)为常数c：这时，T(n) = 0(n P)。
D(n)为线形函数cn：r O(n) 当a. < b(NT(n) = < Ofnlog^n) "n = blljI O(I1P)二"A bl吋其中.p = log b a oD(n)为幕函数n x：r O(n x) 当a< D(b)II JT{ii) = O(ni1og b n) 'ia = D(b)ll].O(nr)D(b)lHJI：中，p= log b ao考虑下列递归方程：T(1) = 1⑴ T( n) = 4T(n/2) +n⑵ T(n) = 4T(n/2)+n2⑶ T(n) = 4T(n/2)+n3解：方程中均为a = 4，b = 2，其齐次解为n2。
对⑴，T a > b (D(n) = n) /• T(n) = 0(n);对⑵，•/ a = b2 (D(n) = n2) T(n) = O(n2iog n);对⑶，•/ a < b3(D(n) = n3) - T(n) = 0(n3)；证明一个算法的正确性需要证明两点：1、算法的部分正确性。
