算法设计与分析讲义chapter1

《算法设计与分析讲义chapter1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter1Introduction1.1RoleofAlgorithmsinComputerScience(1)算法是计算机科学基础的重要主题·70年代前，计算机科学基础的主题没有被清楚地认清。·70年代，Knuth出版了《TheArtofComputerProgramming》(三卷）,以各种算法研究为主线，确立了算法为计算机科学基础的重要主题，1974年获得图灵奖。·70年代后，算法作为计算机科学的核心推动了计算机科学技术的飞速发展(2)计算机科学的体系·解决一个计算问题的过程可计算否→能行可计算否→算法

2、设计与分析→用计算机语言实现算法→软件系统·可计算理论:·计算模型·可计算问题/不可计算问题·计算模型的等价性--图灵/Church命题·计算复杂性理论·在给定的计算模型下研究问题的复杂性·上界·下界·平均·固有复杂性·复杂性问题的非类:P=NP?·抽象复杂性研究·算法设计和分析·可计算问题的算法的设计与分析·设计算法的理论、方法和技术·分析算法的理论、方法和技术(3)算法设计与分析的意义·计算机各领域的核心·计算机工程特别是计算机软件工程的基础51.2ConceptsofAlgorithms(1)算法的定义定义1

3、.2.1(计算).可由一个给定计算模型机械地执行的规则或计算步骤序列称为该计算模型的一个计算。*一个计算机程序是一个计算（计算模型是该计算机）*计算可能永远不停止--不是算法。定义1.2.2(算法).算法是一个满足下列条件的计算：①有穷性/终止性：有限步内必须停止。/*好算法/坏算法*/②确定性：每一步都是严格定义和确定的动作。/*要严格算法语言*/③能行性：每一个动作都能够被精确地机械执行。④输入：有一个满足给定约束条件的输入。⑤输出：满足给定约束条件的结果。*直观地说，算法如下图所示：*算法的目的是求解问题。什

4、么是问题？(2)问题的定义定义1.2.3(问题).设Input和Output是两个集合。一个问题是一个关系RÍInput´Output，Input称为问题R的输入集合，Input的每个元素称为R的一个输入，Output称为问题R的输出或结果集合，Output的每个元素称为R的一个结果。*问题定义了输入和输出的关系。例.SORT问题定义如下：输入集合Input={

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

6、bi是整数,b1£b2£…£bn}问题SORT={（

7、>，）

8、ÎInput,ÎOutput,{a1,…,an}={b1,…,bn}}.定义1.2.4(问题实例).问题R的一个实例是的一个二元组。*一个算法面向一个问题，而不是仅仅求解一个问题的实例。5(3)算法实例—InsertimSort·问题定义Input={

9、ai是整数}output={

10、bi是整数,且b1£b2£...£bn}R={(,)½

11、an>ÎInput,Îoutput,{a1,...,an}={b1,...,bn}·算法的思想—扑克牌游戏·算法描述Insertion-sort(A)Input:A[1,.....,n]=n个sort数output:A[1,.....,n]=n个sort数Method:FORi=2TonDokey¬A[i],i¬j-1WHILEi>0ANDA[i]>keyDoA[i+1]¬[i];i¬i-1;A[i+1]¬key;·实例：A[1,......,n]=5,2,4,6,1,31.3Analyzin

12、gAlgorithms(1)正确性分析定义1.3.1.一个算法是正确的，如果它对于每一个输入都最终停止,而且产生正确的输长*不正确：①不停止(在某个输入上)②对所有输入都停止，但对某个输入产生不正确的结果*近似算法①对所有输入都停止②产生近似正确的解或产生不多的不正确解*正确性证明·证明算法对所有输入都停止·证明对每个输入都产生正确结果*调试程序¹程序正确性证明“程序调试只能证明程序有错误，不能证明程序无错误”5(2)复杂性分析目的：预测算法对不同输入所需要的资源量—是输入大小的函数复杂性测度：时间，空间，I/O等

13、等用途：为求解一个问题选择最佳算法需要的数学基础：离散数学，组合数学，概率论，代数等需要的数学能力：·建立算法复杂性的数学模型·数学模型化简定义1.3.2(输入的大小)设Input是问题R的输入集合，R的输入大小是一个函数。F：Input®N，N是正整数集合例：矩阵问题的输入大小=矩阵的维数图论问题的输入大小=图的边数/结点数定义1.3.3（时间复杂性）一个