第1章算法设计基础ppt课件.ppt

《第1章算法设计基础ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章算法设计基础学习要点:掌握算法的概念理解什么是程序，程序与算法的区别和内在联系掌握算法的描述理解图灵机的计算模型理解P类问题和NP类问题1.1为什么要学习和研究算法程序设计的核心提高分析问题的能力以时间（速度）为核心问题，推动计算机技术发展：检索技术压缩与解压缩信息安全与数据加密1.2算法的基本概念算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足特性：输入（≥0）：有外部提供的量作为算法的输入。输出（≥1）：算法产生至少一个量作为输出。确定性：组成算法的每条指令是清晰，无歧义的。有穷性：算法中每条指令的执行次数是有限的，执行每

2、条指令的时间也是有限的。可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有穷性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。“好”算法还具备：正确性健壮性可理解性抽象分级高效性例：欧几里德算法——辗转相除法求两个自然数m和n的最大公约数欧几里德算法mnr1.2.2算法的描述方法自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述

3、算法思想注意事项：避免写成自然段欧几里德算法：①输入m和n；②求m除以n的余数r；③若r等于0，则n为最大公约数，算法结束；否则执行第④步；④将n的值放在m中，将r的值放在n中；⑤重新执行第②步。——通常用来粗略地描述算法的基本思想流程图优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次欧几里德算法：N开始输入m和nr=m%nr=0m=n；n=r输出n结束Y——通常用来描述程序设计语言的基本语法程序设计语言优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数欧几里德算法：#in

4、cludeintCommonFactor(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算法论与问题概

5、述建立计算机的模型——理想计算机，并研究模型的性质理想计算机中，研究什么样的问题是可解的可解的问题在实际计算机上计算的资源消耗情况并根据消耗情况对问题进行分类计算机的基本能力和限制是什么？自动机理论可计算性理论复杂性理论1.3.1形式语言与自动机简介语言：由组成句子的字符和被群体共同遵守的组合规则构成的统一体。什么是形式语言？形式语言：按一定规则排列的符号的集合。字母表∑：由字符构成的非空有穷集合。字符串：由∑上的字符构成的有穷序列。如，空串ε；字符串集合∑*（包括空串）（形式）语言：字符串集合∑*的任一子集。文法与语言：形式文法：产生特定语言的规则。

6、一个形式文法是一个四元组G=(V,T,S,P)：V：非空有穷集合——非终止符集合。T：非空有穷集合——终止符集合，T中的字符是语言的句子中出现的字符。V∩T=фS：起始符。S∈VP：非空有穷集合——产生式（α→β）集合。α，β∈(V∪T)*且α≠ε由文法生成的语言：L(G)={ω

7、ω∈T*且S≛＞ω}，为文法G产生的语言。文法和语言的分类0型文法1型文法（上下文有关文法）2型文法（上下文无关文法）——语法分析器！3型文法（正则文法）——词法分析器！有穷自动机ababaababbaa有穷状态q0q1q2q3控制器输入带读头确定性有穷自动机的定义：一台确定

8、性有穷自动机是一个五元组（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建立计算机的模型——理想计算机，并研究模型的性质理想计算机中，研究什么样的问题是可解的可解的问题在实际计算

9、机上计算的资源消耗情况并根据消耗情况对问题进行分类计算机的基本能力和限制是什么？自动机理论可计