计算机学科核心概念.ppt

目 录,前言第一篇 引入篇 第一章 算法概述 第二章 算法分析基础第二篇 基础篇 第三章 算法基本工具和优化技巧第三篇 核心篇 第四章 基本的算法策略 第五章 图的搜索算法第四篇 应用篇 第六章 算法设计实践,引 入 篇,第一章 算法概述,11 用计算机求解问题,问题求解(problem solving)是个大课题，它涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念 我们学习算法设计的重点就是把人类找到的求解问题的方法、步骤，以过程化、形式化、机械化的形式表示出来，以便让计算机执行。（当然人工智能软件系统也离不开“算法设计”这个最基本的软件设计环节。）就把我们学习的目标定为“用计算机求解问题”。,111 用计算机求解问题的步骤,现实中，在解决一个问题时，根据不同的经验，不同的环境会采用不同的方法，用计算机解决现实中的问题，同样也有很多不同的方法，但解决问题的基本步骤是相同的。下面给出用计算机求解问题的一般步骤。,1.问题分析 准确、完整地理解和描述问题是解决问题的第一步。要做到这一点，必须注意以下一些问题：在未经加工的原始表达中，所用的术语是否都明白其准确定义？题目提供了哪些信息？这些信息有什么用？题目要求得到什么结果？题目中作了哪些假定？是否有潜在的信息？判定求解结果所需要的中间结果有哪些？等等。针对每个具体的问题，必须认真审查问题描述，理解问题的真实要求。,2、数学模型建立 用计算机解决实际问题必须有合适的数学模型，因为在现实问题面前，计算机是无能为力。对一个实际问题建立数学模型，可以考虑这样两个基本问题：最适合于此问题的数学模型是什么？是否有已经解决了的类似问题可借鉴？如果上述第二个问题的答复是肯定的,那么通过类似的问题的分析、比较和联想，可加速问题的解决。,3、算法设计与选择 算法设计是指设计求解某一特定类型问题的一系列步骤，并且这些步骤是可以通过计算机的基本操作来实现的。算法设计要同时结合数据结构的设计，简单说数据结构的设计就是选取存储方式。算法的设计与模型的选择更是密切相关的，但同一模型仍然可以有不同的算法，而且它们的有效性可能有相当大的差距。,*在这些步骤中，算法设计是解决问题的核心。,4、算法分析 算法分析的目的，首先为了对算法的某些特定输入，估算该算法所需的内存空间和运行时间；其次是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。通常将时间和空间的增长率作为衡量的标准。另参见114算法及其设计的评价,5、算法表示 对于复杂的问题，确定算法后可以通过图形准确表示算法。算法的表示方式很多如：算法流程图、盒图、PAD图和伪码（类似于程序设计语言）等。,6、算法实现 根据选用的程序设计语言，要解决下列一些问题：有哪些变量，它们是什么类型？需要多少数组，规模有多大？用什么结构来组织数据？需要哪些子算法？等等。算法的实现方式，对运算速度和所需内存容量都有很大影响。,7、程序调试 算法测试的实质是对算法应完成任务的实验证实，同时确定算法的使用范围。测试方法一般有两种：白盒测试对算法的各个分支进行测试；黑盒测试检验对给定的输入是否有指定输出。如何选择算法测试中的输入，还没有一般答案。通常采用的方法是，对输入数据做有代表性的采样，使之对被测试算法的各个语句、分支和路径尽可能都被检查到。对输入集中的边界点也要进行测试。经测试验证是否正确的算法，在较大程度上是可以相信它的正确性。,、结果整理文档编制编制文档的目的是让人了解你编写的算法。首先要把代码编写清楚。代码本身就是文档。同时还要采用注释的方式，另外还包括算法的流程图，自顶向下各研制阶段的有关记录，算法的正确性证明（或论述），算法测试结果，对输入/输出的要求及格式的详细描述等。,112 算法及其要素和特性,、算法的定义算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。当面临某个问题时，需要找到用计算机解决这个问题的方法和步骤，算法就是对解决这个问题的方法和步骤的描述。,机械步骤是指，算法中有待执行的运算和操作，必须是相当基本的。换言之，它们都是能够精确地运行的算法，执行者甚至不需要掌握算法的含义，即可根据该算法的每一步骤要求，进行操作并最终得出正确的结果。,2算法的要素 算法由操作、控制结构、数据结构三要素组成。1）操作 算术运算：加、减、乘、除 关系比较：大于、小于、等于、不等于 逻辑运算：与、或、非 数据传送：输入、输出,赋值,2）控制结构 各操作之间的执行次序。顺序结构：各操作依次执行 选择结构：由条件是否成立来选择 执行 循环结构：有些操作要重复执行，直到功能满 足某个条件时结束。又称重复或迭 代结构。,注意：模块间的调用也是一种控制结构，特别 地模块自身的直接或间接调用递归结构，是一种功能很强的控制结构。,3）数据结构 算法操作的对象是数据，数据间的逻辑关系、数据的存储方式及处理方式就是数据的数据结构。它与算法设计是紧密相关的。,注意：算法是把人类找到的求解问题的方法，用以上要素过程化、形式化、机械化地表示出来。,在算法的表示中要满足以下的性质：目的性 算法有明确的目的，能完成赋予它的功能分步性 算法为完成其复杂的功能，由一系列计算机可执 行的步骤组成有序性 算法的步骤是有序的，不可随意改变算法步骤的 执行顺序有限性 算法是有限的指令序列，所包含步骤也是有限的 操作性 算法是有限的指令序列，算法所包含的步骤是有 限的,3.算法的基本性质,4.算法的地位,算法是计算机学科中最具有方法论性质的核心概念，也被誉为计算机学科的灵魂。,5.算法的基本特征,有穷性 一个算法在执行有穷步之后必须结束。也就是说一个算法它所包含的计算步骤是有限的而且每个步骤都能在有限时间内完成。确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。,可行性 算法中描述的操作都可以通过已经实现的基本操作运算有限次实现。算法有零个或多个的输入 有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。算法有一个或多个的输出 它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果。,113 算法设计及基本方法,1.算法设计的概念 算法设计作为用计算机解决问题的一个步骤,其任务是对各类具体问题设计良好的算法;作为一门课程，是研究设计算法的规律和方法。,2算法设计应注意的问题 1）正确性（Correctness）一切合法的输入数据都能得出满足要求的结果；典型、苛刻的几组输入数据也能够得出满足要求的结果。2）可读性(Readability)算法应该易于人的理解；晦涩难读的算法易于隐藏较多错误而难以调试。,3）健壮性（Rubustness）算法的异常情况。处理出错的方法是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4）高效率与低存储量需求 效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。,3算法设计的基本方法,1）结构化方法“自顶向下,逐步求精”结构化方法总的指导思想是自顶向下、逐步求精。它的基本原则是功能的分解与模块化 所谓“自顶向下”是将现实世界的问题经抽象转化为逻辑空间或求解空间的问题。是将复杂且大的问题划分为较小问题，找出问题的关键和重点，然后抽象、概括地描述问题。所谓“逐步求精”是将复杂问题经抽象化处理变为相对比较简单的问题。经若干步精化处理，最后细化到用“三种基本结构”及基本操作去描述算法。,结构算法设计技术的优越性:符合人类解决复杂问题的普遍规律。用先全局后局部、先整体后细节、先 抽象后具体的逐步求精过程开发出的 算法有清晰的层次结构。,2)面向对象方法 对象=数据+对数据操作的代码实体 面向对象算法设计方法的过程包括以下步骤：在给定的抽象层次上识别类和对象 识别这些对象和类的语义 识别类和对象之间的关系 实现类和对象,面向对象方法的特征主要包括:抽象化 将各种独立的操作分解成为可以用命名区分的单元。封装性 不同的操作具有不同的作用范围。多态性 对于不同数据类型的相似操作使用相同的名。继承性 类可以被继承。重用是面向对象的一个重要优点。最大特点是能够大幅度的提高软件项目的成功率，减少日后的维护费用，提高软件的可移植性和可靠性。,3）本书采用的设计方法结构化设计方法（1）自顶向下从抽象到具体 把一个较大的算法划分为若干子模块 每一个模块可继续划分为更小的子模块 直到用三种控制结构和具体操作表示算 法注：运用这种编程方法，考虑问题必须先进行整体分析。,（2）模块划分的基本要求 模块的功能尽可能地单一化、明确化 模块间的联系及相互影响尽可能地小 模块的规模应当足够小，以便于调试 原则是简单性、独立性和完整性。,（3）模块间的接口问题 传递方式一般有以下几种：按名共享：全局变量 子模块返回调用模块信息：子模块名 调用模块传递给子模块信息：值参数传递 调用模块与子模块互相传递信息：变量参数传递(C语言没有此种传递方,Pascal、C+语言提供此类参数)按地址共享变量：地址参数传递（参数为指针变量名、数组名，变量地址）,（4）算法细节设计的基本方法从具体到抽象 设计算法“如何做”的细节是比较容易出错的，如：循环变量的初始值或终值，数组的下标与循环变量间的关系等算法细节的确定。最基本的方法是通过“枚举”一些真实数据，从具体的实例中，抽象“归纳”出算法的这些细节。,（5）算法的正确性 算法的正确性不容易证明。即使可以证明，所涉及的数学理论和推导证明过程也很复杂。设计算法时力争严谨、考虑周全，可能的情况下，分析论证算法设计的合理性，最后在算法实现后，靠大量的测试，以保证算法的正确性。,1.1.4 从算法到实现,从算法到实现应注意的问题有：1.数据类型的选择 类型的选择主要取决于你解决问题中数据的实际情况。,这部分知识不属于本书的必要内容。在此进行简述是为了让读者在学习算法设计过程中上机实验时，不要走太多弯路。,2 计算过程的差异 运算符号的差异 运算符优先级的差异 标识符命名方式的差异 循环方式的差异,3.结果的输出格式 如：矩阵输出时上、下行的数据应该对齐。4.算法实现后的测试、调试 测试就是要发现算法是否存在问题。测试就是要找到出现问题的原因并改正它。然后还需要进行回归测试，以确保算法的正确性。,1.2 算法描述,121 算法描述简介,算法是对解题过程的精确描述。算法=控制结构+原操作 表示算法的语言主要有：自然语言、流程图、盒图、PAD图、伪代码和计算机程序设计语言等。,1自然语言 自然语言是人们日常所用的语言。其缺点是：由于自然语言的歧义性容易导致算法执行的不确定性。自然语言的语句一般太长从而导致了用自然语言描述的算法太长。当一个算法中循环和分支较多时就很难清晰地表示出来。自然语言表示的算法不便翻译成计算机程序设计语言理解的语言。,2流程图 流程图可以表示任何算法的逻辑结构。1)基本组件,算法的 加工、处理 条件 控制流 连接点 入口和出口,2）三种基本控制结构 顺序结构：,选择结构,IF THEN ELSE型分支 DOCASE型多分支,循环结构,DOWHILE型循环 DOUNTIL循环结构,3)算法流程图的主要缺点 不是逐步求精的好工具，它诱使算法员过早地考虑算法的控制流程，而不去考虑算法的全局结构。随意性太强，结构化不明显。不易表示数据结构。流程图的层次感不明显,3盒图（NS流程图）（1）盒图具有以下优点：层次感强、嵌套明确 支持自顶向下、逐步求精。容易转换成高级语言源算法,（2）三种基本控制结构 顺序结构,选择结构,当条件P为真执行语句体A 当条件P的值为P1时执行语句体 否则执行语句体 A1，为P2时执行语句体A2，,循环结构,如果条件P成立，如果条件P不成立，重复执行S 重复执行S,（3）主要缺点：不易扩充和修改，不易描述大型复杂算法。,4 PAD图 问题分析图(Problem Analysis Diagram,简称PAD)表示的算法是一个二维树形结构图，层次感强、嵌套明确且有明确的控制流程。,三种基本控制结构 顺序结构,选择结构,如果条件P成立，执行S1 当条件P的值为P1,执行语句体S1 条件不成立，执行S2 为P2时执行语句体A2，,循环结构,如果条件P成立，重复执行S 如果条件P不成立，重复执行S,PAD图的主要优点：设计出来的算法必是结构化的。PAD图描绘的算法结构清晰。用PAD图表现的算法逻辑，易读、易懂、记。容易用软件工具自动将PAD图转换成高级语言 源算法。既可用于表示算法逻辑，也可用于描绘数据结构。支持自顶向下、逐步求精。缺点：由于是图形符号书写、录入不方便。,例：,图3.6 问题分析图实例,5伪代码 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号，因此书写方便格式紧凑，易于理解，便于用计算机程序设计语言实现。,6程序设计语言的缺点 算法的基本逻辑流程难于遵循与自然语言一样，程序设计语言也是基于串行的，当算法的逻辑流程较为复杂时这个问题就变得更加严重 特定程序设计语言编写的算法限制了与他人的交流，不利于问题的解决 要花费大量的时间去熟悉和掌握某种特定的程序设计语言 要求描述计算步骤的细节而忽视算法的本质 需要考虑语法细节，而扰乱算法设计的思路 考虑到程序设计语言的不断更新，不适于描述算法。算法设计都不用程序设计语言直接描述。,122 算法描述约定,本书采用类C语言的伪代码描述，具体细节约定如下：1、三种基本控制结构的描述 1）顺序结构 一个操作以分号“；”结束，每行一般只写一条操作。,2）选择结构 单条件控制 if 条件 语句体1 else 语句体2,多条件控制switch(表达式0)case常量表达式1:语句组1;case常量表达式n:语句组n;default:语句组n+1;,3）循环结构 计数循环：for(表达式1；表达式2；表达式3)循环体 当型循环：while(循环条件)循环体 直到型循环：do 循环体 while(循环条件)；说明：在这三种循环体中，均可有continue语句和 break语句。,2、数据结构说明 算法中的标识符由字母数字构成，以字母开头。1）一般类型说明方式：类型名 变量表；类型名有：整型int、实型float、双精度型 double 字符型 char 2）指针类型说明方式：类型名*指针变量名表；,3）构造类型：数组说明：类型名 一维数组名n(开辟n个空间，下标0n-1)；类型名 二维数组名m,n(开辟m*n个空 间，下标0,0m-1,n-1)；结构类型:struct 结构体类型名 类型 成员名;类型 成员名;.;,4）动态空间申请函数 malloc(size)功能：申请size个字节的一个空间；返回所申请空间的首地址。calloc(num,size)功能：申请num个size个字节的空间；返回所申请空间的首地址。free(*p)功能：释放p指向的动态空间。,3模块及模块间的接口方式的描述 算法或算法中模块结构为：模块（算法）名（参数）模块体,模块间的接口方式的描述如下：全局变量：定义模块外的变量。子模块返回调用模块信息：调用函数：子模块名 被调用函数：return(返回信息)调用模块传递给子模块信息：值参数传递 实际参数为：表达式、普通变量名、常量或数组元素 形式参数为：普通变量名,调用模块与子模块互相传递信息：变量参数传递 实际参数为：普通变量名 形式参数为：&变量名 按地址共享变量：地址参数传递 实际参数为：指针变量名(不带*)、数组名，变量地址（&变量名）形式参数为：指针变量名(*变量名),4其它细节说明：1）无歧义的情况下一般不做存储结构和数据类型说明。2）运算符号采用较通用的表示形式，如求余不用“%”而用“mod”表示、逻辑“与”不用“&”而用“and”表示等等。3）用 表示整除，用/表示带小数除法。4）无歧义时允许连续赋值，如a=b=1。5）条件语句中判断相等，用符号“=”，判断不相等，用符号“”。,6）算法中的注释用“/”与操作分隔。7）为讲解说明方便，有的算法对指令进行编号。8）输入用input(变量表)表示，输出用print(输出项)表示，一般不说明输入、输出格式。9）算法中会使用库函数，一般在算法中注释其功能。如ABS（）取绝对值，INT（）取整函数（舍去小数部分）。,123 一个简单问题的求解过程,问题求解的步骤可以简化为三步：具体（问题的现实领域）1问题分析建立模型抽象（逻辑结构、模型建立、功能确认）2算法设计具体（计算机世界）3算法分析抽象（性能及算法文档）。,第一步“数学建模”是在对问题的认真分析加上必要的数学知识来确定问题的解决方法。对一般的问题，我们把这一步称为“问题分析”，是确认问题和问题的基本运算的。运算只描述处理功能，第二步“算法设计”是对处理功能的求精，即找出问题的处理步骤。第三步“算法分析”是对数学模型的建立、数据结构的选择及算法设计工作的评价、总结。,【例】求二个正整数的最大公约数。问题分析：此题只需有小学知识，就可有以下建立以下的数学模型。数学模型：a，b0 的整数，求c，c能整除a，b，且a/c与b/c互质。算法设计：这个方法首先基于人能“宏观”地“看出”所求两数的公约数才能继续的。计算机虽没有“宏观”能力来“看出”公约数，但通过“枚举尝试”（逐个尝试）就可以“试出”a,b有哪些是公约数，并将这些公约数“累乘”，就能得到最大公约数。,具体算法设计：1）用for循环枚举可能的因数，并用变量累乘求出的因数。2）注意到2因数在“4，8”两个数据中出现两次，所以，测试某因数是否所给数据的因数时，应该用循环语句而不是条件语句。,算法描述如下：main()int a,b,t,i;input(a,b);c=1；/变量c是为累乘因数而设置的；for(i=2;i=a and i=b;i+)/“枚举”可能的公约数 while(a mod i=0 and b mod i=0)/“试”i是否为公约数 t=t*i;a=a/i;b=b/i;print(t,“is maximal common divisor”);,算法说明：变量t是为累乘因数而设置的；外层循环是在“枚举”可能的公约数，内层循环条件是在“尝试”i是否为公约数，若是则进入内层循环累乘因数，并且对a,b都除掉这个因数，避免下次重复计算该因数。算法分析：通过以上算法设计过程应该看到，可以依赖以前学到的解决问题方法，改进有关步骤以便能通过机械的计算机操作（准确地说是通过程序设计语言）来实现。“问题分析、数学模型、算法设计要点、算法分析”是解决问题的必然过程。,下面是初学者容易发生的一些问题，提前指出以引起大家注意：通过输入语句增加算法的通用性。会忘掉“输出”或在模块间传递处理的数据结果 易忽略细节造成“死循环”。出现语序方面的错误，特别是双重循环中指令常有嵌套错误。注意学习和总结。用大脑“运行”算法是学习算法很好的方法。解题时要学会择优。简单说择优要考虑四个方面：可读性、可修改性、时间效率和空间效率。,