计算机学科核心概念

《计算机学科核心概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录前言第一篇引入篇第一章算法概述第二章算法分析基础第二篇基础篇第三章算法基本工具和优化技巧第三篇核心篇第四章基本的算法策略第五章图的搜索算法第四篇应用篇第六章算法设计实践引入篇第一章算法概述1．1用计算机求解问题问题求解(problemsolving)是个大课题，它涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念我们学习算法设计的重点就是把人类找到的求解问题的方法、步骤，以过程化、形式化、机械化的形式表示出来，以便让计算机执行。（当然人工智能软件系统也离不开“算法设计”这个最基本的软件设计环节。）就把我们学习的目标定为“用计算机求解问题”。1．1．1用计算机求解问

2、题的步骤现实中，在解决一个问题时，根据不同的经验，不同的环境会采用不同的方法，用计算机解决现实中的问题，同样也有很多不同的方法，但解决问题的基本步骤是相同的。下面给出用计算机求解问题的一般步骤。1.问题分析准确、完整地理解和描述问题是解决问题的第一步。要做到这一点，必须注意以下一些问题：在未经加工的原始表达中，所用的术语是否都明白其准确定义？题目提供了哪些信息？这些信息有什么用？题目要求得到什么结果？题目中作了哪些假定？是否有潜在的信息？判定求解结果所需要的中间结果有哪些？等等。针对每个具体的问题，必须认真审查问题描述，理解问题的真实要求。2、数学模型建立用计算机解决实际问题必须有合

3、适的数学模型，因为在现实问题面前，计算机是无能为力。对一个实际问题建立数学模型，可以考虑这样两个基本问题：最适合于此问题的数学模型是什么？是否有已经解决了的类似问题可借鉴？如果上述第二个问题的答复是肯定的,那么通过类似的问题的分析、比较和联想，可加速问题的解决。3、算法设计与选择算法设计是指设计求解某一特定类型问题的一系列步骤，并且这些步骤是可以通过计算机的基本操作来实现的。算法设计要同时结合数据结构的设计，简单说数据结构的设计就是选取存储方式。算法的设计与模型的选择更是密切相关的，但同一模型仍然可以有不同的算法，而且它们的有效性可能有相当大的差距。*在这些步骤中，算法设计是解决问题

4、的核心。4、算法分析算法分析的目的，首先为了对算法的某些特定输入，估算该算法所需的内存空间和运行时间；其次是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。通常将时间和空间的增长率作为衡量的标准。另参见1．1．4算法及其设计的评价5、算法表示对于复杂的问题，确定算法后可以通过图形准确表示算法。算法的表示方式很多如：算法流程图、盒图、PAD图和伪码（类似于程序设计语言）等。6、算法实现根据选用的程序设计语言，要解决下列一些问题：有哪些变量，它们是什么类型？需要多少数组，规模有多大？用什么结构来组织数据？需要哪些子算法？等等。算法的实现方式，对运算速度和所需内存容量都有很大影响

5、。7、程序调试算法测试的实质是对算法应完成任务的实验证实，同时确定算法的使用范围。测试方法一般有两种：白盒测试对算法的各个分支进行测试；黑盒测试检验对给定的输入是否有指定输出。如何选择算法测试中的输入，还没有一般答案。通常采用的方法是，对输入数据做有代表性的采样，使之对被测试算法的各个语句、分支和路径尽可能都被检查到。对输入集中的边界点也要进行测试。经测试验证是否正确的算法，在较大程度上是可以相信它的正确性。８、结果整理文档编制编制文档的目的是让人了解你编写的算法。首先要把代码编写清楚。代码本身就是文档。同时还要采用注释的方式，另外还包括算法的流程图，自顶向下各研制阶段的有关记录，算

6、法的正确性证明（或论述），算法测试结果，对输入/输出的要求及格式的详细描述等。1．1．2算法及其要素和特性１、算法的定义算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。当面临某个问题时，需要找到用计算机解决这个问题的方法和步骤，算法就是对解决这个问题的方法和步骤的描述。机械步骤是指，算法中有待执行的运算和操作，必须是相当基本的。换言之，它们都是能够精确地运行的算法，执行者甚至不需要掌握算法的含义，即可根据该算法的每一步骤要求，进行操作并最终得出正确的结果。2．算法的要素算法由操作、控制结构、数据结构三要素组成。1）操作算术运算：加、减、乘、除关系比较：大于、小于

7、、等于、不等于逻辑运算：与、或、非数据传送：输入、输出,赋值2）控制结构——各操作之间的执行次序。顺序结构：各操作依次执行选择结构：由条件是否成立来选择执行循环结构：有些操作要重复执行，直到功能满足某个条件时结束。又称重复或迭代结构。注意：模块间的调用也是一种控制结构，特别地模块自身的直接或间接调用—递归结构，是一种功能很强的控制结构。3）数据结构算法操作的对象是数据，数据间的逻辑关系、数据的存储方式及处理方式就是数据的数据结构。它与算法设计是紧密相关的。