算法与程序设计浙教版教材介绍市公开课一等奖百校联赛特等奖课件.pptx

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