第一章算法复杂性

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,算法设计与分析,高尚,1,关于本课程,课程目的：计算机算法设计与分析导引,不是一门试验或程序设计课程,也不是一门数学课程,参考教材：计算机算法设计与分析-王晓东,前导课：数据结构+程序设计,授课形式：作业+实验,+,笔试,2,第1章 算法复杂性,本章主要知识点：,1.1 引言,1.2 算法复杂性的测度,3,1.1引言,算法（,algorithms,）的研究是计算机科学的核心课题之一。早在计算机问世以前，就有人开创了算法的研究，并创建了许多有效的算法。,欧几里德算法（求两数的最大公因子）,孙子算法（求若干个数的最小公倍数）,快速富里叶变换（,FFT,）算法（,60,年代后半期）,并行算法（,70,年代）,据不完全统计，,50,年代以前约占文献总量,10%,；产生,60,年代的约占文献总量的,30%,；产生于,70,年代（,76,年前）约占文献总量,60%,。,4,目前，算法的研究仍方兴未艾，它所涉及的范围十分广泛。不论是从事计算机硬件设计（如计算机部件设计、系统设计和网络设计等），还是从事计算机软件设计（如设计系统软件和各种应用软件），都需要认真研究算法。计算机程序的核心则是计算机算法，如果不发明更有效的算法，就不可能开发出更新更先进的软件。,5,一年一度的计算机科学领域最高荣誉,计算图灵奖（,Turing Awards,），被誉为计算机科学领域的“诺贝尔奖”，从,1966,年至,1999,年，约有,12,人是由于在算法与数据结构、计算复杂性理论、程序设计等获图灵奖，比如,1984,年图灵设计得主瑞士的,NWirth,教授提出“算法,+,数据结构,=,程序”著名公式。,1980,年授予在程序设计和算法方面，因发明,Quick Sort,算法的英国,Hoare,教授。,6,阿兰,麦席森,图灵（,Alan,Mathison,Turing,，,1912.6.231954.6.7,），是,英国,著名的数学家和逻辑学家，被称为计算机科学之父、,人工智能,之父，是计算机逻辑的奠基者，提出了“,图灵机,”和“,图灵测试,”等重要概念。人们为纪念其在计算机领域的卓越贡献而设立“,图灵奖,”。,7,提出“图灵机”概念,提出“图灵测试”概念,开创非线性力学,破解德国密码系统,Enigma,8,图灵试验,由计算机、被测试的人和主持试验人组成。计算机和被测试的人分别在两个不同的房间里。测试过程由主持人提问，由计算机和被测试的人分别做出回答。观测者能通过电传打字机与机器和人联系（避免要求机器模拟人外貌和声音）。被测人在回答问题时尽可能表明他是一个“真正的”人，而计算机也将尽可能逼真的模仿人的思维方式和思维过程。如果试验主持人听取他们各自的答案后，分辨不清哪个是人回答的，哪个是机器回答的，则可以认为该计算机具有了智能。这个试验可能会得到大部分人的认可，但是却不能使所有的哲学家感到满意。,9,图灵图灵享年,42,岁，科学家为了纪念他，,1966,年美国计算机协会设立了“图灵奖”成为计算机科学家的最高奖项。后来一位加利福尼亚的小伙子为了纪念图灵，开办了一家公司，而公司的,Logo,就是图灵死时手里拿着的被咬过一口的苹果，这家公司就是现在很出名的苹果公司，而那个小伙子则是苹果的第一任,CEO,乔布斯,.,10,2009 Charles Thacker,获奖原因,对第一台现代个人计算机,Xerox PARC Alto,的先驱性设计与实现，还有在局域网（包括以太网）、多处理器工作站、窥探高速缓存一致性协议和平板,PC,等方面的重大发明和贡献,.,2008 Barbara,Liskov,获奖原因,在计算机程序语言设计方面的开创性工作。她的贡献是让计算机软 件更加可靠、安全和更具一致性。美国第一个获得计算机科学博士学位的女性（,1968,年，斯坦福大学），其创新性研究给计算机编程领域带来了巨大变革,.,她是第二位授予图灵奖的女性,.,2007 Edmund M.Clarke,、,Allen Emerson,和,Joseph,Sifakis,获奖原因,在将模型检查发展为被硬件和软件业中所广泛采纳的高效验证技术上的贡献。而,DDJ,则将三人的贡献称为“在发现计算机硬件和软件中设计错误的自动化方法方面的工作”。,11,2000 Andrew Chi-,Chih,Yao,(,姚期智,),获奖原因：由于在计算理论方面的贡献而获奖，包括伪随机数的生成算法、加密算法和通讯复杂性。,1984,Niklaus,Wirth,获奖原因：由于开发了,EULER,、,ALGOL-W,、,MODULA,和,PASCAL,一系列崭新的计算语言。,算法十数据结构,=,程序,（,Algorithms,Data Structures,Programs),12,1980 C.,Antony,R.Hoare,获奖原因：由于在编程语言的定义和设计方面的基础性贡献。,Quicksort,算法之父查尔斯,霍尔,1974 Donald E.Knuth,获奖原因：由于在算法分析和程序语言设计方面的重要贡献，计算机程序设计艺术的作者。算法大师,Donald E.Knuth,的,计算机程序设计艺术,是一部鸿篇巨著。原计划要出七册，但目前只完成了三册。他还有个中文名字：“高德纳”。,数据结构和编译原理的,KMP,算法和,LR(K),算法,13,2006 Fran Allen,获奖原因：对于优化编译器技术的理论和实践做出的先驱性贡献，这些技术为现代优化编译器和自动并行执行打下了基础。第一位女性图灵奖得主。,14,约翰,冯,诺依曼（,John Von Neumann,，,1903,1957,），美藉匈牙利人，,1903,年,12,月,28,日，在布达佩斯诞生了一位神童，这不仅给这个家庭带来了巨大的喜悦，也值得整个计算机界去纪念。正是他，开创了现代计算机理论，其体系结构沿用至今，而且他早在,40,年代就已预见到计算机建模和仿真技术对当代计算机将产生的意义深远的影响。他，就是约翰,冯,诺依曼（,John Von Neumann,）。,15,1933,年，冯,诺依曼解决了,希尔伯特,第,5,问题，即证明了局部欧几里得紧群是,李群,1934,年他又把紧群理论与波尔的殆周期函数理论统一起来他还对一般拓扑群的结构有深刻的认识，弄清了它的代数结构和,拓扑,结构与,实数,是一致的 他对算子代数进行了开创性工作，并奠定了它的理论基础，从而建立了算子代数这门新的数学分支这个分支在当代的有关数学文献中均称为冯,诺依曼代数这是有限维空间中矩阵代数的自然推广,16,冯,诺依曼还创立了,博弈论,这一现代数学的又一重要分支,1944,年发表了奠基性的重要论文,博弈论与经济行为,论文中包含博弈论的纯粹数学形式的阐述以及对于实际博弈应用的详细说明文中还包含了诸如统计理论等教学思想冯,诺依曼在,格论,、连续几何、,理论物理,、,动力学,、,连续介质力学,、气象计算、,原子能,和经济学等领域都作过重要的工作,冯,诺依曼对人类的最大贡献是对,计算机科学,、,计算机技术,和,数值分析,的开拓性工作,17,1.1引言,算法：是满足下述性质的指令序列。,有穷性,:,一个算法在执行有穷个计算步骤后必须终止。,确定性,:,一个算法中给出的每一个计算步，必须是精确地定义的、无二义性的。,能行性,:,算法中要执行每一计算步都是可以在有限时间内做完的。能行性、有穷性和确定性是相容的。,输入,:,一个算法一般都要求,0,个或多个输入信息，这些输入量是算法所需的初始数据，它们取自某一特定的集合。,输出,:,一个算法一般有一个或多个输出信息。被解释为“对输入的计算结果”。程序：,18,凡是一个算法，都必须满足以上五个特征，只满足后四条特征的一组规则，不能称作算法，叫做计算过程。操作系统就是计算过程的一个重要例子。设计操作系统的目的是为了控制作业的运行，当没有作业可用时，这一计算过程并不终止，而是处于等待状态，一直等到一个新的作业进入。,19,例如，求给定两个整数,m,和,n,的最大公因子，这个问题通常用“辗转相除法”求解。西方称为欧几里得（,Euclid,）算法，我国数学家秦九韶在,数书九章,中记载了这个方法。,Euclid,算法如下：,（,1,）输入,m,，,n,（,mn,）；,（,2,）以,n,除,m,，,r=MOD,（,m,，,n,），,r,为余数；,（,3,）若,r=o,，输出,n,的当前值，算法结束；否则执行第（,4,）步；,（,4,）,mn,，,nr,，转入（,2,）。,20,21,例,m=36,，,n=28,r=8,r0 m=28 n=8,r=4,r0 m=8 n=4,r=0,输出最大公因子为,4,22,算法与过程的区别：,算法要在有限的时间内通过有穷步计算后终止；过程则可以是有穷的，也可以是无穷的，无穷的过程永远不会终止。,算法与程序的区别：,程序往往是指用某种机器语言书写的一个计算过程；但一个特定的算法不一定表现为一个计算机程序。,一个算法可以采用多种方式描述，如图解描述、语言描述等，如果语言描述一算法，既可用人类的自然语言描述，也可以用各种计算机语言描述，这时表现为程序。也就说程序是算法描述的其中一种方法。我们最感兴趣的还是用计算机语言来描述和在计算机上执行各种算法。,一个计算机程序一般只能在某些机器上执行；而一个算法，既可以编成程序在各种计算机上执行，也可以用纸、笔手工执行，甚至可以用算盘，算筹或其它工具执行。,23,二、算法设计和算法分析的步骤,1,、问题的陈述,准确地陈述问题是解决问题的第一步。为了设计求解某一问题的算法，首先必须了解问题的实质。即已知条件是什么？要求回答是什么？一个问题的正确描述应当使用科学的语言把所有已知条件和需要的答案陈述清楚。,24,2,、模型的选择或拟制,当问题陈述清楚后，选择或拟制描述问题的数学模型是非常重要的工作。模型适当与否影响算法设计的速度和算法的效率。模型选择无公式可循，取决于设计者的知识结构、工作经验等。设计者应当十分重视模型的选择，宁可多下功夫来选择或拟制一个适合当前问题的数学模型，才能为后续工作的顺利开展铺平道路。,25,3,、算法设计和正确性证明,数学模型一经选定，就可以进行算法设计。算法的选择与模型的选择是密切相关的。对同一模型仍有不同的算法，这些算法的有效性可能相差很大。算法的设计是指设计求解某个具体问题类的一般步骤，并且这些步骤通过计算机的各种操作来实现。算法设计是一种复杂的、艰苦的创造性劳动，要求设计者充分发挥主观能动性，充分运用已知知识和抽象思维，形成算法思想，写出算法的具体步骤。,26,算法的正确性证明与程序的正确性证明一样，是算法理论研究中引人注目的一部分。一个算法的正确性证明，就是要证明对于一切合法输入算法都能在有限次计算后产生正确的输出。这实际上是一种穷举证明法，当算法的输入庞大时，实际上是很难做到的。当输入是一个无穷集时，穷举证明是不可能的。另一种证明方法将一个算法的输入和输出都表示成“输入断言”和“输出断言”，一个算法的各计算步可以表示成一组“谓词演算”规则。论证通过这一组谓词演算，能由输入断言导出输出断言。这种形式演绎过程是很冗长繁复，往往比一个算法（或程序）本身还要长。我们对算法的正确性不采用严格的形式论证，而只给出非形式的直观解释。,27,4,、算法的程序实现,将一个算法正确地编写成一个机器程序，叫做算法的程序实现。将给定的算法正确地转换成一个程序，并不是一个简单的工作，要求设计者掌握多种程序设计方法和技巧。,28,5,、算法分析,算法分析与算法设计有必然联系，算法设计的中心任务对于现实生活中提出的某些问题是如何设计出一个求解的算法。算法分析研究各种算法的特征和优劣。主要关心如何判定算法的优劣，标准是什么？,29,6,、程序的测试、文档编制,编制完实现算法的程序后，对程序进行测试，程序测试可以被认为是对程序应完成的任务的实验验证，同时确定程序的使用范围。编制文档应该和算法设计及实现