第1章_算法在计算中的作用_算法分析与设计_杭电_褚一平

1、1. 算法在计算机中的作用指导思想解决问题的方法学习、不是数据结构学习：如何解决问题算法分析是重点，知道方法比较容易，分析该方法的复杂度、优缺点才是重要基本的算法及其分析方法讲全，高级设计与分析技术都讲授，而算法研究的问题非常多，因此选择主题讲授数据结构、包括高级数据结构不是本课程的讲授内容课程教材以MIT的算法导论为基本教材，可参考：计算机算法导论、卢开澄、清华Introduction to Algorithms, A Creative Approach、Ubi Manber（算法大师）Algorithms Design Techniques and Analysis、沙特（强调分析）Pro

2、gramming Pearls（编程珠玑I和II）对算法课的看法核心是分析算法复杂性的方法第一部分是核心 基础算法（应用最广泛）+分析（最重要）解决问题的思路是关键第二部分 方法+分析+应用算法无止境第三部分是提升（数学很重要）算法的应用：论文增色如何在各个方向应用则是重点，算法本身的研究不是目的。实际应用当中需要考虑计算机系统的结构内存访问读写操作等等实用的才是最好的三大部分都将提供部分最新研究成果或者相应应用的paper，课后学习和阅读。算法的概念算法是求解某个问题的长度有限的指令序列，每条指令都是确定的、简单的、机械的和可执行的。“求解数学问题（如寻找最大公约数）的一个过程，该过程步骤有

3、限，通常还涉及重复的操作。”维基百科求解某一具体问题的数学过程收敛算法迭代算法对于任一属于这个问题的实例的有效输入，应在有限步（一步执行一条指令）内给出结果（输出），并中止。形象的算法例子DEMO视频p( x) 3x 2x 1; x 4实例：2问题：抽象描述；实例：问题的具体化；【例1】多项式计算问题：给定多项式 p( x) an xn an1 xn1 a1 x和x求p(x)的值人类基因：10万种基因；30亿种化学基对排序和比对快速地访问和检索因特网上的信息数据传输路径寻找；搜索引擎检索技术；电子商务领域的信息安全公共密钥加密技术数字签名技术规划（动态、线性）石油公司确定该在何处打井？总统选举

4、确定宣传基金花在何处？航空公司的机组人员调配？因特网服务提供商确定服务器安置位置？交通图中任何两个交叉点之间的最短路径：最短路径n个矩阵相乘:动态规划A*x=b (mod n); a,b,n为整数：数论平面上n个点的凸壳：计算几何共同特征：有很多解决方案-算法分析：复杂性有着实际的应用算法需要考虑的问题排序算法要考虑的因素：待排序的数据项数数据项已经排好序的程度对数据项取值的可能相知打算采用的存储设备的类型内存磁盘磁带对多项式计算：变元个数、次幂、系数范围等等算法的正确性如果一个算法对其每一个输入实例，都能输出正确的结果并停止，则称它是正确的。正确的算法解决了给定的计算问题不正确的算法：可能不

5、会停止或者给出的结果不正确不正确的算法不是都没用近似模拟可计算性从理论上判断什么问题可以给出算法利用计算机求解，什么问题不可以，属于“可计算性理论”研究的问题。比如：“停机问题”就是不可计算的。可计算理论认为可计算的问题，都有求解的算法，这样的算法不是唯一的（有无限多个），它们的计算复杂性也不一样。复杂性较小的才是实际可计算的。算法概念的总结算法是求解某个问题的长度有限的指令序列，每条指令都是确定的、简单的、机械的、可执行的。算法给出了某一实际问题的计算/处理过程对算法的研究算法设计算法复杂度分析单个算法的复杂性算法复杂性比较：效率更近一步：算法的使用场景算法的复杂性评价一个算法可以从不同方面

6、来考虑，如正确性，简单性，时间复杂性，空间复杂性，还可以提出求解某问题的最优算法这样的问题。我们将着重讨论时间复杂性，并且是从数学的角度来讨论，而不从具体的机器、语言、编程技巧来看。时间复杂性将归结为某些基本操作的次数问题，基本操作的次数与问题的规模有关。那么如何确定问题的规模？一般我们考虑对基本操作的次数影响最大的量。算法效率求解同一个问题可以有不同的算法，效率或复杂性也可能不同。多项式值计算的基本操作乘法两个已排好序的数据合并；算法效率比较：排序法比较：插入排序和合并排序设进行长度为n的数组的排序则：f (1) 2f (n) f (n 1) 2, 2n方法1：多项式：1110111101(

7、 )()nnnnnnnnnp xa xaxa xaa xxaxa xa 次则：f (n) f (n 1) 1, nf (1) 1方法2：多项式：1110121101( )()nnnnnnnnnp xa xaxa xaa xaxaxa 次算法1算法21. y 12. p a03. 对i从1到n做4 y xy5. p ai y + p6. 输出p乘法：2n次加法：n次1. p an2. 对i从n到1做3p px + ai 14. 输出p乘法：n次加法：n次算法分析即指对一个算法所需要的资源进行预测；资源：内存、通信带宽或计算机硬件，但通常，资源是指我们希望测度的计算时间；对于一个问题，通过分析几种

8、候选算法，选出一个最有效地算法；分析的结果可能是找出不止一个的候选算法，但在这一过程中，通常都要去掉几个较差的算法；算法分析模型20世纪30年代：问题的可解和不可解计算模型-建立算法求解问题（可解）计算模型：哥德尔(Godel)的递归函数丘齐(Church)的伽马演算波斯特(Post)的波斯特机图灵(Turing) 的图灵机RAM模型丘齐：所有这些模型是等效的（可解层次）算法分析的模型：RAM模型分析一个算法之前，要建立有关实现技术的模型；包括描述所用资源及代价的模型单处理器、随即存取（Random AccessMachine, RAM）计算模型指令一条接一条执行，没有并发操作常见指令：算术指

9、令（加、减、乘、除、取余、向上和向下取整）数据移动指令（装入、存储、复制）控制指令（条件和非条件转移、子程序调用和返回指令）RAM模型数据类型有整数类型和浮点实数类型一般不关心数据的精度问题一些应用中，精度是非常关键的存储层次建模：高速缓存和虚拟内存RAM模型分析算法需要：组合、代数、数论、概率等简单明了的公式形式来总结分析的结果和行为“几乎所有”的问题都是不可解的：被计算的函数集是不可数的（非负整数-实数）任何算法可对应一个唯一的正整数，是可数的；Pi中是否存在连续的7个“1”？多个变元的多形式方程是否存在整数解？问题的可判定性和可解性属于可计算性理论。计算机出现的时候：满足于一个简单的程序能够在它需要的时间内求解一个特定的问题；之后：提出了对尽可能少使用资源的有效算法的需求；资源的有限性开发复杂算法计算复杂性：可解类问题的效