第1章算法设计基础.

第1章算法设计基础学习要点:掌握算法的概念理解什么是程序，程序与算法的区别和内在联系掌握算法的描述理解图灵机的计算模型理解P类问题和NP类问题1.1为什么要学习和研究算法程序设计的核心提高分析问题的能力以时间（速度）为核心问题，推动计算机技术发展：检索技术压缩与解压缩信息安全与数据加密1.2算法的基本概念算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足特性：输入（≥0）：有外部提供的量作为算法的输入。输出（≥1）：算法产生至少一个量作为输出。确定性：组成算法的每条指令是清晰，无歧义的。有穷性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有穷性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。“好”算法还具备：正确性健壮性可理解性抽象分级高效性例：欧几里德算法——辗转相除法求两个自然数m和n的最大公约数欧几里德算法mnr1.2.2算法的描述方法自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想注意事项：避免写成自然段欧几里德算法：①输入m和n；②求m除以n的余数r；③若r等于0，则n为最大公约数，算法结束；否则执行第④步；④将n的值放在m中，将r的值放在n中；⑤重新执行第②步。——通常用来粗略地描述算法的基本思想流程图优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次欧几里德算法：N开始输入m和nr=m%nr=0m=n；n=r输出n结束Y——通常用来描述程序设计语言的基本语法程序设计语言优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数欧几里德算法：#includeiostream.hintCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}伪代码介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强、抽象性强、容易理解欧几里德算法：1.r=m%n;2.循环直到r=0;2.1m=n;2.2n=r;2.3r=m%n;3.输出n;1.2.3算法问题求解过程证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法1.3算法论与问题概述建立计算机的模型——理想计算机，并研究模型的性质理想计算机中，研究什么样的问题是可解的可解的问题在实际计算机上计算的资源消耗情况并根据消耗情况对问题进行分类计算机的基本能力和限制是什么？自动机理论可计算性理论复杂性理论1.3.1形式语言与自动机简介语言：由组成句子的字符和被群体共同遵守的组合规则构成的统一体。什么是形式语言？形式语言：按一定规则排列的符号的集合。字母表∑：由字符构成的非空有穷集合。字符串：由∑上的字符构成的有穷序列。如，空串ε；字符串集合∑*（包括空串）（形式）语言：字符串集合∑*的任一子集。文法与语言：形式文法：产生特定语言的规则。一个形式文法是一个四元组G=(V,T,S,P)：V：非空有穷集合——非终止符集合。T：非空有穷集合——终止符集合，T中的字符是语言的句子中出现的字符。V∩T=фS：起始符。S∈VP：非空有穷集合——产生式（α→β）集合。α，β∈(V∪T)*且α≠ε由文法生成的语言：L(G)={ω|ω∈T*且S≛＞ω}，为文法G产生的语言。文法和语言的分类0型文法1型文法（上下文有关文法）2型文法（上下文无关文法）——语法分析器！3型文法（正则文法）——词法分析器！有穷自动机ababaababbaa有穷状态q0q1q2q3控制器输入带读头确定性有穷自动机的定义：一台确定性有穷自动机是一个五元组（Q,Σ,δ,S,F)。其中，Q,Σ,δ都是有穷集合。Q：有穷状态集合Σ：字母表S：初始状态。S∈QF：终止状态集合。FQδ：转移函数。Q×Σ→Q例设计一台确定性有穷自动机，它接受这样的语言：由a,b字符构成、不含3个连续b字符的有限长度的字符串。Q={q0,q1,q2,q3}∑={a,b}S=q0F={q0,q1,q2}δ采用状态图表示：应用：文本处理、编译程序、程序设计语言和人工智能等。q0q1q2q3bbbaaaab建立计算机的模型——理想计算机，并研究模型的性质理想计算机中，研究什么样的问题是可解的可解的问题在实际计算机上计算的资源消耗情况并根据消耗情况对问题进行分类计算机的基本能力和限制是什么？自动机理论可计算性理论复杂性理论▽bababb□□□□□1.3.2图灵机（TuringMachines——TM）特点：读/写头即能读，又能写。读写头能左/右移动，但不会移出带的左端。“带”无限长，上置所读/写的字符和特殊符号。有穷状态控制器内置各种状态。带有穷状态q0q1q2q3控制器读/写头（可以双向移动）TM工作原理设：有穷控制器当前状态是q，读/写头读入当前字符a。有穷控制器每步完成以下操作：根据当前的(q,a)，读/写头完成以下操作：在当前字符位置上写一个字符b（b可为ф）。左移或右移一个字符位置，或不动。有穷控制器从状态q，进入新状态p。仅当有穷状态控制器所进入的新状态p属于停机状态时，TM停止计算。——符合计算的本质TM的定义一个图灵机是一个七元组（Q,∑,Γ,δ,S,A,R)。其中，Q,∑,Γ都是有穷集合，并且：Q：TM的状态集合。∑：输入字母表。（不含空白符和）Γ：带字母表。（，Γ；∑Γ）δ：转移函数。Q×Γ↦Q×Γ×{→，←}SQ：起始状态。AQ：接受状态RQ：拒绝状态停机状态1.3.3可计算性一个问题是可计算的，当且仅当它在图灵机上经过有限步骤后得到正确的结果。——Turing论题例子：希尔伯特第10问题：判断任意一个整系数多项式是否有整数根。（“算法”？）6x3+7x2y–2xy2+y3z–12Church-Turing论题算法的直觉化概念等于在所有输入机上停机的Turing机停机问题对于任意的计算机程序及其一个输入，能否设计一个程序，它判定计算机程序相对该输入是否停机？——不可计算问题可计算性的现实意义不能验证一个计算机程序具有一定功能不能判定任意一个程序是否包含计算机病毒问题的算法可解性与计算机程序之间的区别建立计算机的模型——理想计算机，并研究模型的性质理想计算机中，研究什么样的问题是可解的可解的问题在实际计算机上计算的资源消耗情况并根据消耗情况对问题进行分类计算机的基本能力和限制是什么？自动机理论可计算性理论复杂性理论1.3.4计算复杂性Cook论题：一个问题是实际可计算的当且仅当它在图灵机上进过多项式步骤得到正确的结果。易解问题可以在多项式时间内求解的问题。难解问题需要指数时间求解的问题。确定性算法算法的每一步运算结果都是唯一。一个七元组（Q,∑,Γ,δ,S,A,R)的图灵机所确定的算法就是确定性算法。非确定性算法理论上，允许算法每步运算的结果是一个运算结果集合中的一个元素。非确定性算法下，一个非确定性图灵机仍然是一个七元组。但，转移函数是：δ：Q×Γ↦P3(Q×Γ×{→，←})P3(M)：M的幂集两类问题P类问题（语言）：所有可在多项式时间内用确定算法求解的判定问题（语言）的集合。它是确定性计算模型下的易解问题类。NP类问题（语言）：所有可在多项式时间内用非确定算法求解的判定问题（语言）的集合。它是非确定性计算模型下的易验证问题类。特殊的NP问题就是NP完全问题（即NPC）。NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立!!一般认为NPC问题是难解的问题类。问题类型查找问题排序问题231333231788131723233313233323178132333231781323233317813172323338图问题组合问题最小乘车费用假设12345678910费用122131404958697990101而任意一辆汽车从不行驶超过10公里。某人想行驶n公里，假设他可以任意次换车，请你帮他找到一种乘车方案，使得总费用最小。几何问题怎么修围墙满足利用最大化？本章小结算法的概念、表示方法和问题的求解过程。介绍了算法论的三方面研究内容：形式语言与自动机：建立计算机模型并研究模型性质可计算性理论：确定哪些问题可解，哪些问题不可解计算复杂性理论：把问题分成易解的P类问题、易验证的NP类问题和难解的NP完全问题。