《计算思维-概念、特征与启示(樊磊)》由会员分享，可在线阅读，更多相关《计算思维-概念、特征与启示(樊磊)（26页珍藏版）》请在金锄头文库上搜索。
1、计算思维计算思维 - 概念、特征与启示概念、特征与启示樊 磊首都 师 范大学 教育技 术 系计算思维兴起的缘由 从二十世纪七十年代中期开始，在诺贝尔物理学奖从二十世纪七十年代中期开始，在诺贝尔物理学奖得主得主 Ken Wilson等人的积极倡导下，基于大规模并等人的积极倡导下，基于大规模并行数值计算与模拟的行数值计算与模拟的 “计算科学计算科学 ”（ Computing Science）开创了科学研究的第三种范例（理论、实）开创了科学研究的第三种范例（理论、实验、计算机模拟）。验、计算机模拟）。 计算科学协同其它科学领域（如基因组工程、天体计算科学协同其它科学领域（如基因组工程、天体物理等等）
2、取得了一系列物理等等）取得了一系列 重要重要 的突破性的突破性 进展进展 ，受到，受到传统科学界的重视和接纳。传统科学界的重视和接纳。 1991年，美国联邦政府立法将建立联网的大规模超年，美国联邦政府立法将建立联网的大规模超级计算中心（资源）作为保持美国科学技术领先地级计算中心（资源）作为保持美国科学技术领先地位的一项重要措施。位的一项重要措施。 今天我们所熟悉的大数据、可视化及云计算等等今天我们所熟悉的大数据、可视化及云计算等等均源自于这场运动。均源自于这场运动。 国内很多大学数学学院中的国内很多大学数学学院中的 “信息与计算信息与计算 ”专业也专业也是在这个时期出现的。是在这个时期出现的。
3、 这场运动对于这场运动对于 “计算机科学计算机科学 ”的普及和得到政府决的普及和得到政府决策部门的重视起到了一定的推进作用（像之前的策部门的重视起到了一定的推进作用（像之前的 “人工智能人工智能 ”一样！）。一样！）。 由于相对片面地理解和宣扬所谓的由于相对片面地理解和宣扬所谓的 “计算科学计算科学 ”，也带来很多副作用，至今学术界仍有相当多的人也带来很多副作用，至今学术界仍有相当多的人混淆混淆 “计算科学计算科学 ”与与 “计算机科学计算机科学 ”（或（或 “信息科学信息科学 ”）。）。计算思维兴起的缘由 更传统意义上、更广义的计算机科学（更传统意义上、更广义的计算机科学（ Computer
4、 Science，指围绕计算现象和计算对象的研究）受，指围绕计算现象和计算对象的研究）受到冷落甚至质疑。到冷落甚至质疑。 进入二十一世纪后，美国报考各大学计算机科学进入二十一世纪后，美国报考各大学计算机科学相关专业的优秀学生数量开始呈明显下降趋势，相关专业的优秀学生数量开始呈明显下降趋势，高规格科研资助的力度和水平降低，这标志学科高规格科研资助的力度和水平降低，这标志学科的影响力和社会认知度出现了危机。的影响力和社会认知度出现了危机。 计算机科学界开始再次反思并宣扬自身学科的核计算机科学界开始再次反思并宣扬自身学科的核心价值，有关计算思维的探讨和研究就是在这样心价值，有关计算思维的探讨和研究就
5、是在这样的背景下产生的。的背景下产生的。计算思维兴起的缘由 “计算思维计算思维 ”旨在倡导一种所谓的旨在倡导一种所谓的 “计算机科学家的计算机科学家的思维方式思维方式 ”，以区别，以区别 “逻辑（抽象）思维逻辑（抽象）思维 ”、 “数学思数学思维维 ”和和 “工程化思维工程化思维 ”等等 等等 这些这些 已为学术界普遍认同已为学术界普遍认同的思维方式的思维方式 ， 从而从而 提高提高 社会、学生及家长对学科社会、学生及家长对学科的认同。的认同。 比较系统和典型的观点是由比较系统和典型的观点是由 J. Wing提出的：提出的：Computational Thinking, COMMUNICATI
6、ONS OF THE ACM, Vol. 49, No. 3, March 2006 J.Wing的观点在国内也颇具影响力。的观点在国内也颇具影响力。 有关有关 “什么是计算思维？什么是计算思维？ ”的问题仍存争议。的问题仍存争议。计算思维兴起的缘由从算法思维到计算思维 早在二十世纪五、六十年代，就提出了算法思维的早在二十世纪五、六十年代，就提出了算法思维的说法，是当时的说法，是当时的 “算法学家算法学家 ”们为争取将计算机科学们为争取将计算机科学从数学中独立从数学中独立 出来出来 所进行所进行 的的 努力努力 。 著名计算机科学家著名计算机科学家 D.Knuth（高德纳）（高德纳） 1985
7、年在年在 美国数学月刊美国数学月刊 （为美国影响最大、读者群最广的（为美国影响最大、读者群最广的数学杂志）上发表了数学杂志）上发表了 “数学思维与算法思维数学思维与算法思维 ”的文的文章。章。 “算法思维算法思维 ”着重着重 强调在强调在 （数学）问题求解过程中算（数学）问题求解过程中算法（构造！）的核心作用。法（构造！）的核心作用。 现代现代 “计算思维计算思维 ”的含义比的含义比 “算法思维算法思维 ”要广泛得多，要广泛得多，包含了多种抽象层次、发展算法的数学以及跨越不包含了多种抽象层次、发展算法的数学以及跨越不同尺度问题的算法效率问题的分析等方面。同尺度问题的算法效率问题的分析等方面。模
8、型与（现实世界中的）问题模型现实世界 理论数学模型与数学思维数学模型数学概念 数学理论抽象自然现象及对象建模应用概念关联 结构规律计算模型与计算思维计算模型计算概念 计算机科学理论抽象自然的及人工的信息处理建模应用概念关联 结构规律小问题中的计算思维 CAPTCHA = Completely Automated Public Turing Tests to Tell Computers and Humans Apart 图灵测试的一个现代简单直接应用！图灵测试的一个现代简单直接应用！ 图灵测试的目的是给机器图灵测试的目的是给机器 “智能智能 ”下一个定义，这个小小的下一个定义，这个小小的应用与
9、图灵提出应用与图灵提出 “测试测试 ”的本意相差甚远。的本意相差甚远。整数 乘法 的计算量问题 两 个 n 位的整数相乘的 “计算量 ”大致上与 n2成正比。 用计算理论的术语说：两个 n 位整数乘法的 “计算复杂度 ”为 O(n2). 例如，两个 10000位整数乘法约需要 10000 10000 = 1010次标准运算。 对于大整数（如 1010 位级别的）的乘法，这个复杂程度是不可接受的（为什么？）。 1971年，基于 Gauss在十九世纪的一个古老的思想，由计算机科学家们设计的快速乘法算法，其计算复杂度为O(n log n log log n) 这个算法每年节省的计算资源价值数以百亿元
10、！小问题中的计算思维小问题中的计算思维X YffX Y数学函数数学函数 观观 点：点： 强强 调调 定定 义义 域（域（ 输输 入）和入）和值值 域（域（ 输输 出）的具体形式，淡化出）的具体形式，淡化 对应对应 本身。本身。算法（流程算法（流程 图图 ） 观观 点：点： 强强 调调 如何将如何将 输输 入入 变换为输变换为输 出，出，淡化淡化 对输对输 入入 输输 出自身的出自身的 描述描述 （由数据（由数据 结结 构来构来 处处 理！）。理！）。大问题中的计算思维 素数判定与大数分解素数判定与大数分解 公公 钥钥 密密 码码 学学 图图 着色着色 问题问题 （ NP难难 解解 问题问题 ）
11、 身份认证（身份认证（ 零知零知 识协议识协议） 稀疏矩稀疏矩 阵计阵计 算算 PageRank值值 （网（网 页页 排名排名 ） 量子力学的范畴基量子力学的范畴基 础础零知识协议所谓所谓 零零 知识知识 认证协议指：一方（认证协议指：一方（ 证明者）在不暴露证明者）在不暴露 有可有可能危及秘密的任何能危及秘密的任何 信息前提下，向另一方（验证方）证信息前提下，向另一方（验证方）证明明 她知道一个她知道一个 秘密。秘密。零知识协议在零知识协议在 1985年由以色列计算机科学家年由以色列计算机科学家 Shafi Goldwasser等人提出。等人提出。Shafi Goldwasser图着色与零知
12、识协议 图图 的的 3-着色着色 问题问题 ：任：任 给给 一个一个 图图 ， 设计设计 一种方案，使用一种方案，使用 3种种颜颜 色着色色着色 图图 中的各个中的各个 节节 点，使得任意相点，使得任意相 邻邻 两个两个 节节 点（有点（有 边边相相 连连 的的 节节 点）的点）的 颜颜 色不同。色不同。 3-图图 着色着色 问题问题 是一个是一个 NP难难 解解 问题问题 ， 简单简单 地地 说说 ，就是没有快，就是没有快速算法能速算法能 对对 任何任何 给给 定的定的 图图 完成完成 3-着色。着色。 但反但反 过过 来可以快速生成来可以快速生成 3-着色的着色的 图图 ！图着色与零知识协
13、议协同计算 一组人一组人 通过通过 其各自拥有的私秘信息（如年龄、体其各自拥有的私秘信息（如年龄、体重等）共同计算出一个共享的信息，但在计算过重等）共同计算出一个共享的信息，但在计算过程中不透露出个人的秘密。程中不透露出个人的秘密。 例如：例如： Alice, Bob, Carol想计算他们的体重之和，想计算他们的体重之和，但都不希望别人知道自己的体重。但都不希望别人知道自己的体重。协同计算1. 每人随机选择每人随机选择 0到到 1000之间的两个数，然之间的两个数，然后再选择后再选择 出出 第三个数，使得三个数之和模第三个数，使得三个数之和模1000后恰好是自己的体重。后恰好是自己的体重。2
14、. 每人每人 将随机选择的两个数分别发送给将随机选择的两个数分别发送给 其其他两人。他两人。4. 每个人将每个人将 三个人的数相加后再模三个人的数相加后再模 1000后后的余数就是三人的体重之和。的余数就是三人的体重之和。3. 每人将自己的第三个数与接收到的其他人每人将自己的第三个数与接收到的其他人的共享数相加，并将结果模的共享数相加，并将结果模 1000。计算思维与数学思维的关系 关注的关注的 对对 象不同象不同 关注的关注的 问题问题 不同不同 都有多都有多 级级 抽象抽象 层层 次次 使用数学方法来使用数学方法来 证证 明或研究算法明或研究算法 问题问题 计计 算思算思 维维 会反作用于
15、数学（会反作用于数学（ 这这 点非常关点非常关 键键 ！）！） 指数运算、逻辑推理和化简法则指数运算、逻辑推理和化简法则(am)n = amn. p (q r) p q r. 两者的共同点是什么？两者的共同点是什么？参见：樊磊等，利用计算直觉理解参见：樊磊等，利用计算直觉理解 抽象抽象 数学数学 概念概念 ，黑龙江高教研究，黑龙江高教研究， 2005年。年。计算思维对数学的反作用什么是计算思维？ 计算思维的实质计算思维的实质 是将问题表征为关于某种计算模型的信是将问题表征为关于某种计算模型的信息处理，并在此基础上寻求问题的算法解。息处理，并在此基础上寻求问题的算法解。 依问题的情况可能需要发现新的计算模型或修改现有的依问题的情况可能需要发现新的计算模型或修改现有的模型。模型。 计算思维对每个人都是基本技能，不仅仅是对计算机科计算思维对每个人都是基本技能，不仅仅是对计算机科学家。学家。 在儿童的基本分析能力的在儿童的基本分析能力的 构成构成 上，除阅读、书写、算术上，除阅读、书写、算术外，还应加上计算外，还应加上计算 （ 思维思维 ） 。 印刷出版促进了阅读、书写、算术能力的普及，而计算印刷出版促进了阅读、书写、算术能力的普及，而计算机则将促进计算思维的普及。机则将促进计算思维的普及。计算思维的特征 概念化概念化 和抽象化和抽
