《算法设计与分析40学时课件ch1new》由会员分享，可在线阅读，更多相关《算法设计与分析40学时课件ch1new（27页珍藏版）》请在金锄头文库上搜索。
1、第一章 引 言,骆吉洲 计算机科学与工程系,1.1 Role of Algorithms in Computer Science,算法是计算机科学的主题 计算机科学体系与算法设计与分析的地位 算法设计与分析的意义,70年代前 计算机科学基础的主题没有被清楚地认清。 70年代 Knuth出版了The Art of Computer Programming 以算法研究为主线 确立了算法为计算机科学基础的重要主题 1974年获得图灵奖。 70年代后 算法作为计算机科学核心推动了计算机科学技术 飞速发展,算法是计算机科学基础的重要主题,解决一个计算问题的过程,计算机科学的体系,可计算否,可计算理论 计
2、算模型 可计算问题/不可计算问题 计算模型的等价性-图灵/Church命题 计算复杂性理论 在给定的计算模型下研究问题的复杂性 固有复杂性 上界 下界 平均 复杂性问题的分类: P=NP? 抽象复杂性研究,算法设计和分析 可计算问题的算法的设计与分析 设计算法的理论、方法和技术 分析算法的理论、方法和技术 计算机软件 系统软件 工具软件 应用软件,1.2 Concepts of Algorithms,算法的定义 问题的定义 算法的实例,定义1.2.1(计算) 可由一个给定计算模型机械地执行的规则或计算步骤序列称为该计算模型的一个计算 注意 一个计算机程序是一个计算（计算模型是计算机） 计算可能
3、永远不停止不是算法,算法的定义, DB-LAB (2003),定义1.2.2 (算法) 算法是一个满足下列条件的计算： 有穷性/终止性：有限步内必须停止， 确定性：每一步都是严格定义和确定的动作， 能行性：每一个动作都能够被精确地机械执行， 输入：有一个满足给定约束条件的输入， 输出：满足给定约束条件的结果。 最早的算法是欧几里德的“求最大公因子算法” 直观地说，算法如下图所示： 算法的目的是求解问题。什么是问题？,定义1.2.3 (问题) 设Input和Output是两个集合。一个问题是一个关系RInputOutput，Input称为问题R的输入集合，Input的每个元素称为R的一个输入，O
4、utput称为问题R的输出或结果集合，Output的每个元素称为R的一个结果。 注意 问题定义了输入和输出的关系。,问题的定义,例：SORT问题定义如下： 输入集合Input=|ai是整数 输出集合Output=|bi是整数, b1.bn 问题SORT=(,)|Input, Output,a1, , an=b1, , bn 定义1.2.4(问题实例) 问题P的一个实例是P的一个二元组 注意 一个算法面向一个问题，而不是仅求解一个问题的一个或 几个实例,问题定义 Input= ai是整数 output= bi是整数,且b1.bn R=(,)Input, output,a1,.,an= b1,.,
5、bn 算法的思想扑克牌游戏,算法示例,A1,n = 5,2,4,6,1,3 A1,n = 5,2,4,6,1,3 A1,n = 2,5,4,6,1,3 A1,n = 2,4,5,6,1,3 A1,n = 2,4,5,6,1,3 A1,n = 1,2,4,5,6,3 A1,n = 1,2,3,4,5,6,算法描述 Insertion-sort(A) Input: A1,.,n=n个数 output: A1,.,n=n个sorted数 1. FOR j=2 To n Do 2. keyAj; 3. ij-1 4. WHILE i0 AND Aikey Do 5. Ai+1Ai; 6. ii-1;
6、7. Ai+1key; 实例：A1,n=5,2,4,6,1,3,1.3 Analyzing Algorithms,算法的正确性分析 算法的复杂性分析,定义1.3.1(算法正确性) 一个算法是正确的，如果它对于每一个输入都最终停,而且产生正确的输出。 不正确算法： 不停止(在某个输入上) 对所有输入都停止，但对某输入产生不正确结果 近似算法 对所有输入都停止 产生近似正确的解或产生不多的不正确解,算法的正确性分析,算法正确性证明 证明算法对所有输入都停止 证明对每个输入都产生正确结果 调试程序程序正确性证明: 程序调试只能证明程序有错， 不能证明程序无错误!,循环不变量方法 证明主要结构是循环结
7、构的算法的正确性,循环不变量：数据或数据结构的关键性质 依赖于具体的算法和算法特点 初始 ：循环开始前循环不变量成立 循环步骤：循环体每执行一次,循环不变量成立 终止 ：算法结束后，循环不变量保证算法正确,循环不变量方法实例,Insertion-sort(A) 1. FOR j=2 To n Do 2. keyAj; 3. ij-1 4. WHILE i0 AND Aikey Do 5. Ai+1Ai; 6. ii-1; 7. Ai+1key;,循环不变量：循环变量为j但循环体未执行前， A1,2,.,j-1来自输入且有序,初始 j=2: A1来自输入且有序,循环 : 设A1,.,j-1来自输
8、入且有序 循环体执行一遍，A1,.,j-1,j来自输入且有序,终止j=n+1: A1,2,.,n来自输入且有序,目的 预测算法对不同输入所需资源量 复杂性测度 时间，空间， I/O等, 是输入大小的函数 用途 为求解一个问题选择最佳算法、最佳设备 需要的数学基础 离散数学，组合数学，概率论，代数等 需要的数学能力 建立算法复杂性的数学模型 数学模型化简,算法的复杂性分析,定义1.3.2 (输入的大小) 设Input是问题R的输入集合，R的输入大小是一个函数 F：InputN，N是正整数集合 示例 矩阵问题的输入大小=矩阵的维数 图论问题的输入大小=图的边数/结点数,定义1.3.3（时间复杂性）
9、 一个算法对特定输入的时间复杂性是该算法对该输入产生结果需要的原子操作或“步”数 注意 时间复杂性是输入大小的函数 我们假设每一步的执行需要常数时间，实际上每步需要的时间量可能不同,定义1.3.4（空间复杂性） 一个算法对特定输入的空间复杂性是该算法对该输入产生结果所需要的存储空间大小, DB-LAB (2003),定义1.3.5（最坏复杂性） 设Input是问题R的输入集合，Complexity(X)是求解R 的算法A的复杂性函数，Size(y)是确定R中输入大小的 函数，A的最坏复杂性是 MaxComplexity(size(y)yInput 定义1.3.5（最小复杂性） MinCompl
10、exity(size(y)yInput 定义1.3.6 （平均复杂性） 设yInput,y作为算法A的输入出现的概率是py，A的 平均复杂性为,1.4 Designing Algorithms,算法的设计方法 算法的分析方法,Divide-and-Conquer Dynamic Programming Greedy Algorithms Approximation Algorithms Randomlized Algorithms Tree Searching Strategies Prune-and-Search On-Line Algorithms Genetic Algorithms Parellel Algorithms,算法的设计方法,不同的设计方法有不同的分析方法,算法的分析方法,
