信息技术教育中的计算思维

信息技术教育中的计算思维樊磊首都师范大学教育技术系北京师范大学智慧学习研究院[e-mail]……学会运用计算思维对问题进行识别、分析、抽象、建模并设计系统解决方案……--摘自《高中信息技术课程标准修订（草稿）》学科核心素养总目标信息技术教育中的计算思维运用计算机科学领域的思想方法形成解决问题方案的过程中，所包含的一系列思维活动即计算思维。具备计算思维的学生在信息活动中能够采用计算机可以处理的方式界定问题，抽象问题特征，建立结构模型，合理组织数据；通过判断、分析与综合各种信息资源，运用算法设计解决问题的方案；总结利用计算机解决问题的过程与方法，并将其迁移到与其相关的其他问题解决之中。--摘自《高中信息技术课程标准修订（草稿）》学科核心素养部分信息技术教育中的计算思维“计算思维”是信息社会运用信息技术解决问题的主要思维方式，作为人类三大科学思维方式之一，计算思维对学生世界观、人生观、价值观的形成有着重要影响。计算思维的本质是抽象和自动化，在不同的模块课程中有不同的表现形式。任何一种思维方式从形成到内化都需要在解决问题的过程中经过多次运用才能逐步完成。教学时要在各个模块课程中提炼计算思维的具体表现，将思维过程设计为教学中每个范例的主线，每个实践项目的主线，让学生在解决不同问题的情境中，反复亲历思维的全过程，不断运用学科思维，从而达到内化程度。--摘自《高中信息技术课程标准修订（草稿）》教学建议部分信息技术教育中的计算思维计算思维兴起的缘由•从二十世纪七十年代中期开始，在诺贝尔物理学奖得主KenWilson等人的积极倡导下，基于大规模并行数值计算与模拟的“计算科学”（ComputingScience）迅速崛起，并开创了科学研究的第三种范例（理论、实验、计算机模拟）。•计算科学协同其它科学领域，如基因组工程、生物信息学、天体物理等，取得了一系列重大突破性进展，并受到传统科学界的重视和接纳。•1991年，美国联邦政府立法将建立联网的大规模超级计算中心（资源）作为保持美国科学技术领先地位的一项重要措施。•今天我们所熟悉的一些新技术，包括大数据、数据可视化及云计算等均源自于这场运动。•国内很多大学数学学院中的“信息与计算”专业也是在这个时期陆续出现的。计算思维兴起的缘由•这场运动对于“计算机科学”的普及、得到政府决策部门的重视和基金支持起到了一定的推进作用，像之前的“人工智能”一样！•但是，由于相对片面地理解和宣扬所谓的“计算科学”，也带来一些副作用。•至今仍有相当多的人（包括学术界）混淆“计算科学”与“计算机科学”或“信息科学”。计算思维兴起的缘由•更传统意义上的计算机科学（ComputerScience，指围绕计算现象和计算对象的研究）反而受到了冷落甚至质疑。•进入二十一世纪后，美国报考各大学计算机科学及其相关专业的优秀学生数量开始呈明显下降趋势，高规格的科研资助力度和水平有所降低。•这标志学科的影响力和社会认知度出现了危机。计算思维兴起的缘由计算思维兴起的缘由•计算机科学界开始反思，随后大力宣扬自身学科的核心价值。•有关计算思维的探讨和研究就是在这样的背景下产生的。•计算思维旨在倡导一种所谓的“计算机科学家的思维方式”，以区别“逻辑（抽象）思维”、“数学思维”和“工程化思维”等等这些已为学术界普遍认同的思维方式，从而提高社会、学术界、学生及家长对学科的认同。•当前比较系统和典型的观点是由J.Wing（周以真）提出的：ComputationalThinking,COMMUNICATIONSOFTHEACM,Vol.49,No.3,March2006•J.Wing的观点对国内高校的计算机教学颇具影响力。•但有关“什么是计算思维？”的问题仍存争议。计算思维兴起的缘由从算法思维到计算思维•早在二十世纪五、六十年代，就曾提出算法思维的说法，是当时的“算法学家”们为争取将计算机科学从数学中独立出来所进行的努力。•著名计算机科学家D.Knuth（高德纳）1985年在《美国数学月刊》（为美国影响最大、读者群最广的数学杂志）上发表了题为“数学思维与算法思维”的文章。•文章中例举了十个例子，说明算法思维与数学思维解决问题的相同和不同之处。•“算法思维”着重强调在（数学）问题求解过程中算法构造的核心作用。•现代“计算思维”的含义比“算法思维”要更广泛。•计算思维包含了多种抽象层次、发展算法的数学以及对跨越不同尺度问题的算法效率的分析等方面。从算法思维到计算思维（现实世界中的）问题与模型模型现实世界理论数学模型与数学思维数学模型数学概念数学理论自然现象及对象概念关联结构规律计算模型与计算思维计算模型计算概念计算机科学理论自然的及人工的信息处理概念关联结构规律从小处看计算思维XYffXY数学函数观点：强调定义域（输入）和值域（输出）的具体形式，淡化对应本身。算法（流程图）观点：强调如何将输入变换为输出，淡化对输入输出自身的描述（由数据结构来处理！）。•如何防止非正常用户破解密码？•常规的解决方法：使用复杂的密码、限制密码输入次数、限制输入的时间…•关键：防止非法用户利用计算机快速尝试不同的密码。•计算思维的解决方法：只有人能做好但计算机做不好的。日常应用中的计算思维日常应用中的计算思维•CAPTCHA=CompletelyAutomatedPublicTuringTeststoTellComputersandHumansApart•图灵测试的一个现代的、简单的直接应用！•图灵测试的初始目的是给“机器智能”下一个定义。•这个小应用与图灵提出“测试”的本意相差甚远。整数乘法的计算问题•使用标准的乘法算法，两个n位整数相乘的“计算量”大致上与n2成正比。•用计算理论的术语说：两个n位整数乘法的“计算复杂度”为O(n2).•例如，两个10000位整数乘法大约需要1000010000=1010次标准运算。•对于“大”整数（如1010位以上级别的）的乘法，这个复杂程度是不可接受的。关于算法效率的一个非平凡例子•1971年，基于著名数学家高斯在十九世纪的一个古老的思想，计算机科学家们设计出一种快速的乘法算法，其计算复杂度为O(nlognloglogn)•这个算法每年节省的计算资源价值数以百亿元！关于算法效率的一个非平凡例子•例如，Web上总共大概有1011个页面，做一次关键词搜索要做多次10111011阶矩阵的乘法，这个计算量约为1025次标准计算单位。•假设计算机每秒计算1015次（这已经超过了当前最快的计算机数百万倍了），那么做一次搜索就需要大概1010秒。•使用快速乘法算法，计算量大约只有大约1012次！关于算法效率的一个非平凡例子大问题中的计算思维•公钥密码学–素数判定与大数分解•身份认证问题–图着色问题（NP难解问题）•网页排名问题–稀疏矩阵的计算•大数据时代的个人隐私保护用计算思维解决问题的一个非平凡例子•在网络上如何向某个实体证实自己的身份？•这称为身份认证问题。•关于这个问题已经有大量的研究和解决方案。用计算思维解决问题的一个非平凡例子•真正难做到的是：既要证实身份，同时不透露与身份有关的任何有价值的信息。•这能做到吗？•如果不改变观念，肯定做不到!•“隐含假设”是定势思维最常见的现象之一。•假设了验证过程要一次完成。•假设了一方只能问、另一方方只能答。•假设了验证结果的绝对性。零知识认证问题一方（证明者）在不暴露任何有用信息的前提下，向另一方（验证方）证明她知道一个秘密。•1985年由以色列计算机科学家ShafiGoldwasser等人首先提出。•Goldwasser获得2012年度图灵奖。Goldwasser的突破性思想很大程度上基于去掉三个隐含的不必要假设。去掉隐含假设后对答案的要求有显著变化。•验证过程不必一次性完成，可以进行多步验证，每一步只验证一个微小的部分。•求证方和证明方可以进行任意对话。•不强求绝对的“零”知识，只要求在每一步“几乎”是零知识的，而累积的结果不随着步骤的增多而加大。零知识认证问题–一个简化的版本证明者A向验证方B证明她有暗道内双面门的某一侧的钥匙，但不能透露是哪一面的钥匙（秘密）。•两个关键因素：重复及随机性！•重复逐渐降低了A恰好蒙对的可能。这称为Quisquater-Guillou-Berson零知识协议。这是所有可能中最简单的情况，因为涉及的知识仅有1位。原始论文发表于1989年，标题为“写给婴儿的零知识协议”。•A先进入暗道走到岔道处。•B进入暗道到达岔道处，同时A从自己有钥匙的那一侧到达门口。•B要求A从左侧或右侧出来。•重复上述步骤，直到B确信A的确有一把钥匙。入口岔道双面门零知识认证问题A向B证明:她可以使用三种不同的颜色将某个图的顶点着色，使得相邻顶点的颜色不同。这个问题的理论依据是：你可以快速生成一个着好色的图。但反之，给出未着色的图，没有简单方法能迅速找出着色。这个问题涉及的知识可以任意多，而知识的多少依赖于图的复杂程度。零知识认证问题–Goldwasser的解答A准备三幅着色好的图，每幅图之间的差异在于同一个顶点上的颜色相互替换。B看到翻开顶点的着色情况后退出房间，A再换一张图重复前面的步骤。每次B都看到正确的着色结果，重复足够多次后，不得不相信A的确知道如何正确着色。A随机选择其中一幅图，用纸杯盖住所有的顶点。B进入房间，可一次性任意选择两个相邻的顶点翻开纸杯查看。一组人通过各自拥有的私秘信息共同产生一个可共享的信息信息，但在过程中不能向其他人透露出其个人秘密。协同共享问题协同作业在现代网络环境中非常重要，协同作业中的隐私信息保密是巨大的难题。三个人希望计算出其体重之和，但不希望其他两人知道自己的体重。这个能做到吗？•计算过程不必一次完成，可以进行多步计算，每步只计算一个微小的部分。•三方均可以与任意其他人进行对话。•不强求绝对不泄漏，只要求在每步计算时，信息极少透露。•计算结果知识泄漏的累积不随步骤的增多而加大。1.每人随机选择0到1000之间的两个数，然后再选择出第三个数，使得三个数之和模1000后恰好是自己的体重。2.每人将随机选择的两个数分别发送给其他两人。4.每个人将三个人的体重数相加后再模1000后得到的余数就是三人的体重之和。3.每人将自己的第三个数与接收到的其他人的共享数相加，并将结果模1000。协同共享问题一个思考题在ATM机上操作时需要完整正确输入密码。能否不用输入密码，就让ATM机（验证方）相信你的确知道密码？•这个过程有巨大的安全隐患。•请你找出其中的主要安全隐患。暂且不考虑是否实用。计算思维与数学思维的关系•关注的对象不同•关注的问题不同•都有多级抽象层次•数学方法是证明或研究算法问题的工具•计算思维会反作用于数学（这点非常关键！）•计算的方法也可以成为数学研究的工具（数学实验、实验数学）什么是计算思维？•计算思维的实质是将问题表征为关于某种计算模型的信息处理，并在此基础上寻求问题的算法解。•依问题的情况可能需要发现新的计算模型或修改现有的模型。•计算思维对每个人来讲都是基本技能，不仅仅是对计算机专家。•在人的基本能力构成上，除阅读、书写、算术外，还应加上计算（思维）。•印刷出版促进了阅读、书写、算术能力的普及，而计算机促进了计算思维的普及。计算思维的特征•概念化和抽象化-不仅与编程能力有关，计算机科学也不仅是计算机编程。“像计算机科学家一样思考”，其含义比能够编程要更深刻，需要不同抽象层面的思考。•不能靠死记硬背积累-现代社会中每个人都必须具备的一种基本技能。•计算思维是人类（而不是计算机）解决问题的一种思维方式，它不是试图让人类像计算机一样思考。计算思维的教育价值•计算思维与数学思维和工程思维互补。•计算思维是思想，不是软硬件制品或工具。•计算思维是我们用以处理和求解问题、管理日常事务、与他人通信及交互的“计算概念”框架。•计算思维是指导计算机科学教育、研究者及实践者的大一统视界，与人类思维密切集成。•计算思维作为高中信息技术学科的核心素养之一，不仅可行，而且必需。•计算机科学的核心价值在于计算能够做些什么（计算理论）、如何做（算法）、能做