关于第二个问题主要应讲清楚以下内容:(1)3种遍历算法对二叉树的遍历过程几乎一样,惟一的区别在于对根节点的访问时间不同;(2)每个节点都要经过3次,而不是想像中的1次,只不过每个访问进行了1次;(3)3种算法可以简单区别如下:如果是第一次经过就访问,就是先序遍历;如果是第二次经过时访问,即左子树返回时访问,就是中序遍历;如果是第三次经过时访问,即右子树返回时访问,就是后序遍历的算法。
2.二叉树遍历算法的扩充
一个填充3个访问时机的算法描述如图1所示。可以看到,语句3、语句5和语句7分别对应于第一次访问、第二次访问和第三次访问的时机。我们用灰色的语句表示其位置,具体的算法中可能没有真正的语句,但其位置是存在的。
3.二叉树遍历的图形表示
4.二叉树遍历算法的展开
二叉树的先序遍历过程。可以看到,二叉树中每个指针都执行了一次preorder。由于二叉树的节点是4个,因此共有4*2=8个指针域,于是preorder函数会执行8次。这一点对于理解二叉树遍历算法非常重要,学生往往混淆的就是空指针的情况,他们认为空指针不需要调用遍历过程。
可以清楚看出,该二叉树中的4个非空的节点进行遍历时执行了visit过程,该过程的时间顺序即为先序遍历的顺序。对4个空指针的处理,可以看出它们也调用了preorder过程,只是应为调用时参数中指针为空,所以经过语句1进入函数,在语句2进行的判断中知道该指针为空,于是控制跳过语句3、4、5,然后经过语句6和7,最后针对该节点的子树遍历结束。
其他两种遍历的顺序也可以以同样的方式表达出来,惟一的区别在于visit的执行时间不同。正是这个访问时间的不同,导致不同的遍历算法。
三、教学效果检验
为检验上述教学方法的效果,考虑给出的算法。(a)中二叉树根节点的指针,要求写出其遍历顺序。显然,该算法不是3种算法中的任何一种。不少学生对这类问题束手无策,原因主要在于没有真正理解算法。
(a)算法(b)执行过程
如果应用本文的方法,将会很快得到问题的答案。多数同学能较快地通过图形方式给出正确的解答。
下面我们将其展开。该算法中语句4和语句6实现对根节点的访问,它们分别对应第二次和第三次访问的时机。显然,每个节点需要访问2次,分别是左子树返回时和右子树返回时的情况。
算法的具体执行过程分析,完整的执行步骤如下:1→2→3[1→2→3[1→2→7→8]→4(B)→5[1→2→3[1→2→7→8]→4(D)→5[1→2→7→8]→6(D)→7→8]→6(B)→7→8]→4(A)→5[1→2→3[1→2→7→8]→4(C)→5[1→2→7→8]→6(C)→7→8]→6(A)→7→8。依次记录所得符号,即为算法结果:BDDBACCA。
四、总结
遍历二叉树的实质是对二叉树的线性化过程,即遍历的结果是将非线性结构中的节点排成一个线性序列。遍历是二叉树中的重要操作,是很多其他操作的基础。本文对二叉树遍历的教学过程进行了探讨,提出一些有用的教学方法,实践表明,它们的使用可以取得较好的教学效果。
计算机专业本科生计算思维能力的培养
陈文宇欧齐
【摘要】计算思维能力是指形式化描述和抽象思维能力以及逻辑思维方法。本文论述了计算机专业本科学生计算思维能力培养的重要性。计算理论是研究计算机解决计算问题的数学理论,对于计算思维能力的培养具有重要作用,本文提出计算理论系列课程教学需要重视的问题。
【关键词】计算思维能力计算理论
计算机科学与技术学科强调4个方面的专业能力:计算思维能力,算法设计与分析能力,程序设计与实现能力,计算机系统的认知、分析、设计和运用能力。这也是计算机科学与其他学科的重要区别。相关的理论是计算机学科的基础。理论方面的知识是计算机的真正灵魂。理论是从计算机应用当中抽象出来的,目的在于使用抽象出来的理论去更好地指导实践[1]。
在本科阶段的学习过程中,学生以观察、描述、比较、分类、推断、应用、创造性思维等科学思维过程为主,强调自学的能力培养。
建立物理符号系统并对其实施等价变换是计算机学科进行问题描述和求解的重要手段。“可行性”所要求的“形式化”及其“离散特征”使得数学成为重要的工具,而计算模型无论从方法还是从工具等方面,都表现出它在计算机科学中的重要作用。
计算机科学与技术学科要求学生具有形式化描述和抽象思维能力,要求掌握逻辑思维方法。这种能力就是计算思维能力或计算机思维能力。
计算机学科系统地研究信息描述和变换算法,其中包括信息描述和变换算法的理论、分析、效率、实现和运用。学科的根本问题在于:什么能被(有效地)自动化?学科的重要内容之一是研究计算领域中的一些普遍规律,描述算法的基本概念与模型。
计算思维能力的培养,不是靠一两门课程就可以实现的,它需要计算理论系列课程的学习,并且通过长期的培养才能实现。
一、计算思维能力的培养
计算思维能力的培养主要是通过基础理论系列课程来实现的,该系列课程由数学和抽象度较高的理论课程组成,包括《数学分析》、《集合和图论》、《离散数学》、《数学建模》、《计算理论》等课程。它们构成了对学生计算思维能力培养的一个阶梯训练系统。
在此系统中,连续数学、离散数学、计算模型三部分内容按阶段分开。三个阶段对应计算机学科的学生在本科学习期间的思维方式和能力变化的三个步骤,使得学生的计算思维能力不断提高。
在中学阶段所学的数学,研究的是具体的、静止的对象的计算。到了数学分析阶段,通过连续变量和函数,将运动带入了考虑的范围中,到离散数学阶段,开始考虑基本运算系统,该系统更加抽象,更具一般性,所考虑的计算对象具有更明显的抽象和离散的特征。到计算理论阶段,所考虑的运算对象是更高级别上抽象出来的形式化特征,而运算也呈现出模型化的特征。计算从孤立的、单一的计算演变成为一般、形式化的计算,而一般、形式化的计算,正是计算机科学所要研究的计算。
考虑的计算对象不同,所需要的思维方式和能力就有所不同,正是通过系列课程的学习,在不断升华的过程中,逐步培养出学生的抽象思维能力和逻辑思维方法;同时,创新意识的建立和创新能力的培养也在学习过程中不断进行。系列课程是对学生进行思维能力培养的最佳知识载体。
本科生的适应能力以及创新能力在很大程度上取决于坚实的理论基础和专业基础知识,这是高质量本科生教育的重要特征之一。在当今计算机科学技术突飞猛进、专业知识日新月异的时代,只有扎实掌握专业的计算机理论基础,才有可能从事这个专业所进行的科研、教学和其他专业技术工作,才能打好进行创造性研究的基础。因此,对理论课程的学习就显得尤为重要。
二、计算理论是研究计算问题的数学理论
计算理论是研究使用计算机解决计算问题的数学理论,有3个核心领域:形式语言与自动机理论、可计算性理论和计算的复杂性理论。可计算性理论的中心问题是建立计算的数学模型,进而研究哪些是可计算的,哪些是不可计算的。计算的复杂性理论研究算法的时间复杂性和空间复杂性。在可计算性理论中,将问题分成可计算的和不可计算的;在复杂性理论中,目标是把可计算的问题分成简单的和困难的。形式语言与自动机理论在本科阶段学习,而可计算性理论和计算的复杂性理论在研究生阶段学习。
形式语言与自动机理论论述计算的数学模型的定义和性质,这些模型在计算机科学的若干应用领域中起着重要作用,其应用范围已被扩展到生物工程、自动控制系统、图像处理与模式识别等许多领域。
形式语言与自动机理论是学习计算理论的良好起点,不仅能提高学生的感知能力,同时也能提高学生思维的敏捷性,使学生考虑问题仔细、严谨、周密、有理有据;可以使学生由具体形象思维逐渐向抽象思维过渡,从而促进逻辑思维和创造力的发展;可以使学生的逻辑思维过程清晰化、条理化、整体化,有利于培养学生的计算表达能力,提高推理、判断、分析问题和解决问题的能力。
三、形式语言与自动机理论的学习
计算机专业的本科生学习形式语言与自动机理论,既要知其然,更要知其所以然。学习的目的应该是:将抽象的理论再应用于实践,不但要掌握题目的解题方法,更要掌握解题思想,对于定理的学习,不是简单地应用,而是掌握证明过程即掌握定理的由来,训练自己的推理能力。只有这样才达到了学习这门科学的目的,同时也缩小了与数学专业的学生之间思维上的差距。
将科学思维过程融入学生的知识结构之中,加强知识结构形成的教学。思维能力是在知识的掌握和运用中发展起来的,思维能力的培养离不开知识,而影响学生学习最根本的因素是学生头脑中原有的知识结构。因此,在形式语言与自动机理论教学中,当学生深刻理解新法则后,要精心设计课程练习,引导学生通过比较、观察,帮助他们把新法则纳入到原有法则系统中,构成紧密联系和融会贯通的知识网络。这样,学生思维的概括性也得以发展。
形式语言与自动机理论并不神秘,也不令人厌烦,而是容易理解,甚至是有趣的。形式语言与自动机理论中包含有许多迷人而重要的思想,要体会、感悟思想的闪光点,并且体会大师们当初发现这些思想而获得的极大乐趣。同时,它也有许多细小的、有时是枯燥乏味的细节,这些细节才是可能让学生感到厌倦的地方。理论课程的学习是一件艰苦的工作,应该抓住思想,而不要陷入细节的单调乏味之中。
理论课程的教学,最大的问题有两个:一是内容高度的抽象,导致教材和参考书的阅读十分枯燥,而且理论的作用主要是在潜移默化中体现出来的,在一点一滴地影响着思维,难以直接地、立即地找到理论的使用;二是内容具有较大的难度,不容易找到体验感性认识的具体实例,不容易发现相关理论知识点的来龙去脉,达到深入理解的目的。要解决这两个问题,必须掌握问题求解的思想和方法,并且通过对它们的研究,来领略理论在高度抽象和形式化下的优美和乐趣,使这些枯燥的内容鲜活起来,使自己能够创造“思路”和“想法”。这也是人们在科学研究中创造性发现的来源。
四、结束语
在本科生阶段,需要加强理论计算机基础理论的学习。形式语言与自动机理论课程的学习,除了在计算机科学与技术领域得到直接应用外,更在计算机科学与技术领域人才的计算思维能力的培养中占有极其重要的地位。
体验英语英语体验
——《体验英语》基本理念再诠释
熊宣东王大庆
【摘要】由高等教育出版社出版的《大学体验英语》系列教材注重实用能力的培养;注重教材的可操作性;强调以人为本,突出“个性化”学习;重视文化知识的学习,培养“跨文化意识”;立体化教材的“超文本化”理念,真正实现了《大学英语》教学的“个性化”、“协作化”、“模块化”和“网络化”,是对“任务教学法”理念的最佳诠释。
【关键词】个性化“跨文化”意识超文本化协作化模块化任务教学法