算法设计与分析ch1.ppt

《算法设计与分析ch1.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Chapter1.Introduction1.1RoleofAlgorithmsinComputerScience算法是计算机科学的主题计算机科学体系与算法设计与分析的地位算法设计与分析的意义70年代前计算机科学基础的主题没有被清楚地认清。70年代Knuth出版了《TheArtofComputerProgramming》以算法研究为主线确立了算法为计算机科学基础的重要主题1974年获得图灵奖。70年代后算法作为计算机科学核心推动了计算机科学技术飞速发展算法是计算机科学基础的重要主题解决一个计算问题的过程计算机科学的体系可计算否能行可计算否软件系统用计算机语言实现算法算法

2、设计与分析可计算理论计算模型可计算问题/不可计算问题计算模型的等价性--图灵/Church命题计算复杂性理论在给定的计算模型下研究问题的复杂性固有复杂性上界下界平均复杂性问题的分类:P=NP?抽象复杂性研究算法设计和分析可计算问题的算法的设计与分析设计算法的理论、方法和技术分析算法的理论、方法和技术计算机软件系统软件工具软件应用软件1.2ConceptsofAlgorithms算法的定义问题的定义算法的实例定义1.2.1(计算)可由一个给定计算模型机械地执行的规则或计算步骤序列称为该计算模型的一个计算注意一个计算机程序是一个计算（计算模型是计算机）计算可能永远不停止——不

3、是算法算法的定义定义1.2.2(算法)算法是一个满足下列条件的计算：有穷性/终止性：有限步内必须停止，确定性：每一步都是严格定义和确定的动作，能行性：每一个动作都能够被精确地机械执行，输入：有一个满足给定约束条件的输入，输出：满足给定约束条件的结果。最早的算法是欧几里德的“求最大公因子算法”直观地说，算法如下图所示：算法的目的是求解问题。什么是问题？定义1.2.3(问题)设Input和Output是两个集合。一个问题是一个关系RInputOutput，Input称为问题R的输入集合，Input的每个元素称为R的一个输入，Output称为问题R的输出或结果集合，Outp

4、ut的每个元素称为R的一个结果。注意问题定义了输入和输出的关系。问题的定义例：SORT问题定义如下：输入集合Input={

5、ai是整数}输出集合Output={

6、bi是整数,b1….bn}问题SORT={(,)

7、Input,Output,{a1,…,an}={b1,…,bn}}定义1.2.4(问题实例)问题P的一个实例是P的一个二元组。注意一个算法面向一个问题，而不是仅求解一个问题的一个或几个实例。问题定义Input=ai是整数

8、output=bi是整数,且b1...bnR=(,)Input,output,a1,...,an=b1,...,bn}算法的思想—扑克牌游戏算法示例A1,......,n=5,2,4,6,1,3A1,......,n=5,2,4,6,1,3A1,......,n=2,5,4,6,1,3A1,......,n=2,4,5,6,1,3A1,......,n=2,4,5,6,1,3A1,......,n=1,2,4,5

9、,6,3A1,......,n=1,2,3,4,5,6算法描述Insertion-sort(A)Input:A1,.....,n=n个数output:A1,.....,n=n个sorted数FORj=2TonDokeyAj;ij-1WHILEi>0ANDAi>keyDoAi+1Ai;ii-1;Ai+1key;实例：A1,......,n=5,2,4,6,1,31.3AnalyzingAlgorithms算法的正确性分析算法的复杂性分析定义1.3.1(算法正确性)一个算法是正确的，如果它对于每一个输入都最终停止,而且产生正确的输

10、出。不正确算法：①不停止(在某个输入上)②对所有输入都停止，但对某输入产生不正确结果近似算法①对所有输入都停止②产生近似正确的解或产生不多的不正确解算法的正确性分析算法正确性证明证明算法对所有输入都停止证明对每个输入都产生正确结果调试程序程序正确性证明:程序调试只能证明程序有错，不能证明程序无错误!目的：预测算法对不同输入所需资源量复杂性测度：时间，空间，I/O等,是输入大小的函数用途：为求解一个问题选择最佳算法、最佳设备需要的数学基础离散数学，组合数学，概率论，代数等需要的数学能力建立算法复杂性的数学模型数学模型化简算法的