第1章_算法在计算中的作用讲解材料.pptx

1. 算法在计算机中的作用 指导思想解决问题的方法学习、不是数据结构学习：如何解决问题算法分析是重点，知道方法比较容易，分析该方法的复杂度、优缺点才是重要基本的算法及其分析方法讲全，高级设计与分析技术都讲授，而算法研究的问题非常多，因此选择主题讲授数据结构、包括高级数据结构不是本课程的讲授内容课程教材以MIT的算法导论为基本教材，可参考： 《计算机算法导论》、卢开澄、清华 《Introduction to Algorithms, A Creative Approach》、Ubi Manber （算法大师） 《Algorithms Design Techniques and Analysis》、沙特（强调分 析） 《Programming Pearls》（编程珠玑I和II）对算法课的看法核心是分析算法复杂性的方法 第一部分是核心 基础算法（应用最广泛）+分析（最重要）解决问题的思路是关键 第二部分 方法+分析+应用算法无止境 第三部分是提升（数学很重要）算法的应用： 论文增色 如何在各个方向应用则是重点，算法本身的研究不是目的。 实际应用当中需要考虑 计算机系统的结构 内存访问 读写操作等等 实用的才是最好的三大部分都将提供部分必威体育精装版研究成果或者相应应用的paper，课后学习和阅读。 算法的概念 算法是求解某个问题的长度有限的指令序列，每条指令 都是确定的、简单的、机械的和可执行的。 “求解数学问题（如寻找最大公约数）的一个过程，该过 程步骤有限，通常还涉及重复的操作。”—维基百科求解某一具体问题的数学过程 收敛算法 迭代算法对于任一属于这个问题的实例的有效输入，应在有限步（一步执行一条指令）内给出结果（输出），并中止。形象的算法例子DEMO视频 问题：抽象描述；实例：问题的具体化；【例1】多项式计算问题：给定多项式 p( x) ? an xn ? an?1 xn?1 ? ? ? a1 x和x 求p(x)的值p( x) ? 3x ? 2x ? 1; x ? 42实例： 人类基因：10万种基因；30亿种化学基对 排序和比对 快速地访问和检索因特网上的信息 数据传输路径寻找； 有哪些信誉好的足球投注网站引擎检索技术； 电子商务领域的信息安全 公共密钥加密技术 数字签名技术 规划（动态、线性） 石油公司确定该在何处打井？ 总统选举确定宣传基金花在何处？ 航空公司的机组人员调配？ 因特网服务提供商确定服务器安置位置？ 算法需要考虑的问题 排序算法要考虑的因素： 待排序的数据项数 数据项已经排好序的程度 对数据项取值的可能相知 打算采用的存储设备的类型 内存 磁盘 磁带 对多项式计算： 变元个数、次幂、系数范围等等算法的正确性如果一个算法对其每一个输入实例，都能输出正确的结果并停止，则称它是正确的。正确的算法解决了给定的计算问题不正确的算法： 可能不会停止 或者给出的结果不正确不正确的算法不是都没用 近似 模拟可计算性从理论上判断什么问题可以给出算法利用计算机求解，什么问题不可以，属于“可计算性理论”研究的问题。比如：“停机问题”就是不可计算的。可计算理论认为可计算的问题，都有求解的算法，这样的算法不是唯一的（有无限多个），它们的计算复杂性也不一样。复杂性较小的才是实际可计算的。算法概念的总结 算法是求解某个问题的长度有限的指令序 列，每条指令都是确定的、简单的、机械 的、可执行的。 算法给出了某一实际问题的计算/处理过程 对算法的研究 算法设计 算法复杂度分析 单个算法的复杂性 算法复杂性比较：效率 更近一步：算法的使用场景算法的复杂性评价一个算法可以从不同方面来考虑，如正确性，简单性，时间复杂性，空间复杂性，还可以提出求解某问题的最优算法这样的问题。我们将着重讨论时间复杂性，并且是从数学的角度来讨论，而不从具体的机器、语言、编程技巧来看。时间复杂性将归结为某些基本操作的次数问题，基本操作的次数与问题的规模有关。那么如何确定问题的规模？一般我们考虑对基本操作的次数影响最大的量。算法效率求解同一个问题可以有不同的算法，效率或复杂性也可能不同。多项式值计算的基本操作——乘法两个已排好序的数据合并；算法效率比较：排序法比较：插入排序和合并排序设进行长度为n的数组的排序方法1：多项式：则：f (n) ? f (n ? 1) ? 2, ? 2nf (1) ? 2 方法2：多项式：则：f (n) ? f (n ? 1) ? 1, ? nf (1) ? 11. y ← 12. p ← a03. 对i从1到n做4． y ← xy5.p ← ai y + p6. 输出p 乘法：2n次 加法：n次 1. p ← an 2. 对i从n到1做 3．p ← px + ai ?1 4. 输出p 乘法：n次 加法：n次算法1算法2 算法分析即指对一个算法所需要的资源进行 预测； 资源：