《算法与程序设计》（浙教版）教材介绍

《《算法与程序设计》（浙教版）教材介绍》由会员分享，可在线阅读，更多相关《《算法与程序设计》（浙教版）教材介绍（25页珍藏版）》请在金锄头文库上搜索。

1、算法与程序设计 （浙教版）教材介绍华东师范大学吴洪来一、为什么标准要将这门课程 列为选修模块二、教材编写思路三、计算机处理中的“难”的问题和 不能处理的问题计算机技术对社会和世界已经产生了 深刻的影响。每个公民都要熟知这项技术 以及它在家庭、学校、工作场所和社区所 起的重要作用。由于这门技术的细节发展 日新月异，因此要跟上这些技术的细节是 困难的，而且常常是徒劳的。所以，这门 课的学习必须注重本领域基本的科学原理 和概念。 摘自ACM高中计算机科学课程规范当今的高中计算机教学要么是将计算机作 为其他学科的工具（字处理是为学英文，电子 表格和数据库是商科的工具，CAD/CAM是技术 教学的工具，

2、数学软件包是数学和科学课的工 具），要么就是讲授程序设计。这两种讲法都 没有抓住计算机科学的本质，尽管两者都包括 了训练方面。计算机科学课的学习应由一些最 基本的一般概念组成，这些概念超越技术本身 ，并且是高中教育的一个基本组成部分。正是 这些概念使学生们得以了解并有效地参与到现 代世界中来。摘自ACM高中计算机科学课程规范 目前，在高中计算机教师队伍中还有 不少人是在其他领域里受的教育，他们很 少有机会接受计算机科学方面的正规培训 ，有些完全是自学的。因此在实施具体教 学过程之前，其中的大多数人还需接受某 种正规培训，以更好地理解和掌握现代计 算机科学的理念。摘自ACM高中计算机科学课程规范

3、在教学过程中，要让学生们学会把一 个算法看成是一个活生生的处理过程的一 种精确描述，而这种处理可以由计算机、 人或某种机器来实现。学生要学会设计简 单的算法，并对这种算法的效率能做出粗 略评价；要能够说明算法的基本构件，如 顺序、选择和重复；也要能够认识算法的 许多不同形式的表示，程序设计语言只是 许多表示方法中的一种。摘自ACM高中计算机科学课程规范一、为什么标准要将这门课列入选修模块12003年4月教育部颁布了普通高中课程方案 ，方案强调提高学生“分析和解决问题的能力”。同年，教育部制订的技术课程标准(信息 技术部分)在课程目标中提出：“能熟练运用信息 技术，通过有计划的、合理的信息加工进

4、行创造 性探索或解决实际问题”。要求是比较高的。怎样培养学生分析问题和解决问题的能力， 通过算法与程序设计课程的教学是达到这一 目标的有效途径之一，这一点在标准起草小 组中有了共识。2信息技术和数学两个标准 起草小组曾两次在一起讨论 ，如何加强算法理念的教学。 中科院张景中院士等人专门就“ 算法”列入教学内容提出了看法 和建议。3算法在问题求解中的地位问题空间计算机空间问题定义模型化自然语言伪代码数学语言数据结构设计算法制定自动数据转换机器指令程序设计语言计算机实现编码问题定义模型化自然语言数学语言4基于问题求解驱动的算法课程设计的 教学模式之一优 化问题定义问题描述引导形成问题描述算法与数据

5、结 构设计编制代码 上机实现算法程序的质 量分析问题分析生成结果 分析结果修正过滤分类抽象化问题来源n问题来源2问题来源1问题来源2学教二、教材编写思路早先，在高中计算机课程中，不少学校曾 试验过程序设计语言的教学，较多时间介绍该 语言所用的符号、语句和规则等，在讲解编程 举例时也讲一点算法，用来作为语言应用实例 。实际上这是一种本末倒置。为此，我们尝试 在教材中强调算法在解决问题过程中的关键地 位，得到了教育部评审专家的肯定。审查意见 认为：“突出了“算法”的核心地位，有一定特点 ，可以探索使用。”1.尝试新的教材体系著名的计算机科学家Kunth认为：计算机 科学是算法的学习。瑞士科学家Wi

6、rth给出公式 ：算法数据结构程序。算法是程序设计的依据，而程序设计语 言只是算法描述的手段之一。为此，我们在教 材中花了相当多的篇幅，以问题解决为核心， 用较易理解的自然语言和流程图语言来描述算 法，让学生充分体验算法的作用，并逐步建立 起算法思维的理念和方法。有了上述基础再讲“ 算法实现（编程、上机）”就比较自然了。2.几种常用算法的介绍教材介绍了 5 种常用算法：枚举（蛮干）、解析、排序、查找、递归。这几种算法在学习、生活和工作中是大量遇到的。(1)枚举算法。教材介绍了两个例子，其中关于“单据”的实例 比较有趣，而第二个例子是解不定方程，解不定方 程技巧性很强，但用计算机进行枚举搜索却比

7、较容 易，学生也易于理解。(2)解析算法。将问题归结为数学表达式，并通过计算机 来实现问题求解，是学生较易接受的。困难点 可能是如何归结出表达问题的数学表达式。(3)排序和查找算法。“排序和查找”在学校学习中被大量运用， 学生会排序，但不知道如何用计算机来排序； 用计算机检索资料对有些学生来说是轻而易举 的事，但他们可能不知道资料为什么会这么快 被查到。这里面就有一个知其所以然的问题。Kunth在他的计算机程序设计的 艺术的第3卷整卷探讨了这两种算法， 可见其重要性。有专家称这两种算法是“ 使用频率最高的算法”。(4)递归算法。这种算法应用很广泛，它是一个把 较大规模的问题逐次简化为一个简单易

8、解 问题的一般算法。递归就使程序调用自身 。教材以计算n!为例来说明递归算法。3.教学实施建议(1)按教材编写顺序进行教学。这确实是一种新的尝试，突出了算法思想 ，但由于在第三章学习前较难安排上机实践， 会使学生感到不适应。为此，我们为教材配套 了光盘，其中附有全部实例的算法执行过程(流 程图)的演示动画，生动直观，有助理解。(2)将第二章的“排序”、“查找”和第五章的程序实 现结合起来组织教学，这样可使编程和上机的 时间提前。三、计算机处理中的“难”的问题和不可解问题现实世界中，大量非数值问题在求解时，首 先要判定其是否可解。通过建立计算的数学模 型（如图灵机、递归函数、-演算、Post系统

9、等 ）精确区分哪些是可计算的，哪些是不可计算 的。但是许多问题本身是不可判定的(如悖论问 题、图灵机停机问题等)。只有是可判定、可计 算的问题，才能通过精确的算法描述进行求解 。 计算的过程就是执行算法的过程。可计算性 的核心问题是将算法这一直观概念精确化，变 为一个具有有限性、可执行性、确定性、终止 性、有限个输入、1个或1个以上输出的具体算 法。 现代计算机处理问题的能力确实很强 ，我们的学习、工作、生活都离不开计算 机。这一点经过多年的信息技术课程的学 习，学生们都有体会。但是，计算机不是 无所不能的，有些问题对计算机来说是很 “难”的，有的则是计算机无法解决的。这 些在教材中没有写入，

10、而是在教师用书的 第三部分作了一些介绍，尽管是浅显的， 任课老师读一读有好处，条件较好的学校 ，可将其中一些思想介绍给学生。1.多项式问题（P问题）如果一个问题的规模是n，按某种算法解 决问题时用的计算次数是n的多项式，或者说计 算的复杂度为O(log n)，O(n)，O(n2)，O(n3)或 O(nk)（k为常数），则称该算法为多项式算法 ，而这类问题称为多项式(P)问题。以当今计算 机的处理速度，对于一个有合理输入数量的多 项式问题，计算机都能有效地予以解决。一个问题会有多种算法，算法会有快、慢 。例如教材中排序、查找部分，选择排序比冒 泡排序快，对分查找比顺序查找快，等等。2.非多项式问

11、题（NP问题）有许多问题，当它们的规模变得越 来越大时，不管你采用什么算法，求解它 所用的时间都会长得惊人。就算是用当今 的快速计算机，都无法在可容忍的时间内 完成，这就是所谓非多项式（NP）问题 。若问题求解时所用算法的计算时间的 阶等价于某种指数函数，或者说算法的复 杂度为O(2n)，O(kn) （k为常数）或O(n!) ， 则称该算法为指数型算法，而这类问题 就是非多项式（NP）问题。非多项式问 题远比多项式问题难度大，当问题规模增 大时，用计算机处理需要数月甚至数年的 时间才能得出问题结果。例如，梵塔问题 、货郎担问题、因式分解问题、纵横字谜 问题、图形着色问题、棋类博弈问题、可 满足

12、性问题等等都是所谓“难”的问题。3.不可解问题对这类问题，无法用计算机程序来解决。 图灵是较早发现这类问题的人。例如，他提出 了“停机问题”就是一个不可解问题。还有很多不 可解问题。问 题不可解的问题非多项式问题多项式问题可解的问题小结：计算机是现代化信息处理工具，“信息 ”在这里是以有限种符号的有限长序列这 种形式所表示的，而“处理”的过程就是按 预先编好的程序对这种序列做有穷的变换 ，以得到一组新的符号序列作为结果。这 就是计算机科学中术语“计算”的确切含义 。要计算机去解决某种问题，有三个基 本前提：1.必须把问题形式化计算机求解的过程就是从表示 问题的符号串出发，按规则进行加 工，直到得出符合要求的结果(符号 串)为止。就是说，先要建立一个形式系统。 规定所用的符号、规则（语法）以及如 何用合法符号串来表示问题的意义与处 理过程等。2. 问题必须是可计算的，即一定要有算 法。存在着某个算法和找出这个算法是 两回事，前者是客观的，后者是人脑和 知识的功能。3. 要用计算机实现一个算法以解决某种 问题，问题的复杂度必须是合理的，即 要避免指数爆炸。