在算法设计与分析课程教学中融入计算思维
Abstract： Basic teaching contents of design and analysis of algorithms is introduced. Proceeding with the computational thinking――one of three scientific thinkings that have promoted human civilization and scientific development， the importance of computational thinking is stated. Finally， some suggestions for integrating computational thinking into teaching of design and analysis of algorithms are proposed.
Key words： design and analysis of algorithms；computational thinking；teaching innovation
中图分类号：TP301.6 文献标识码：A 文章编号：1006-4311（2016）08-0245-03
0 引言
思维能力对人类生活和科技发展的关键意义不言而喻。近年来，计算思维在计算机科学教学中的重要意义得到了普遍关注，众多学者和组织参与了这一思想的讨论和传播。然而，如何合理设置课程体系，科学地落实培养过程，在教学中真正使学生的计算思维能力得到培养，我们依然面临着严峻的挑战。本文介绍了算法设计与分析课程的一般框架和计算思维的思想，并就如何在该课程教学中融入计算思维提出一些建议，希望引起更多专业人员进行探讨，并引起重视。
1 算法设计与分析
计算过程的效率和计算结果的准确性是古老的研究课题。科学技术的发展使得人们一方面更容易获得大量的信息，另一方面对这些信息的处理（计算）方法变得日趋复杂，计算量也越来越大。许多理论上可以计算的问题，由于计算过程中所需空间或者时间的限制，而变成了现实不可计算的问题，造成了虽然理论上可计算但现实条件不允许的矛盾。自20世纪中期以来，随着各个领域算法研究工作的发展，诞生了一个新的研究领域，即算法的设计与分析。这一领域的研究成果不仅对不同学科问题提供了有效的解决方法，而且提供了一种独特的处理问题的思维方式。
由于实际问题求解的需求以及算法的广泛应用，算法研究领域已是包罗万象。从最初的排序、查询、图算法、数值计算等，到信息处理、工程计算与模拟、金融分析、生物计算、量子计算，以及最前沿的大数据分析，计算机的应用无处不在，算法的应用也无处不在[1-5]。按照算法所处理的对象进行分类，算法设计与分析主要包括数值算法和非数值算法两大领域。数值算法主要有多项式计算、矩阵计算、有限域计算、数论计算，方程（组）求解，优化计算等，非数值算法主要有排序、搜索、几何问题的计算、离散结构的计算、模式匹配等。按照计算时所需数据的提供情况可分为离线算法和在线算法，前者是指计算中所需数据在计算开始时已全部提供，后者指计算开始时不提供或部分提供数据，然后在计算过程中逐步提供数据，其典型的应用是股市风险和效益的评估分析。按照计算方式进行分类，则可分为串行算法和并行算法，还可以分为智能算法、近似算法、随机型算法、交错型算法、非确定型算法、确定型算法等。
算法设计的任务是对各类具体问题设计高质量的算法，以及研究设计算法的一般规律和方法。常用的算法设计方法主要有回溯法、贪婪法、分治法、概率方法和近似方法等[6]。算法分析的主要任务则是对于所设计的每一个具体算法，讨论它的时间和空间复杂度、相关概率、近似比和竞争比等，分析的结果既可作为评价算法质量的标准，也可为改进算法提供参考方向。
由于算法设计与分析在计算机学科中的重要地位，其基本内容已经成为计算机相关学科的一门专业核心必修课程。算法设计与分析课程的教学方式、内容和质量，必须能够确保培养学生的学习兴趣，提高学习效果，以便提高学生专业能力和综合能力的培养，为学生高水平高层次应用和发展提供保障。
2 计算思维
计算思维是多种学科学习和研究人员所必备的基本素质，甚至与人们的生活也密切相连。科学界一般认为，计算思维、实验思维和理论思维是推动人类文明进步和科技发展的三大科学思维方式。近些年，诸多学者从计算思维的定义、内容、特点和培养方式等多方面进行了探讨。计算思维能力包括抽象能力和逻辑思维能力，必须经过系列数学和抽象程度较高的理论课程渐进、系统地训练才能形成[7]。2006年，原美国卡耐基?梅隆大学计算机系主任，现美国基金会计算机和信息科学与工程部主任周以真（Jeannette M. Wing）教授在国际权威杂志上发表文章，明确了计算思维的一般定义：“计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动”。在此基础上周教授对计算思维给出了更详尽的描叙（或定义），对计算思维是什么，或不是什么的特征给出了界定，指出了计算思维是每个人的基本技能，不仅仅属于计算机科学家[8]。
计算思维这一概念提出后，立即引起了国际计算机界的广泛关注，已经成为当今社会计算机教育研究的重点课题，美国教育界对此给予了大力支持，卡耐基?梅隆大学成立了专门的课题进行研究，很多相关组织和团体都参与了这项研究，比如美国数学研究所（AIM）、美国国家计算机科学技术教师协会（CSTA）、美国计算机协会（ACM）等，不仅如此，计算思维还有效促进了美国国家科学基金会（NSF）重大基金资助计划CDI（Cyber-Enabled Discovery and Innovation）的产生，CDI计划旨在使用计算思维产生的新思想、新方法，促进美国自然科学和工程技术领域产生革命性的成果，CDI的最终研究成果将使人们的思维模式发生转变。而这种转变不仅延伸到了美国国家自然科学与工程，也体现在了社会经济与技术等各个学科领域。同时，计算思维的影响也逐渐从美国延伸到了英国的教育界，在英国的爱丁堡大学开展了很多与计算思维相关的研讨会，重点讨论了计算思维对不同学科的影响，比如教育、建筑、医学、生物、物理、哲学等。此外，英国的计算机学会也组织了相关学者对计算思维进行研讨，提出了欧洲的行动纲领。 国内为了紧跟国际学术的研究步伐，加紧更新传统的教学理念，开展了多次计算思维的专题研讨会，参会团体包括全国各高等学校计算机教育研究组织等。研讨内容主要包括如何以课程为载体讲授面向学科的思维方法，以及这种讲授对国家科学与教育事业发展的作用等。2010年7月，九所知名高校在西安交通大学举办了“C9高校联盟计算机基础课程研讨会”，这九所知名高校分别是西安交通大学、哈尔滨工业大学、中国科枝大学、南京大学、上海交通大学、浙江大学、复旦大学、清华大学、北京大学。教育部高等学校计算机基础课程教学指导委员会主任陈国良院士，作了“计算思维能力培养研究”的报告，并主持了该专题的讨论。经大会研究讨论后就增强大学生计算思维能力的培养发表了“九校联盟（C9）计算机基础教学发展战略联合声明”，声明中强调“旗帜鲜明地把‘计算思维能力的培养’作为计算机基础教学的核心任务[9]”。《中国大学教学》连续发表有关计算思维的文章，一批知名学者如陈国良、李廉等积极参与这一思想的阐释与推广[10，11]，对计算思维的理解、普及和应用，进一步对计算机学科的教学发展起到了积极的推动作用。
计算思维并不是要求人类像计算机那样思考，它只是人类求解问题的一条途径。计算机拥有强大的计算能力，人类拥有了计算机，也就拥有了强大的计算能力，人类应该学会利用这种力量去解决更多的问题。当今社会计算机几乎无处不在，计算机科学的出现不仅给人类带来了便利，更重要的是计算的概念，它被人们用来求解问题、管理日常生活以及与他人进行交流和互动。计算思维无处不在，作为一个解决问题的有效工具，人人都应掌握，处处都会被使用。因此计算思维应当是当前计算机教育需要继续重点研究的课题，而且应当有效地融入到我们的课程教学之中。
3 算法设计与分析教学中融入计算思维
有研究指出，计算思维作为一种工具，应当被所有学校的所有课堂教学采纳。采用这个工具，自然会面临以下几个问题：
①人所固有的能力与局限性？计算机的计算能力与局限性？②问题解决的判定条件是什么？③问题到底有多复杂？④什么样的技术能被应用于当前的问题求解或讨论之中？⑤什么样的计算策略更有利于当前问题的解决？
对于前两个问题，计算理论课程做了较好的解释[12]。后三个问题则应该是算法设计与分析课程重点解释的内容。由于计算思维的重要性，结合多年算法设计与分析的教学经验，笔者认为在算法设计与分析教学改革中，必须要将计算思维的培养融入到教学当中，在教学中不能局限于知识的传授，而应该注重学生思维的培养，以提高学生的创新能力。具体在教学中应该注意以下几点：
①算法教学应脱离具体的程序设计语言。算法独立于具体的计算机和具体的程序设计语言。虽然算法的最终具体实现需要某一种具体的编程语言，例如C++、Java等，但这些编程语言只是一种实现工具。教学中应避免把算法课变成程序语言和程序设计的教学课程。对算法的描述应主要通过某种伪代码、甚至可以是自然语言的形式。这样的算法描述更为直观、清晰、易懂，并使得教师的教学和学生学习专注于算法的概念和计算思维的培养，而不是具体应该如何编程实现某一段代码。
②复杂性理论应作为教学重点内容。计算复杂性理论是理论计算机科学的分支学科，使用数学方法对计算中所需的各种资源的耗费作定量分析，并研究各类问题之间在计算复杂程度上的相互关系和基本性质，是算法分析的理论基础。该理论回答了一个问题到底有多复杂，并指导选择和设计解决问题的策略。而目前在教学过程中，由于教材通常将复杂性理论部分放在教材的最后章节，由于学时等因素，对复杂性理论的教学不够重视。而复杂性理论是培养计算思维及对各种算法深刻理解的必备基础。所以复杂性理论在教学中应该适当提前，并作为教学的重点内容。
③教学中应注重培养学生解决问题的思维能力。在各种算法的具体教学过程中，教师应该注重培养学生面对问题时的解决办法。例如人们往往首先通过猜测，然后经过验证、证明、分析、完善等过程，最终解决一个问题。这个过程也是人们探究真理的常见过程。在这个过程中培养学生科学的分析问题、逻辑推理、抽象概括能力，往往要比单纯地讲解某一种算法有更大的意义。逻辑推理是依据一定的逻辑规则，从已知项得出未知项，或用已知项来解释未知项。抽象是抽出事物的本质属性或特征的过程。概括是在抽象的基础上，把抽取出来的那些本质属性归结在一起进行考察的思维方法。这些都是解决问题、探讨概念、发现事物规律的重要基本工具，任何一个算法思想的产生都离不开推理、抽象和概括。对这些思维能力的训练和培养是大学计算思维和通识教育的重要组成部分。
④算法思想应渗透在整个教学课程中。发展层次理论认为思维是多层次的，逐步发展的过程。发展层次的最高层次是严密性或公理性，算法教学时应有意识地朝着这一方向努力。很多算法的提出往往都基于某一个实际的、有趣的问题。在教学过程中可以为学生设置不同的问题情境，有意识的培养学生多角度思考问题的能力。现实生活中通常问题的解决方式都不是唯一的，在教学过程中应有意识的培养学生的算法思想，引导学生用不同的解决方法面对不同问题，甚至是同一个问题，从而加深学生对算法思想的理解，并在解决问题的过程中体会到算法思想的意义和作用，真正意识到算法思想的重要性。
4 结束语
计算思维已经和人们的生活和各种密不可分，甚至成为了一项重要的生存能力。当今的信息社会已经离不开计算机，如何培养具有计算思维的新型人才，变成了时代向教育事业提出的课题。国家要求高校必须重视并加强大学生创新能力的开发和培养，而计算思维中蕴含了强大的创新能力，培养计算思维能力的最高目标就是为了创新[8]。但是，目前还缺少如何培养学生计算思维的系统方法。针对这一问题，本文对算法设计与分析课程教学中如何融入计算思维做了一些讨论。但这方面仍然需要很多非常艰巨的工作，例如算法设计与分析教学课程体系、教学内容、实践体系、教材等方面还需要进一步的实践与探索。希望我们的工作，为全国算法设计与分析课程教学的建设、改革探路，为国家培养拔尖创新人才做出贡献。
