《算法与程序设计浙教版教材介绍.ppt》由会员分享，可在线阅读，更多相关《算法与程序设计浙教版教材介绍.ppt（25页珍藏版）》请在三一文库上搜索。
1、算法与程序设计（浙教版）教材介绍,华东师范大学 吴洪来,一、为什么标准要将这门课程列为选修模块 二、教材编写思路 三、计算机处理中的“难”的问题和不能处理的问题,计算机技术对社会和世界已经产生了深刻的影响。每个公民都要熟知这项技术以及它在家庭、学校、工作场所和社区所起的重要作用。由于这门技术的细节发展日新月异，因此要跟上这些技术的细节是困难的，而且常常是徒劳的。所以，这门课的学习必须注重本领域基本的科学原理和概念。 摘自ACM高中计算机科学课程规范,当今的高中计算机教学要么是将计算机作为其他学科的工具（字处理是为学英文，电子表格和数据库是商科的工具，CAD/CAM是技术教学的工具，数学软件包是
2、数学和科学课的工具），要么就是讲授程序设计。这两种讲法都没有抓住计算机科学的本质，尽管两者都包括了训练方面。计算机科学课的学习应由一些最基本的一般概念组成，这些概念超越技术本身，并且是高中教育的一个基本组成部分。正是这些概念使学生们得以了解并有效地参与到现代世界中来。 摘自ACM高中计算机科学课程规范,目前，在高中计算机教师队伍中还有不少人是在其他领域里受的教育，他们很少有机会接受计算机科学方面的正规培训，有些完全是自学的。因此在实施具体教学过程之前，其中的大多数人还需接受某种正规培训，以更好地理解和掌握现代计算机科学的理念。 摘自ACM高中计算机科学课程规范,在教学过程中，要让学生们学会把一
3、个算法看成是一个活生生的处理过程的一种精确描述，而这种处理可以由计算机、人或某种机器来实现。学生要学会设计简单的算法，并对这种算法的效率能做出粗略评价；要能够说明算法的基本构件，如顺序、选择和重复；也要能够认识算法的许多不同形式的表示，程序设计语言只是许多表示方法中的一种。 摘自ACM高中计算机科学课程规范,一、为什么标准要将这门课列入选修模块,12003年4月教育部颁布了普通高中课程方案，方案强调提高学生“分析和解决问题的能力”。 同年，教育部制订的技术课程标准(信息技术部分)在课程目标中提出：“能熟练运用信息技术，通过有计划的、合理的信息加工进行创造性探索或解决实际问题”。要求是比较高的。
4、 怎样培养学生分析问题和解决问题的能力，通过算法与程序设计课程的教学是达到这一目标的有效途径之一，这一点在标准起草小组中有了共识。,2信息技术和数学两个标准起草小组曾两次在一起讨论，如何加强算法理念的教学。中科院张景中院士等人专门就“算法”列入教学内容提出了看法和建议。,3算法在问题求解中的地位,问题空间 计算机空间,4基于问题求解驱动的算法课程设计的教学模式之一,二、教材编写思路,早先，在高中计算机课程中，不少学校曾试验过程序设计语言的教学，较多时间介绍该语言所用的符号、语句和规则等，在讲解编程举例时也讲一点算法，用来作为语言应用实例。实际上这是一种本末倒置。为此，我们尝试在教材中强调算法在
5、解决问题过程中的关键地位，得到了教育部评审专家的肯定。审查意见认为：“突出了“算法”的核心地位，有一定特点，可以探索使用。”,1.尝试新的教材体系,著名的计算机科学家Kunth认为：计算机科学是算法的学习。瑞士科学家Wirth给出公式：算法数据结构程序。 算法是程序设计的依据，而程序设计语言只是算法描述的手段之一。为此，我们在教材中花了相当多的篇幅，以问题解决为核心，用较易理解的自然语言和流程图语言来描述算法，让学生充分体验算法的作用，并逐步建立起算法思维的理念和方法。有了上述基础再讲“算法实现（编程、上机）”就比较自然了。,2.几种常用算法的介绍,教材介绍了 5 种常用算法： 枚举（蛮干）、
6、解析、排序、查找、递归。 这几种算法在学习、生活和工作中是大量遇到的。 (1)枚举算法。 教材介绍了两个例子，其中关于“单据”的实例比较有趣，而第二个例子是解不定方程，解不定方程技巧性很强，但用计算机进行枚举搜索却比较容易，学生也易于理解。,(2)解析算法。 将问题归结为数学表达式，并通过计算机来实现问题求解，是学生较易接受的。困难点可能是如何归结出表达问题的数学表达式。 (3)排序和查找算法。 “排序和查找”在学校学习中被大量运用，学生会排序，但不知道如何用计算机来排序；用计算机检索资料对有些学生来说是轻而易举的事，但他们可能不知道资料为什么会这么快被查到。这里面就有一个知其所以然的问题。,
7、Kunth在他的计算机程序设计的艺术的第3卷整卷探讨了这两种算法，可见其重要性。有专家称这两种算法是“使用频率最高的算法”。 (4)递归算法。 这种算法应用很广泛，它是一个把较大规模的问题逐次简化为一个简单易解问题的一般算法。递归就使程序调用自身。教材以计算n!为例来说明递归算法。,3.教学实施建议,(1)按教材编写顺序进行教学。 这确实是一种新的尝试，突出了算法思想，但由于在第三章学习前较难安排上机实践，会使学生感到不适应。为此，我们为教材配套了光盘，其中附有全部实例的算法执行过程(流程图)的演示动画，生动直观，有助理解。 (2)将第二章的“排序”、“查找”和第五章的程序实现结合起来组织教学
8、，这样可使编程和上机的时间提前。,三、计算机处理中的“难”的问题和不可解问题,现实世界中，大量非数值问题在求解时，首先要判定其是否可解。通过建立计算的数学模型（如图灵机、递归函数、-演算、Post系统等）精确区分哪些是可计算的，哪些是不可计算的。但是许多问题本身是不可判定的(如悖论问题、图灵机停机问题等)。只有是可判定、可计算的问题，才能通过精确的算法描述进行求解。 计算的过程就是执行算法的过程。可计算性的核心问题是将算法这一直观概念精确化，变为一个具有有限性、可执行性、确定性、终止性、有限个输入、1个或1个以上输出的具体算法。,现代计算机处理问题的能力确实很强，我们的学习、工作、生活都离不开
9、计算机。这一点经过多年的信息技术课程的学习，学生们都有体会。但是，计算机不是无所不能的，有些问题对计算机来说是很“难”的，有的则是计算机无法解决的。这些在教材中没有写入，而是在教师用书的第三部分作了一些介绍，尽管是浅显的，任课老师读一读有好处，条件较好的学校，可将其中一些思想介绍给学生。,1.多项式问题（P问题）,如果一个问题的规模是n，按某种算法解决问题时用的计算次数是n的多项式，或者说计算的复杂度为O(log n)，O(n)，O(n2)，O(n3)或O(nk)（k为常数），则称该算法为多项式算法，而这类问题称为多项式(P)问题。以当今计算机的处理速度，对于一个有合理输入数量的多项式问题，计
10、算机都能有效地予以解决。 一个问题会有多种算法，算法会有快、慢。例如教材中排序、查找部分，选择排序比冒泡排序快，对分查找比顺序查找快，等等。,2.非多项式问题（NP问题）,有许多问题，当它们的规模变得越来越大时，不管你采用什么算法，求解它所用的时间都会长得惊人。就算是用当今的快速计算机，都无法在可容忍的时间内完成，这就是所谓非多项式（NP）问题。,若问题求解时所用算法的计算时间的阶等价于某种指数函数，或者说算法的复杂度为O(2n)，O(kn) （k为常数）或O(n!)， 则称该算法为指数型算法，而这类问题就是非多项式（NP）问题。非多项式问题远比多项式问题难度大，当问题规模增大时，用计算机处理
11、需要数月甚至数年的时间才能得出问题结果。例如，梵塔问题、货郎担问题、因式分解问题、纵横字谜问题、图形着色问题、棋类博弈问题、可满足性问题等等都是所谓“难”的问题。,3.不可解问题,对这类问题，无法用计算机程序来解决。图灵是较早发现这类问题的人。例如，他提出了“停机问题”就是一个不可解问题。还有很多不可解问题。,小结：,计算机是现代化信息处理工具，“信息”在这里是以有限种符号的有限长序列这种形式所表示的，而“处理”的过程就是按预先编好的程序对这种序列做有穷的变换，以得到一组新的符号序列作为结果。这就是计算机科学中术语“计算”的确切含义。 要计算机去解决某种问题，有三个基本前提：,1.必须把问题形式化,计算机求解的过程就是从表示问题的符号串出发，按规则进行加工，直到得出符合要求的结果(符号串)为止。 就是说，先要建立一个形式系统。规定所用的符号、规则（语法）以及如何用合法符号串来表示问题的意义与处理过程等。,2. 问题必须是可计算的，即一定要有算法。存在着某个算法和找出这个算法是两回事，前者是客观的，后者是人脑和知识的功能。 3. 要用计算机实现一个算法以解决某种问题，问题的复杂度必须是合理的，即要避免指数爆炸。,